Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.