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:

../../_images/insertion_sort.png

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)\).