Elementary Sorting

Exercise 1: Manual Sorting (15 points)

Demonstrate how the three sorting algorithms shown in the lecture sort the given array in ascending order. You may skip loop iterations in which nothing changes. An example trace for selection sort is shown below.

1. Show how selection sort sorts the array (E, A, S, Y, Q, U, E, S, T, I, O, N).
2. Show how insertion sort sorts the array (E, A, S, Y, Q, U, E, S, T, I, O, N).
3. Show how shellsort sorts the array (E, A, S, Y, S, H, E, L, L, Q, U, E, S, T, I, O, N).

Exercise 2: Short questions (10 points)

1. Which method runs faster for an array with all keys identical, selection sort or insertion sort?
2. Which method runs faster for an array in reverse order, selection sort or insertion sort?

Exercise 3: Implementation (25 points)

Download Material.zip and implement the missing functions in Sorting.py. You can check your solution by executing the program using the provided GradingList.txt.

Related files: Sorting.py, DSA.py, GradingList.txt

1. The method __lt__ returns a boolean indicating the correct order of two students self and other (True means self is "smaller"). Students should be ordered by grade. For equal grades, fall back to surname and then first name. Example: C. Ivey (1.7), C. Grieve (2.3), L. Stenger (2.3), S. Stenger (2.3).
2. The method selectionSort performs the selection sort algorithm introduced in the lecture.
3. The method insertionSort performs the insertion sort algorithm introduced in the lecture.
4. The method shellSort performs the shellsort algorithm introduced in the lecture.

Exercise 4: Improving Insertion Sort (15 points)

Choose and implement one of the two practical improvements for insertion sort. You may use helper methods if that keeps the initial method call clean.