## 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*^{2}) 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`.

Last update: Wednesday, February 8th, 2012mflatt@cs.utah.edu |