When evaluating sorting algorithms, there many factors that might affect how fas

Question

When evaluating sorting algorithms, there many factors that might affect how fast an algorithm will run when it is programmed for a real machine: CPU speed, language used, type of data being sorted, type of operating system, and the number of concurrent processes running at the same time. For this reason, comparing actual running times of an algorithm is ineffectual for making judgments about how good the algorithm might be. To effectively make a judgment that is free of real world constraints, computer scientists, when comparing sorting algorithms, often simply count the number of comparisons an algorithm makes.

In this exercise, we will add a counter to the MergeSorter program to help us measure the number of comparisons of array elements being made while the routine is completing the sort.

The MergeSorter code is listed below.

The behavior we want to monitor occurs in this section of code,

It is in the above section that we compare array elements and decide which element becomes part of our merged and sorted array. By counting the number of comparisons here, we obtain a measurement that helps us gauge the speed of the algorithm. Add code that will count each comparison, maintaining the result in an integer counter. Supply a method getCounter to retrieve the counter. Supply a second method called resetCounter to set the counter to 0.

The code below supports creating and swapping elements in arrays of varying sizes.

Modify the main program below so you can test sorting arrays with sizes 10000, 20000, …,90000.

What are your results?

Explanation / Answer

/**
This class contains utility methods for array manipulation.
*/  

public class ArrayUtil
{
/**
Creates an array filled with random values.
@param length the length of the array
@param n the number of possible random values
@return an array filled with length numbers between
0 and n - 1
*/
public static int[] randomIntArray(int length, int n)
{  
int[] a = new int[length];   
for (int i = 0; i < a.length; i++)
{
a[i] = (int) (Math.random() * n);
}
  
return a;
}

/**
Swaps two entries of an array.
@param a the array
@param i the first position to swap
@param j the second position to swap
*/
public static void swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

public class MergeSorter
{
private static int counter=0;
private static void merge(int[] first, int[] second, int[] a)
{  
int iFirst = 0; // Next element to consider in the first array
int iSecond = 0; // Next element to consider in the second array
int j = 0; // Next open position in a

// As long as neither iFirst nor iSecond is past the end, move
// the smaller element into a
while (iFirst < first.length && iSecond < second.length)
{  
if (first[iFirst] < second[iSecond])
{  
a[j] = first[iFirst];
iFirst++;
}
else
{  
a[j] = second[iSecond];
iSecond++;
}
MergeSorter.counter++;
j++;
}

// Note that only one of the two loops below copies entries
// Copy any remaining entries of the first array
while (iFirst < first.length)
{
a[j] = first[iFirst];
iFirst++; j++;
}
// Copy any remaining entries of the second half
while (iSecond < second.length)
{
a[j] = second[iSecond];
iSecond++; j++;
}
}
  
public static void sort(int[] a)
{
int end=a.length-1;
if(end==0)
return;
int start=0,mid=end/2;
int left[]=new int[mid-start+1];
int right[]=new int[end-(mid+1)+1];
for(int i=0;i<=mid;i++)
left[i]=a[i];
for(int i=mid+1,j=0;i<=end;i++,j++)
right[j]=a[i];
merge(left,right,a);
}
  
public static void resetCounter()
{
MergeSorter.counter=0;
}
  
public static int getCounter()
{
return MergeSorter.counter;
}
}

public class MergeSortDemo
{  
public static void main(String[] args)
{  
for(int i=10000;i<=90000;i+=10000)
{
int[] a = ArrayUtil.randomIntArray(i, i);
MergeSorter.resetCounter();
MergeSorter.sort(a);
System.out.println("Array size: "+i+"; comparisons: " + MergeSorter.getCounter());
}
}
}

Results obtained are:

Array size: 10000; comparisons: 5829
Array size: 20000; comparisons: 10100
Array size: 30000; comparisons: 22053
Array size: 40000; comparisons: 38196
Array size: 50000; comparisons: 25229
Array size: 60000; comparisons: 30164
Array size: 70000; comparisons: 38104
Array size: 80000; comparisons: 48198
Array size: 90000; comparisons: 70536

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.