Sorts Covered in Lecture

Implement the two sorting algorithms covered in lecture: selection sort and insertion sort.

Quicksort

This method consists of placing an element (called the pivot) of the sequence to be sorted at its final position by permuting all elements such that all those smaller than it are to its left and all those larger are to its right. This operation is called partitioning. For each of the resulting sub-sequences, a new pivot is defined and the partitioning operation is repeated. This process is repeated recursively until the sequence is sorted. In practice, the pivot is either the first or the last element of the sequence to be sorted. In the following example, the pivot is the last element of the sequence.

|--- | quicksort | 28 | 13 | 20 | 35 | 21 | 19 | 15 | 18 | pivot = 18 | | partition | 15 | 13 | 18 | 20 | 35 | 21 | 19 | 28 | pivot placed | | quicksort | 15 | 13 | | | | | | | pivot = 13 | | partition | 13 | 15 | | | | | | | pivot placed | | quicksort | | | | 20 | 35 | 21 | 19 | 28 | pivot = 28 | | partition | | | | 20 | 19 | 21 | 28 | 35 | pivot placed | | quicksort | | | | 20 | 19 | 21 | | | pivot = 21 | | partition | | | | 20 | 19 | 21 | | | pivot placed | | quicksort | | | | 20 | 19 | | | | pivot = 19 | | partition | | | | 19 | 20 | | | | pivot placed | | done | 13 | 15 | 18 | 19 | 20 | 21 | 28 | 35 | |

The objective is therefore to write the quicksort algorithm

Comparisons

To evaluate the performance of these 3 algorithms, test them on examples of integer arrays of varying sizes with random numbers. Also test the influence of sorting a partially/fully sorted array.