We shall explore various (in-place) algorithms for sorting an array of integers. In your favorite programming language, implement: the insertion sort algorithm, and the heapsort algorithm. Your programs must also output the number of times two elements are swapped which we shall use as the measure of running time.
1. Write a program that implements the Insertion Sort algorithm.
2. Write a program that for a given n generates a Pseudo-Random array of size n, in that index i contains (13 · i) mod n. For example, if n = 10 and you have chosen a language where the first index in an array is 0 (in some languages it is 1), you should return an array with the elements
0,3,6,9,2,5,8,1,4,7.
3. Write a program that for a given n generates an Almost-Ordered array of size n, in that index i contains i, except if i mod 13 = 12 in which case it contains (i + 13) mod n. For example, if n = 40 you should return an array with the elements ...10,11,25,13,14,...23,24,38,26,27,...36,37,11,39.
4. Run your Insertion Sort algorithm on 6 test sets: Pseudo-Random input and Almost-Ordered input, each of size 100, of size 1,000, and of size 10,000. Report the running times (the number of swaps).
5. Write a program that implements the HeapSort algorithm. Recall that the first step is to convert the array into a heap, as done by the pseudo-code
for i ← n downto 1 sift(i)
where sift is defined on the lecture slides (and corresponds to what Cormen calls Max-Heapify).
For this question, feel free to look online for inspiration!
6. Run your HeapSort algorithm on the 6 test sets from Question 4, and report the running times (that is, number of swaps).
7. Repeat Question 6 for a version of HeapSort that uses an alternative approach (with percolate defined on the lecture slides) to convert the input array into a heap:
for i ← 1 to n
percolate(i)
