16. Sorting
Sorting is not a data structure.
Data structures and sorting algorithms are linked.
In this topic we will make some assumptions:
Each algorithm is interchangeable.
Each will receive an array of elements.
Each array positions contain data to be sorted.
The arrays are of size \(N\).
Each element of the array have the operators \(<,>,==\) implemented.
16.1. Insertion Sort
Insertion Sort is one of the simplest sorting algorithms.
16.1.1. Algorithm
The idea:
Works in \(N-1\) passes.
For pass \(p=1\) through \(N-1\):
Move \(p\) to the right to have the elements from 0 to \(p\) sorted.
Based on the fact that elements from 0 to \(p-1\) are already sorted.
Example
Below an example of the process:
16.1.2. Implementation
We can do a very quick implementation:
1/** Implements the insertion sort algorithm. */
2public class InsertionSort {
3 /** Sort the table using insertion sort algorithm.
4 @pre table contains Comparable objects.
5 @post table is sorted.
6 @param table The array to be sorted
7 */
8 public static <T extends Comparable<T>> void sort(T[] table) {
9 for (int nextPos = 1; nextPos < table.length; nextPos++) {
10 // Invariant: table[0 . . . nextPos ‐ 1] is sorted.
11 // Insert element at position nextPos
12 // in the sorted subarray.
13 insert(table, nextPos);
14 } // End for.
15 } // End sort.
16
17 /** Insert the element at nextPos where it belongs
18 in the array.
19 @pre table[0 . . . nextPos ‐ 1] is sorted.
20 @post table[0 . . . nextPos] is sorted.
21 @param table The array being sorted
22 @param nextPos The position of the element to insert
23 */
24 private static <T extends Comparable<T>> void insert(T[] table, int nextPos) {
25 T nextVal = table[nextPos];
26 // Element to insert.
27 while (nextPos > 0 && nextVal.compareTo(table[nextPos - 1]) < 0) {
28 table[nextPos] = table[nextPos - 1];
29 // Shift down.
30 nextPos--;
31 // Check next smaller element.
32 }
33 // Insert nextVal at nextPos.
34 table[nextPos] = nextVal;
35 }
36}
Activity
Apply this code to the previous example.
16.1.3. Analysis
Now we will calculate the running time of this algorithm.
Activity
What is the Big Oh running time of Insertion sort?
We can calculate the precise running time.
The number of tests in the inner loop is at most \(p+1\) for each \(p\).
It sums to : \(\sum_{i=2}^{N}i=2+3+4+\dots + N = \Theta(N^2)\)
16.2. Heapsort
The algorithm is based on binary heap.
The idea:
We build a binary heap of \(N\) elements.
Then, we perform \(N\) delete operations.
We put these elements in another array.
Building the heap takes \(O(N)\) time.
Each delete takes \(O(\log N)\) time.
Activity
What is the running time?
The only downside is that it double the memory used.
Activity
Sort the following array:
[31,41,59,26,53,58,97]
.Show each step.
16.2.1. Analysis
Building the heap uses less than \(2N\) comparisons.
The \(i\) th delete uses at most less \(2\lfloor \log (N-i+1) \rfloor\) comparisons.
For a total of \(2N\log N - O(N)\) if \(N\geq 2\) comparisons.
This is why we have \(O(N\log N)\).