CS 2420-20 Homework 7

Due: Thursday, February 9th, 2012 9:10am

Start with quicksort.c from sort.zip, and fill in the implementation of quick_sort as in class.

Part 1 – Randomly Select the Pivot Element

Quicksort takes O(n²) time if the pivot element is always the first one and the elements starts in order or in reverse order. This problem can be fixed by randomly picking a pivot element, instead of always using the first element as a pivot. Furthermore, an easy way to pick a random pivot without changing the function much is to swap the first element with a random element in quick_sort before starting pivot comparisons.

Fix quick_sort by adding a swap with a random element before pivot comparisons. To get a random number, call the rand function, which takes no arguments and returns a random non-negative integer (and then you can use modulo and other arithmetic to convert it to a number in the right range).

By using inputs such as 10k.txt and 20k.txt, you should be able to confirm that the revised quick_sort has practically linear performance.

Part 2 – Sorting Strings

Copy and paste (yikes!) your quicksort.c to quicksort_string.c, and make quicksort_string.c sort strings instead of numbers.

You’ll have to adjust the array container to work with strings instead of integers, and you’ll need to use strcmp to compare strings. In main, you’ll need to change atoi(buffer) to strdup(buffer), which copies the string out of buffer. Optionally, to drop the newline character, use buffer[strlen(buffer)-1] = 0 before calling strdup.