Merge sort - Programmers Heaven

#### Howdy, Stranger!

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

# Merge sort

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))
else
while(!in1.isEmpty()) // move the remaining elements of in1
while(!in2.isEmpty()) // move the remaining elements of in2
}[/code]

• 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))
: else
: while(!in1.isEmpty()) // move the remaining elements of in1
: while(!in2.isEmpty()) // move the remaining elements of in2
: }[/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?
• 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++;
}
else
while(!in1.isEmpty()) // move the remaining elements of in1
while(!in2.isEmpty()) // move the remaining elements of in2
}

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);
}
}
• 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++;
: }
: else
: while(!in1.isEmpty()) // move the remaining elements of in1
: while(!in2.isEmpty()) // move the remaining elements of in2
: }
:
: 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)?