Question 3: Quicksort (30%) (using C programming)

You are asked to write a program to perform quicksort on an array of strings in the ascending lexicographical order (i.e. ASCII code). You should select the pivot as the median of the first, middle and last element. In addition, you need to hide the pivot at the first position of the array in its iteration. Output the whole array after each partition. You can safely assume that all strings are distinct and contain no spaces, and the length of a stringis at most 100.

Your program should read the input from the file, and output the answer to another file. The first argument is the input file name, while the second argument is the output file name. Name your program as lab2-q3.c.

Input file: First line, n, an integer describes the length of the array. Second line, n distinct strings, the unsorted array.

Output file: k lines, k is the number of partition steps. Each line should have exactly n strings separated by a space, indicating the result of the partition. Then, print an empty line. Then, output exactly n strings separated by a space, the result of quicksort.

Sample Input:

4 Apple Orange Banana Pear 

Sample Output:

Banana Apple Orange Pear Apple Banana Orange Pear