Quick Sort

In this homework assignment, you will count the number of comparisons used to quick sort an array of integers given in an input file. You will do this for four different ways of choosing the pivot element in quick sort. You will also compare the running times of the algorithm when using four different pivoting rules.

Here are the steps and requirements on what youll need to do. Download the sample input text files hw3_input-1.txt, hw3_input-2.txt, hw3_input-3.txt. These files contain one integer in each row, and youll use these numbers for your input array. hw3_input-1.txt file contains all of the integers between 1 and 10,000 (inclusive, with no repeats) in random order. This is a short sample file just for your debugging of the correctness of sorting. hw3_input-2.txt file contains all of the integers between 1 and 1000,000 (inclusive, with no repeats) in random order, similar to your first homework. hw3_input-3.txt file contains integers from 1 and 1000,000 in sorted order. You should use these files as inputs to test your program. However, your program should work with other input files with different number and different order of integers also.

Your main task is to compute the total number of comparisons and measure the actual running time used to sort the given input file by Quick Sort algorithm. As you know, the number of comparisons depends on which elements are chosen as pivots, so we'll ask you to explore four different pivoting rules.

When counting, you should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length m, you should simply add (m-1) to your running total of comparisons. (This is because the pivot element is compared to each of the other (m-1) elements in the subarray in this recursive call.). Once you compute the number of comparisons, your program should output the final answer, in addition to the running time.

WARNING: The Partition subroutine can be implemented in several different ways, and different implementations can give you differing numbers of comparisons. For this homework, you should implement the Partition subroutine exactly as it is described in the lecture (otherwise you might get a wrong answer). Also, recall that you must exchange the pivot element with the first element in the array just before the main Partition subroutine, as described in the lecture.

How to choose the pivot? Use the following four options. You need to implement them all. Pivot Option 1: Always use the first element of the array as the pivot element. Pivot Option 2: Always use the middle element of the given array. That is, use (n-1)/2th number in the array as the pivot. Pivot Option 3: Always choose a random element from the given array and use that as the pivot. (use random();) Pivot Option 4: Always use the "median-of-three" pivot rule. [The primary motivation behind this rule is to do a little bit of extra work to get much better performance on input arrays that are nearly sorted or reverse sorted.]

In more detail, you should choose the pivot as follows. Consider the first, middle, and final elements of the given array. (If the array has odd length it should be clear what the "middle" element is; for an array with even length 2k, use the kth element as the "middle" element. So for the array 4 5 6 7, the "middle" element is the second one ---- 5 and not 6!) Identify which of these three elements is the median (i.e., the one whose value is in between the other two), and use this as your pivot.

EXAMPLE: For the input array 8 2 4 5 7 1 you would consider the first (8), middle (4), and last (1) elements; since 4 is the median of the set {1,4, 8}, you would use 4 as your pivot element. SUBTLE POINT: A careful analysis would keep track of the comparisons made in identifying the median of the three candidate elements. You should NOT do this. That is, you should simply add (m-1) to your running total of comparisons every time you recurse on a subarray with length m, in the same way for all four options.

So, your task is to 1. Given an input file, sort the first N numbers in the file using Quick Sort algorithm. 2. Implement 4 different ways of choosing a pivot in Quick Sort. (first, middle, random, median-of-three). 3. Count the total number of comparisons and measure the running time for N = 10000 and 1000000. 4. [Optional, not graded] Find out which one is best for which input file. 5. [Optional, not graded] Try to find a better way of choosing a pivot.

You must implement one program using C, and you source code MUST have the filename quick_sort.c. The file names must be exactly as given, otherwise it wont be graded and you will get zero points.

Your program must take three command line arguments: , , Ex> ./quick_sort Ex> ./quick_sort hw3_input-2.txt 1000000 3 Ex> ./quick_sort hw3_input-3.txt 1000000 4

Your program should do the following For a given N value, read the first N integers from the input file, put them into an array of integers, and sort them using quick sort algorithm. if N > K, then your program should sort all K, and exactly K, numbers in the file correctly. Use the pivot option specified by the pivot option argument (1, 2, 3, 4). Your program MUST output on the sorted result on the screen. Your program MUST ALSO output the number of comparisons as well as the running time of the program in milliseconds. Make sure that your sorted result is correct!! $ ./quick_sort hw3_input-1.txt 10000 1 sorted result N = 10000, Running_Time = 1.086 ms Pivot option = 1 Number of comparisons = 162085 $ ./quick_sort hw3_input-1.txt 10000 2 sorted result N = 10000, Running_Time = 1.060 ms Pivot option = 2 Number of comparisons = 150657 $ ./quick_sort hw3_input-1.txt 10000 3 sorted result N = 10000, Running_Time = 1.196 ms Pivot option = 3 Number of comparisons = $ ./quick_sort hw3_input-1.txt 10000 4 sorted result N = 10000, Running_Time = 1.079 ms Pivot option = 4 Number of comparisons =

You program must work with other input files as well, not just 'hw3_input-*.txt'. We will test and grade your program with other input files with different number of integers.

__________________________________________________________________________________________

Provided quick_sort.c:

/** * "Quick Sort" * - ./quick_sort * - measure running time of 'Quick Sort' * - count number of comparisons in 'Quick Sort' * - try different 'choose_pivot' methods * * name / ID **/

#include #include #include #include #include

void choose_pivot (int *data, unsigned int n) { /* your code here */ }

unsigned long quick_sort (int *data, unsigned int n) { unsigned long cnt = (n - 1); // number of comparisons

/* your code here */

// choose pivot and always place it at first element of array choose_pivot(data, n);

/* your code here */

return cnt; }

int main (int argc, char* argv[]) {

/* your code here */

/* your code here */

/* your code here */ // Please keep these printf statements! printf("N = %7d,\tRunning_Time = %.3f ms ", N, duration); printf("Pivot option = %d ", m_pivot_option); printf("Number of comparisons = %lu ", comparisons);

/* your code here */ return 0; }