displaying every 1000 comparisons in merge sort

gusy, I have the following merge sort algorithm, and if the number of comparisons is over 1000, I need to display every 1000th comparison, but in this case is kind of tricky since the merge sort is recursive... could anyone give me a hand on how to implement this... here's the code

Code :

//sorting array using merge sort
static void mergeSort(int[] a)
{
if(a.length >= 2)
{
int mid = a.length / 2;
int[] first = new int[mid];
int[] second = new int[a.length - mid];
for(int i = 0; i < first.length; i++) { first[i] = a[i]; }
for(int i = 0; i < second.length; i++)
{
second[i] = a[mid+i];
}
mergeSort(first);
mergeSort(second);
merge(first, second, a);
}
}
//merging first and second halfs of mergeSort array
static void merge(int[] first, int[] second, int[] a)
{
int iFirst = 0;
int iSecond = 0;
int i = 0;
//moving the smaller element into a
while(iFirst < first.length && iSecond < second.length)
{
if(first[iFirst] < second[iSecond])
{
a[i] = first[iFirst];
iFirst++;
}
else
{
a[i] = second[iSecond];
iSecond++;
}
i++;
}
counter += i;
//copying the remaining of first array
while(iFirst < first.length)
{
a[i] = first[iFirst];
iFirst++; i++;
}
//copying the remaining of second array
while(iSecond < second.length)
{
a[i] = second[iSecond];
iSecond++; i++;
}
}

Re: displaying every 1000 comparisons in merge sort

Can you show where in the code you are trying to display something?

How are you trying to detect the 1000th event?

Re: displaying every 1000 comparisons in merge sort

Quote:

Originally Posted by

**Norm**
Can you show where in the code you are trying to display something?

How are you trying to detect the 1000th event?

I was thinking to implement a if statement right after counter that output to screen in increments of 1000, but it is not working, it outputs wired numbers, besides what if total comparisons are smaller than 1000.

Code :

static void merge(int[] first, int[] second, int[] a)
{
int iFirst = 0;
int iSecond = 0;
int i = 0;
//moving the smaller element into a
while(iFirst < first.length && iSecond < second.length)
{
if(first[iFirst] < second[iSecond])
{
a[i] = first[iFirst];
iFirst++;
}
else
{
a[i] = second[iSecond];
iSecond++;
}
i++;
}
counter += i;
if(counter >= 1000 && counter % 1000 == 0)
System.out.println(counter);
//copying the remaining of first array
while(iFirst < first.length)
{
a[i] = first[iFirst];
iFirst++; i++;
}
//copying the remaining of second array
while(iSecond < second.length)
{
a[i] = second[iSecond];
iSecond++; i++;
}
}

Re: displaying every 1000 comparisons in merge sort

ok, I got it.... is working now, but I have one more question, if I need to display the same for both selection sort and merge sort, wouldn't be better to create a method for that?

Re: displaying every 1000 comparisons in merge sort

What would the method do? Test a value and print a message?

Re: displaying every 1000 comparisons in merge sort

Quote:

Originally Posted by

**Norm**
What would the method do? Test a value and print a message?

test whether the number of comparison is over 1000, if it is then print every 1000th number, and then print the total number of comparisons

Re: displaying every 1000 comparisons in merge sort

Not much more than the if statement you are currently using.