• Sorting: Quick Sort

    In this, last in the series, post I will implement probably on of the best known sorting algorithm - Quick Sort. The idea of the in-place algorithm is as follows:

    • randomize initial list
    • select first element as partition value
    • scan i from left to right so long as current element is less than partition value
    • scan j from right to left so long as current element is more than partition value
    • exchange i-indexed element with j-indexed element
    • repeat until i and j cross
    • exchange first element with j-indexed element
    • split list into two sub-lists bounded by j-indexed partition
    • recursively repeat until list contains one or zero elements

    After each iteration when first element is exchanged with j-indexed element following invariant should be valid: elements to left are smaller or equal than partition value and elements to the right are bigger or equal. We can visualize quick sort algorithm by sorting following list [3 5 4 7 2 1]. I’ll use colors to specify partition value, current i-indexed element and current j-indexed element.

    Iteration #1 [3 5 4 7 2 1] → [3 5 4 7 2 1] → [3 5 4 7 2 1] → [3 1 4 7 2 5] [3 1 4 7 2 5] → [3 1 4 7 2 5] → [3 1 2 7 4 5] [3 1 2 7 4 5] → [3 1 2 4 5] → [3 1 2 7 4 5] → [2 1 3 7 4 5]

    Iteration #2 [ [2 1] 3 [7 4 5] ] → [ [2 1] 3 [7 4 5] ] → [ [2 1] 3 [7 4 5] ] → [ [1 2] 3 [7 4 5] ]

    Iteration #3 [ [1] [2] 3 [7 4 5] ] → [1 [2] 3 [4 7 5] ]

    Iteration #4 [1 [2] 3 [7 4 5] ] → [1 2 3 [7 4 5] ]

    Iteration #5 [1 2 3 [7 4 5] ] → [1 2 3 [7 4 5] ] → [1 2 3 [7 4 5] ] → [ 1 2 3 [7 4 5] ] → [1 2 3 [5 4 7] ]

    Iteration #6 [1 2 3 [5 4] 7] → [1 2 3 [5 4] 7] → [1 2 3 [5 4] 7]  → [1 2 3 [4 5] 7]

    Iteration #7 [1 2 3 [4] [5] 7] → [1 2 3 4 [5] 7]

    Iteration #8 [1 2 3 4 [5] 7] → [1 2 3 4 5 7]

    For the sake of easiness I’ll skip list randomization step. Implementation of the quick sort heavily rely on sort and partition functions:

    Complexity: O(n·logn).



  • Sorting: Merge Sort

    In this post I will implement well known divide and conquer sorting algorithm – Merge Sort. The idea of the algorithm is as follows:

    • recursively divide unsorted list into two sub-lists
    • continue until each sub-list contains 1 element
    • recursively merge them back in the right order

    We can visualize merge sort algorithm by sorting following list [3 5 4 7 2 1]. I’ll use colors to specify current split list and current merge elements.

    Split Iteration #1 [3 5 4 7 2 1][3 5 4] [7 2 1] [3 5 4] [7 2 1] → [3] [5 4] [7 2 1] [3] [5 4] [7 2 1] → [3] [5 4] [7 2 1]

    Merge Iteration #1 [3] [5 4] [7 2 1] → [3] [5 4] [7 2 1]

    Split Iteration #2 [3] [5 4] [7 2 1] → [3] [5] [4] [7 2 1]

    Merge Interation #2 [3] [5] [4] [7 2 1] → [3] [4 … [3] [5] [4] [7 2 1] → [3] [4 5] [7 2 1]

    Merge Iteration #3 [3] [4 5] [7 2 1] → [… [3] [4 5] [7 2 1] → [3 4 … [3] [4 5] [7 2 1] → [3 4 5] [7 2 1]

    Split Iteration #3 [3 4 5] [7 2 1] → [3 4 5] [7] [2 1] [3 4 5] [7] [2 1] → [3 4 5] [7] [2 1]

    Merge Iteration #4 [3 4 5] [7] [2 1] → [3 4 5] [7] [2 1]

    Split Iteration #4 [3 4 5] [7] [2 1] → [3 4 5] [7] [2] [1]

    Merge Iteration #5 [3 4 5] [7] [2] [1] → [3 4 5] [7] [… [3 4 5] [7] [2] [1] → [3 4 5] [7] [1 2]

    Merge Iteration #6 [3 4 5] [7] [1 2] → [3 4 5] [1 … [3 4 5] [7] [1 2] → [3 4 5] [1 2 … [3 4 5] [7] [1 2] → [3 4 5] [1 2 7]

    Merge Iteration #7 [3 4 5] [1 2 7] → [1 …] [3 4 5] [1 2 7] → [1 2 …] [3 4 5] [1 2 7] → [1 2 3 …] [3 4 5] [1 2 7] → [1 2 3 4 …] [3 4 5] [1 2 7] → [1 2 3 4 5 …] [3 4 5] [1 2 7] → [1 2 3 4 5 7]

    Implementation of the merge sort heavily rely on sort and merge functions:

    Complexity: O(n·logn).



  • Sorting: Shell Sort

    In this post I will implement more advanced sorting algorithm – Shell Sort. Shell sort is also known as n-gap insertion sort. Instead of comparing only adjacent pair, shell sort makes several passes and uses various gaps between adjacent elements (ending with the gap of 1 or classical insertion sort). The idea of the algorithm is as follows:

    • calculate gaps by using one of the existing sequences, eg.: Shell’s (⌊n/2k⌋), Pratt’s (2p3q) or in our case – Knuth’s ((3k - 1) / 2) as being one of the most popular and due to sequence generation easiness
    • starting from the beginning of the list compare value with every n·gap elements on the left (if any)
    • swap their positions if they are not in the right order
    • continue until element on the left is smaller than current element
    • repeat with the smaller gap

    We can visualize shell sort algorithm by sorting following list [3 5 4 7 2 1] using gaps 4 and 1. I’ll use colors to specify current adjacent pair.

    Iteration #1, gap 4 : [3 5 4 7 2 1] [3 5 4 7 2 1] → [2 5 4 7 3 1]

    Iteration #2, gap 4 : [2 5 4 7 3 1] [2 5 4 7 3 1] → [2 1 4 7 3 5]

    Iteration #3, gap 1 : [2 1 4 7 3 5] [2 1 4 7 3 5] → [1 2 4 7 3 5]

    Iteration #4, gap 1 : [1 2 4 7 3 5] [1 2 4 7 3 5] → [1 2 4 7 3 5]

    Iteration #5, gap 1 : [1 2 4 7 3 5] [1 2 4 7 3 5] → [1 2 4 7 3 5]

    Iteration #6, gap 1 : [1 2 4 7 3 5] [1 2 4 7 3 5] → [1 2 4 3 7 5] [1 2 4 3 7 5] → [1 2 3 4 7 5] [1 2 3 4 7 5] → [1 2 3 4 7 5]

    Iteration #7, gap 1 : [1 2 3 4 7 5] [1 2 3 4 7 5] → [1 2 3 4 5 7] [1 2 3 4 5 7] → [1 2 3 4 5 7]

    Implementation of the shell sort is heavily based on the insertion sort:

    Complexity: O(n3/2) using Knuth’s sequence.