Quicksort

This is algorithm and advanced data strucrture class.

Write a program that runs one of three variants of the Quicksort algorithm (depending on program arguments). Your program will output (print to standard out) the total number of of times that the PARTITION procedure performed a comparison. using Python (you should use either Python 2.7 or Python 3.4 as those are the interpreters that I will use to test your code).

for filling in the following table and pasting it at the top of you file (beneath your names):

+==================+==========+=========+==========+==========+==========+ | file | first | median3 | random-1 | random-2 | random-3 | +==================+==========+=========+==========+==========+==========+ | ordered-10 | 45 | 19 | 26 | 28 | 27 | +------------------+----------+---------+----------+----------+----------+ | ordered-100 | | | | | | +------------------+----------+---------+----------+----------+----------+ | ordered-10000 | | | | | | +------------------+----------+---------+----------+----------+----------+ | randomized-10 | | | | | | +------------------+----------+---------+----------+----------+----------+ | randomized-100 | | | | | | +------------------+----------+---------+----------+----------+----------+ | randomized-10000 | | | | | | +------------------+----------+---------+----------+----------+----------+

The first column indicates these files: ordered-10.txt, ordered-100.txt, ordered-10000.txt, randomized-10.txt, randomized-100.txt, and randomized-10000.txt (Those files are attached). You are required to fill in the remaining columns:

• column 2: the result of calling your program with "X.txt" and "first" as arguments (where X corresponds to the file for that row)
• column 3: the result of calling your program with "X.txt" and "median3" as arguments
• column 4, 5, 6: the result of calling your program with "X.txt" and "random" as arguments (your program should return different results each time)

I've filled in my results for the first row. Please try to keep the formatting of the table as uniform as possible!

MAIN

Your program should accept two command line arguments: (1) a filename, and (2) a string denoting the Quicksort variant. Input files contain a bunch of numbers that you will be sorting (the input format is described below). You can assume that any provided file will not contain any repeated values, and that each value is provided on a separate line.

Depending on the second argument you should execute one of your three Quicksort variants. Possible values for the second argument are first and median3, and random (I will not feed your program invalid input).

Your program will output the total number of comparisons performed by all calls to the PARTITION procedure. If you'd like, you can use a global variable to keep track of your total number of comparisons.

PARTITION

NOTE: It is very important that you implement your partitioning procedure exactly as described here.

You should only need to write your partitioning procedure once (it will be used by all Quicksort variants), and it should assume that the pivot value is the first element of the given subarray.

// // Inputs: // A : an input array // l : the index of the leftmost value (the pivot) // r : the index of the rightmost value // Note: the indices l,r (inclusive) define a subarray of A // // Outputs: // 1 : the index of the pivot after partitioning // 2 : the number of comparisons that were performed // Note: if you want to calculate the number of comparisons using a // global variable then you only need the first output. // PARTITION(A, l, r) pivot = A[l] i = l + 1 for j = l + 1 to r if A[j] < pivot swap A[j] and A[i] increment i swap A[l] and A[i-1] return i-1, r-l

QUICKSORT-FIRST

In your first version of Quicksort, you should always use the first element of the current subarray as the pivot. This means that you do not need to do anything special before calling partition (except checking for the base case).

You can check the lecture slides for implementation details.

QUICKSORT-MEDIAN3

In the second version of your algorithm, you should select your pivot as the median of three values: the first element, the final element, and the middle element of the current subarray. For the middle element, if the subarray has an even length then you should take the left-middle element. From these three values, you should take the median.

Since the PARTITION procedure requires the pivot to be the leftmost element of the subarray, you should swap the median value and the first element of the current subarray.

For example, let A=[1 2 3 4 5 6 7 8], l=2

l=2, and r=7

r=7 (indices start at 1

1 for this example). The three values that you will compare are first=2

first=2, middle=4

middle=4, and final=7

final=7. From these three values, the median would be 4

4. So, we need to swap the 2

2 and the 4

4 before calling the PARTITION procedure (A=[1 4 3 2 5 6 7 8]).

QUICKSORT-RANDOM

In the final version of your Quicksort algorithm, you will select the pivot at random. Essentially, you will pick a random number in the closed interval [l, r] and swap it with the element at A[l].

Example

Below is the contents of an input file. The first value in the file (10

10) denotes how many numbers are in the array.

10 3 9 8 5 6 10 7 4 2 1

Below is an example of running your program and what the expected output should be for the above input file.

prompt > ./qs input_file.txt first 24 prompt > ./qs input_file.txt median3 20 prompt > ./qs input_file.txt random 23

As you can see above, the second variant of Quicksort has one fewer calls the the partition procedure. Note: the random version may return different values on your computer.

Note for Python programmers

I am requiring you to include a shebang at the top (very first line!) of your file/script. If you are using Python3 your shebang will look like this:

#!/usr/bin/env python3

If you are using Python 2.7 you should use this:

#!/usr/bin/env python

These will make it easy for me to run your code regardless of which version of Python you choose to use.

For selecting the pivot at random I'd recommend taking a look at random.randint.