Merge sort - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Merge sort

pcs2112pcs2112 Posts: 5Member
i need help placing a counter in this code tha will keep track of the number of comparissons in the sort

[code]public static > void mergeSort (ArrayList in) {

int n = in.size();
if (n < 2)
return; // the in list is already sorted in this case
// divide
ArrayList in1 = new ArrayList();
ArrayList in2 = new ArrayList();
int i = 0;

while (i < n/2) {
in1.add(in.remove(0)); // move the first n/2 elements to in1
i++;
}
while (!in.isEmpty())
in2.add(in.remove(0)); // move the rest to in2
// recur
mergeSort(in1);
mergeSort(in2);
//conquer
merge(in1,in2,in);
}

public static > void merge(ArrayList in1, ArrayList in2, ArrayList in) {

while (!in1.isEmpty() && !in2.isEmpty())
if ((in1.get(0).compareTo(in2.get(0)) <= 0))
in.add(in1.remove(0));
else
in.add(in2.remove(0));
while(!in1.isEmpty()) // move the remaining elements of in1
in.add(in1.remove(0));
while(!in2.isEmpty()) // move the remaining elements of in2
in.add(in2.remove(0));
}[/code]

Comments

  • zibadianzibadian Posts: 6,349Member
    : i need help placing a counter in this code tha will keep track of
    : the number of comparissons in the sort
    :
    : [code]: public static > void mergeSort (ArrayList in) {
    :
    : int n = in.size();
    : if (n < 2)
    : return; // the in list is already sorted in this case
    : // divide
    : ArrayList in1 = new ArrayList();
    : ArrayList in2 = new ArrayList();
    : int i = 0;
    :
    : while (i < n/2) {
    : in1.add(in.remove(0)); // move the first n/2 elements to in1
    : i++;
    : }
    : while (!in.isEmpty())
    : in2.add(in.remove(0)); // move the rest to in2
    : // recur
    : mergeSort(in1);
    : mergeSort(in2);
    : //conquer
    : merge(in1,in2,in);
    : }
    :
    : public static > void merge(ArrayList in1, ArrayList in2, ArrayList in) {
    :
    : while (!in1.isEmpty() && !in2.isEmpty())
    : if ((in1.get(0).compareTo(in2.get(0)) <= 0))
    : in.add(in1.remove(0));
    : else
    : in.add(in2.remove(0));
    : while(!in1.isEmpty()) // move the remaining elements of in1
    : in.add(in1.remove(0));
    : while(!in2.isEmpty()) // move the remaining elements of in2
    : in.add(in2.remove(0));
    : }[/code]:
    :
    Step 0: Declare the counter variable
    Step 1: Locate the comparison(s)
    Step 2: Insert a line before or after the comparison, which increments the counter variable.

    Hint: Is the counter variable an instance variable or a local variable?
  • pcs2112pcs2112 Posts: 5Member
    is this correct where i put my counter and its a instance variable

    public static > void merge(ArrayList in1, ArrayList in2, ArrayList in) {

    while (!in1.isEmpty() && !in2.isEmpty())
    if ((in1.get(0).compareTo(in2.get(0)) <= 0)){
    mergeSortCounter++;
    in.add(in1.remove(0));
    }
    else
    in.add(in2.remove(0));
    while(!in1.isEmpty()) // move the remaining elements of in1
    in.add(in1.remove(0));
    while(!in2.isEmpty()) // move the remaining elements of in2
    in.add(in2.remove(0));
    }

    public static <E extends Comparable<E>> void heapSort ( E[] s)
    {
    for ( int index = (s.length)/ 2 - 1; index >= 0; index--)
    reHeapDown(s, index, s.length -1);
    for ( int index = s.length - 1; index >= 1; index--){
    E temp = s[0];
    s[0] = s[index];
    s[index] = temp;
    reHeapDown(s, 0, index - 1);
    }
    }
  • zibadianzibadian Posts: 6,349Member
    : is this correct where i put my counter and its a instance variable
    :
    : public static > void merge(ArrayList in1,
    : ArrayList in2, ArrayList in) {
    :
    : while (!in1.isEmpty() && !in2.isEmpty())
    : if ((in1.get(0).compareTo(in2.get(0)) <= 0)){
    : mergeSortCounter++;
    : in.add(in1.remove(0));
    : }
    : else
    : in.add(in2.remove(0));
    : while(!in1.isEmpty()) // move the remaining elements of in1
    : in.add(in1.remove(0));
    : while(!in2.isEmpty()) // move the remaining elements of in2
    : in.add(in2.remove(0));
    : }
    :
    : public static <E extends Comparable<E>> void heapSort ( E[] s)
    : {
    : for ( int index = (s.length)/ 2 - 1; index >= 0; index--)
    : reHeapDown(s, index, s.length -1);
    : for ( int index = s.length - 1; index >= 1; index--){
    : E temp = s[0];
    : s[0] = s[index];
    : s[index] = temp;
    : reHeapDown(s, 0, index - 1);
    : }
    : }
    :
    Almost. What happens when in1.get(0) is larger than in2.get(0)?
Sign In or Register to comment.