In this programming exercise you will perform an empirical analysis of the Quick

Question

In this programming exercise you will perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior. That is, you will write a program that counts the number of comparisons performed by QuickSort on an array of a given size. You will run the program on a large number of arrays of a certain size and determine the average number of comparisons performed. You will do this for several different sizes and compare the observed results with what is expected.

Using Python, or Java, write a program that:

prompts the user to enter the number n, of arrays to be processed and the size m, of each array

creates an array, of the given size, containing the integers between 1 and m

for the given number of arrays

randomly unsorts the array

sorts the array using the version of QuickSort developed in your text and in class

counts the number of comparisons performed during the partitioning subroutine of the sort

calculates the average number of comparisons performed in processing all the arrays

You will need to use the versions of QuickSort and Partition given in your text since that was what was used to derive the predicted average complexity you will be comparing your results with.

The program should output the number of arrays processed, the size of the arrays processed and the average number of comparisons per array.

For example, if the user enters 50 and 100 the output would be similar to:

# of arrays processed: 50

# of items in each array: 100

average number of comparisons: 926.02 (Your results may be different!)

The following algorithm can be used to unsort an array A, of size m.

1) FOR i := 1 to m

2)         Generate a random number r, between 1 and m

3)         Swap A[i] and A[r]

Use your program to determine the average number of comparisons performed in sorting 1000 arrays for each of the array sizes, 10, 50, 100, 500, 1000, 5000, 10,000, 50,000 and 100,000. Compare the observed average with the average predicted by the derivation of the average-case time complexity in section 2.4 of your text. Display your results in a table comparing the predicted average with the observed average. You will want to look at the percent difference between the predicted and observed values. Write a paragraph discussing your conclusions about any differences you notice and what they tell you about the actual asymptotic behavior of the quick sort.

Turn in your table, your analysis, and a hard copy of your source file.

Explanation / Answer

Solution: See the code below:

----------------------------------------------

import java.util.Random;
import java.util.Scanner;

/**
* QuickSortAnalysis class
*
*/
public class QuickSortAnalysis {

      
   /**
   * @param args
   */
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner in=new Scanner(System.in);
       System.out.println("Enter number of arrays (n):");
       int n=in.nextInt();
       int[] comparisions=new int[n]; //array to store number of comparisons
       System.out.println("Enter size of each array:");
       int m=in.nextInt(); //size of array
       //loop to process arrays
       for(int i=1;i<=n;i++)
       {
           int[] array = new int[m]; //array allocation
           //fill array
           for(int j=0;j<m;j++)
           {
               array[j]=j+1;
           }
           //randomly unsort array
           Random rndm=new Random();
           for(int j=0;j<m;j++)
           {
               int r = rndm.nextInt(m-1)+1;
               int temp =array[r];
               array[r]=array[i];
               array[i]=temp;
           }
           //sorts array
           QuickSort.sort(array); //use your own method here
           //access comparisons performed during sort
           comparisions[i-1]=QuickSort.getNumberOfComparisions(); //add this method to your class
       }
      
       //calculation of average number of comparisons
       int totalComparisons = 0;
       for(int i=0;i<n;i++)
       {
           totalComparisons+=comparisions[i];
       }
       float averageComparisons=totalComparisons/n;
      
       //printing of output
       System.out.println("# of arrays processed:"+n);
       System.out.println("# of items in each array:"+m);
       System.out.println("Average number of comparisons:"+averageComparisons);

       //closes scanner
       in.close();
   }
}

---------------------------------

Note: I have used my own QuickSort class to sort the array. You can use your own code in place of this. One sample output as generated on my system is given below:

-----------------------------

Enter number of arrays (n):
50
Enter size of each array:
100
# of arrays processed:50
# of items in each array:100
Average number of comparisons:11423.0

----------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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