gistfile1.txt

Logout

My Submissions

Back to Algorithms HW1 

Quicker Sort 

As good algorithms students, you are aware that in the average case, quicksort runs in O(n*lg(n)) time, and insertion sort runs in O(n^2) time.

For reference, here is pseudocode for both insertion sort and quicksort (0 indexed). You will implement your algorithms directly from this pseudocode.

function insertion_sort(array, left, right)
    for i in the interval [left+1, right]
        val_to_insert = array[i]
        j = i
        while j > left and val_to_insert < array[j-1]
            array[j] = array[j-1]
            j = j - 1
        array[j] = val_to_insert

_______________________________________


function quicksort(array, left, right)
    if left < right
        pivot_index = partition(array, left, right)
        quicksort(array, left, pivot_index - 1)
        quicksort(array, pivot_index + 1, right)

function partition(array, left, right)
    pivot_value = array[right]
    store_index = left
    for i in the interval [left, right-1]
        if array[i] < pivot_value
            temp = array[i]
            array[i] = array[store_index]
            array[store_index] = temp
            store_index = store_index + 1
    temp = array[right]
    array[right] = array[store_index]
    array[store_index] = temp
    return store_index

_______________________________________

These are the naive versions of the sorting algorithms as demonstrated in the book (modified to be 0-indexed). First, you should implement these algorithms in Java or C++ and confirm that they are working correctly. 

This, however, is not the assignment! That would be too easy. 

Due to overhead issues, insertion sort is generally faster than quicksort for small arrays. Consequently, any good implementation of quicksort is actually a hybrid sort, in which subarrays less than or equal to than a certain length, K, are sorted by insertion sort rather than more recursive calls to quicksort.

The assignment is to construct a hybrid sort in which the quicksort algorithm is modified so that arrays less than or equal to a certain length are insertion sorted, rather than quicksorted. A problem that has not been answered is "What value of K should be used to know when to quicksort or insertion sort?" The answer to that problem is the assignment. 

We will measure sort efficiency by number of array assignments. That is to say, a line of code in the form

my_array[some_index] = some_value

counts as an array assignment.

Given N (0 < N <= 100), the length of the array, and then N integer elements, your program should determine the value of K (K >= 0) in which the hybrid sort minimizes the number of array assignments. You are free to modify the given psuedocode for insertion sort and quicksort, but make sure the array assignments are not modified.

Your program should output three lines:
K
The total number of assignments made during the sort when using that value of K
The sorted array

If there are multiple values of K that perform equally well, use the smallest.

Sample Input 1:
8
1 2 4 5 1 9 4 3

Sample Output 1:
4
16
1 1 2 3 4 4 5 9 

This output indicates choosing K of 4 yields the minimum number of array assignments at 16 assignments. The sorted array is shown below it. The newlines don't particularly matter. The automatic grader is fairly lenient with whitespace, and as long as there are whitespace between numbers, you should be fine.

Sample Input 2:
8
1 8 2 7 3 6 4 5

Sample Output 2:
4
15
1 2 3 4 5 6 7 8 

Sample Input 3:
16
1804289383 846930886 1681692777 1714636915 1957747793 424238335 719885386 1649760492 596516649 1189641421 1025202362 1350490027 783368690 1102520059 2044897763 1967513926 

Sample Output 3:
6
69
424238335 596516649 719885386 783368690 846930886 1025202362 1102520059 1189641421 1350490027 1649760492 1681692777 1714636915 1804289383 1957747793 1967513926 2044897763 

Sample Input 4:
8
8 2 3 4 5 6 7 1

Sample Output 4:
7
8
1 2 3 4 5 6 7 8

Notes:
1. Make sure you implement the algorithms exactly as shown in the pseudocode, or your number of array assignments may differ.
2. Your program should receive input via stdin (cin/scanf for C++, or System.in for Java) and output to stdout (cout/printf for C++, System.out for Java).
3. Do NOT prompt the user for input with things like "Input size of array: " There is no user to be prompted. Your program is graded automatically. You should not output anything except for the items listed about (Best value of K, number of array assignments using that K, and the sorted array). Anything else is considered incorrect.
4. If you are using Java, your file class should be called Main. Therefore your file will be Main.java. Use no packages.
5. The server is loosely sandboxed. Any attempt to do anything malicious to the server will result in a 0%.
6. The queue is updated every 1 minute.
7. There are 100 test cases.

Submission Notes:
1. Note the time limits. Your program must run all 100 test cases within the time limit. If you get time limit exceeded and you know that your program is fast enough, you are probably waiting for input that isn't there. Check your code. If you still get time limit exceeded, check your code some more.
2. If you get Runtime Error, you probably got a segfault or OutOfBoundsException on one of the test cases.
3. If you get a Compile Error, your probably didn't name your Java program Main or you don't have a main method or you perhaps used some Java 7 or C++11 features. We are only using Java 6 and C++03. All programs are just compiled with the "javac" or "g++" with no additional flags.
4. If you get 0/100, you are probably not outputting the answer correctly, or your program is just really buggy. Make sure your output exactly matches the test outputs above.
5. If you get 99/100 or something, your program probably does not handle some edge case correctly.
6. After you test everything on the server, submit your Java or C++ source code via Moodle. Your code will be compiled and run against a different set of 100 test cases.

Time Limits:
cpp: 10 seconds 
java: 20 seconds