A sorting laboratory

The problem

Build a program that runs several sorting algorithms on the same data and reports exactly how much work each one did.

Requirements

• Insertion sort, merge sort, quick sort and heap sort are each written by hand
• Each sort counts its comparisons and its moves or swaps
• The data can be random, already sorted, reversed, or full of equal values
• All the sorts receive identical copies of the data
• A check after each run confirms that the output really is sorted
• The results are printed as a table, one row per sort

Technologies

• C
• Arrays
• Recursion
• Function pointers
• Random numbers

Step by step

1. Write a function that fills an array with one of the four kinds of data.
2. Write each sort so that it adds to shared counters for comparisons and moves.
3. Write a function that copies the data, runs one sort, and checks the result.
4. Store the sorts in an array of function pointers, so that one loop can run them all.
5. Print a table for each kind of data and each size.
6. Run sizes that double, such as 1,000, 2,000 and 4,000, and compare how each count grows.

Expected result

A tool that shows, with real counts, which sort does the least work on which kind of data.

How it is evaluated

• Every sort produces correct output on every kind of data
• The counters count the same kinds of operation in every sort
• The growth seen in the table matches the Big-O of each sort
• Quick sort's bad case on sorted input shows up, and you can explain it

Ways to improve it

• Add a median-of-three pivot and compare it
• Add counting sort for data with a small range
• Write the results to a CSV file and plot them