Jocodoma

Joco's Tech Blog

0%

Sorting Algorithms

Posted on In , Disqus:
Symbols count in article: 25k Reading time ≈ 23 mins.

Following are going to be covered in this post:

Selection Sort

Reference: https://www.geeksforgeeks.org/selection-sort/

The Selection Sort algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning.

The logic of algorithm is to maintain two subarrays, sorted and unsorted, in a giving array.

In every iteration of Selection Sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray. (swapping)

Steps:

  • Selection
  • Swapping
  • Counter Shift

Example:
11, 25, 12, 22, 64
11, 12, 25, 22, 64
11, 12, 22, 25, 64
11, 12, 22, 25, 64

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

The default implementation is not stable. However, it can be made stable.

Code Snippet

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>  // std::swap
#include <vector>     // std::vector

void selectionSort(std::vector<int>& arr){
    // one by one move boundary of unsorted subarray
    for(int i = 0; i < arr.size()-1; i++){

        // find the minimum element in unsorted array
        int minIdx = i;
        for(int j = i + 1; j < arr.size(); j++){
            if(arr[j] < arr[minIdx])
                minIdx = j;
        }

        // swap the found minimum element with the first element
        std::swap(arr[i], arr[minIdx]);
    }
}
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

void swap(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
}

void selectionSort(int arr[], int len){
    int i=0, j=0, minIdx=0;

    for(i=0; i<len-1; i++){
        minIdx = i;
        for(j=i+1; j<len; j++){
            if(arr[j] < arr[minIdx])
                minIdx = j;
        }
        swap(arr[i], arr[minIdx]);
    }
}

Properties

Time Complexity: O(n^2), as there are two nested loops
Auxiliary Space: O(1)
Sorting in Place: Yes
Stable: No. The default implementation is not stable. However, it can be made stable. Please see stable selection sort for details.

Bubble Sort

Reference: https://www.geeksforgeeks.org/bubble-sort/

Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

The algorithm always needs one more whole pass without any swap to know it is sorted and completed.

Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm. In computer graphics, it is popular to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axix) and with incrementing y. Their order changes (two elements are swapped) only at intersections of two lines.

Code Snippet

Intuitive Implementation

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <vector>     // std::vector
#include <utility>    // std::swap

void bubbleSort(std::vector<int>& arr){
    int n = arr.size();
    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-1-i; j++){
            if(arr[j] > arr[j+1])
                std::swap(arr[j], arr[j+1]);
        }
    }
}

Optimized Implementation

The above one always run O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop did not cause any swap.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>     // std::vector
#include <utility>    // std::swap

void bubbleSort(std::vector<int>& arr){
    int n = arr.size();
    bool isSwapped = false;
    for(int i=0; i<n-1; i++){
        isSwapped = false;
        for(int j=0; j<n-1-i; j++){
            if(arr[j] > arr[j+1]){
                std::swap(arr[j], arr[j+1]);
                isSwapped = true;
            }
        }
        if(!isSwapped)
            break;
    }
}

Complexity

Time Complexity

  • Worst and Average Case: O(n^2). Worst case occurs when array is reverse sorted.
  • Best Case: O(n). Best case occurs when array is already sorted.

Auxiliary Space: O(1)
Sorting in Place: Yes
Stable: Yes

Boundary Cases

Bubble sort takes minimum time (Order of n) when elements are already sorted.

Insertion Sort

Reference: https://www.geeksforgeeks.org/insertion-sort/

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Example:
12, 11, 13, 5, 6
11, 12, 13, 5, 6
11, 12, 13, 5, 6
5, 11, 12, 13, 6
5, 6, 11, 12, 13

Insertion Sort performs two operations:

  1. Scan through the list, comparing each pair of elements.
  2. Swap elements if they are out of order.

Insertion sort is used when number of elements is small. It can be useful when input array is almost sorted, only few elements are misplaced in complete big array.

Binary Insertion Sort

Binary search can be used to reduce the number of comparisons in normal insertion sort. Binary insertion sort uses binary search to find the proper location to insert the selected item at each iteration.

In normal insertion, sorting takes O(i), at the i-th iteration, in worst case. We can reduce it to O(log i) by using binary search. The algorithm, as a whole, still has a running worst case, running time of O(n^2) because often series of swaps required for each insertion.

In other words, applying Binary Search to calculate the position of the data to be inserted doesn’t reduce the time complexity of insertion sort. This is because insertion of a data at an appropriate position involves two steps:

  1. Calculate the position.
  2. Shift the data from the position calculated in Step 1 to create a gap where the data will be inserted.

Using Binary Search reduces the time complexity in Step 1 from O(n) to O(log n). But, the time complexity in Step 2 still remains O(n). So, the overall complexity remains O(n^2).

More specifically, for each insertion, we use Binary Search for comparisons and finding the position, which takes O(log n). The number of movements is O(n). Hence, the complexity is O(n + log n) = O(n). On top of that, we will have to do this n times for n insertions. Therefore, the overall complexity remains O(n^2).

Code Snippet

Insertion Sort in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>

void insertionSort(std::vector<int>& arr){
    int n = arr.size();
    for(int i = 1; i < n; i++){
        int key = arr[i];
        int j = i - 1;

        // move elements of arr[0..i-1], that greater than key,
        // to one position ahead of their current position
        while(j >= 0 && arr[j] > key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}
Insertion Sort using C++ STL
1
2
3
4
5
6
7
8
9
10
11
12
#include <vector>

void insertionSort(std::vector<int>& arr){
    for(auto it = arr.begin(); it != arr.end(); it++){
        // searching the upper bound
        // the first element greater than *it from beginning
        auto const insertionPoint = std::upper_bound(arr.begin(), it, *it);

        // shifting the unsorted part
        std::rotate(insertionPoint, it, it+1);
    }
}
Binary Insertion Sort in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <vector>

void binarySearch(std::vector<int>& arr, int key, int low, int high){
    if(high <= low)
        return (key > arr[low] ? (low + 1) : low);

    // int mid = (low + high) / 2;  // may have overflow
    int mid = low + (high - low) / 2;  // avoid overflow

    if(key == arr[mid])
        return (mid + 1);

    if(key > arr[mid])
        return binarySearch(arr, key, mid+1, high);

    if(key < arr[mid])
        return binarySearch(arr, key, low, mid-1);
}

void insertionSort(std::vector<int> arr){
    int n = arr.size();
    for(int i = 1; i < n; i++){
        int key = arr[i];
        int j = i - 1;

        // find location where selected should be inserted
        int location = binarySearch(arr, key, 0, j);

        while(j >= location){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

Properties

Insertion sort runs in O(n) time in its best case and runs in o(n^2) in its worst and average cases.

Time Complexity:

  • Best Case: O(n)
  • Worst Case: O(n^2)

Auxiliary Space: O(1)
Algorithmic Paradigm: Incremental Approach
Sorting in Place: Yes
Stable: Yes

Boundary Case

Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Merge Sort

Reference: https://www.geeksforgeeks.org/merge-sort/

Similar to Quick Sort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Merge Sort is useful for sorting linked list in O(n log n) time. In the case of linked lists, the case is different mainly due to the difference in memory allocation of arrays and linked list. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike arrays, int the linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore, merge operation of merge sort can be implemented without extra space for linked list.

In arrays, we can do random access as elements are contiguous in memory. Unlike arrays, we cannot do random access in the linked list. Quick Sort requires a lot of this kind of access. In linked list, to access i-th index, we have to traverse each and every node from the head to i-th node as we don’t have a continuous block of memory. Therefore, the overhead increases for Quick Sort. Merge Sort accesses data sequentially and the need of random access is low.

Logic of Merge Sort

Pseudo Code
1
2
3
4
5
6
7
8
9
10
11
merge(arrp[], l, m, r)
mergeSort(arr[], l, r)
If r > l
    1. Find the middle point to divide the array into two halves:
       middle m = (l+r)/2 or m = l + (r-l) / 2
    2. Call mergeSort for first half:
       Call mergeSort(arr, l, m)
    3. Call mergeSort for second half:
       Call mergeSort(arr, m+1, r)
    4. Merge the two halves sorted in step 2 and 3:
       Call merge(arr, l, m, r)

Code Snippet

Recursive Version of MergeSort in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <vector>

// merges two subarrys of arr[]
// first subarray is arr[l..m]
// second subarray is arr[m+1..r]
void merge(std::vector<int>& arr, int l, int m, int r){
    int n1 = m - l + 1;
    int n2 = r - m;  // r-(m+1)+1 = r-m
    std::vector<int> L(n1), R(n2);  // temp arrays

    // copy data to temp arrays
    for(int i = 0; i < n1; i++)
        L[i] = arr[l+i]

    for(int j = 0; j < n2; j++)
        R[j] = arr[m+1+j]

    // merge the temp arrays back into arr[l..r]
    int i = 0, j = 0, k = l;
    while(i < n1 && j < n2){
        if(L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    // copy the remaining elements of L[] and R[], if there are any
    while(i < n1)
        arr[k++] = L[i++];

    while(j < n2)
        arr[k++] = R[j++];
}

void mergeSort(std::vector<int> &arr, int l, int r){
    if(l < r){
        // same as (l+r)/2, but avoids overflow for large l and h
        int m = l + (r - l) / 2;

        // split into first and second halves, then sort and finally merge
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

Properties

Time Complexity: O(n log n) in all 3 cases (worst, average, and best)
Auxiliary Space: O(n)
Algorithm Paradigm: Divide and Conquer
Sorting in Place: No in a typical implementation
Stable: Yes

Merge Sort for Linked List

Merge Sort is often preferred for sorting a linked list. The slow random access performance of a linked list makes some other algorithms, such as Quick Sort, perform poorly, and others, such as Heap Sort, completely impossible.

Logic of Merge Sort for Linked List

Pseudo Code
1
2
3
4
5
6
7
8
9
10
mergeSort(headRef)
1. If the head is NULL or there is only one element in the linked list
   then return.
2. Else, divide the linked list into two halves.
   frontBackSplit(head, &a, &b);  // a and b are two halves
3. Sort the two halves a and b.
   mergeSort(a);
   mergeSort(b);
4. Sort and merge a and b, using merge(), and update the head pointer using headRef.
   *headRef = merge(a, b);

Code Snippet

Merge Sort for Linked List (Recursive Method)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// linked list node
struct Node {
    int data;
    Node *next;
    Node(int x) : data(x), next(NULL) {}
};

Node* merge(Node* a, Node* b){
    Node dummyHead(0);  // to avoid potential memory leak
    Node *tailNode = &dummyHead;

    // base case
    if(!a)
        return b;

    if(!b)
        return a;

    // pick either a or b
    if(a->val < b->val){
        tailNode->next = a;
        tailNode = tailNode->next;
        tailNode->next = recursive(a->next, b);
    }
    else{
        tailNode->next = b;
        tailNode = tailNode->next;
        tailNode->next = recursive(a, b->next);
    }

    return dummyHead.next;
}

void frontBackSplit(Node* currHead, Node** frontHead, Node** backHead){
    Node *slow, *fast;
    slow = currHead;
    fast = currHead->next;

    while(fast != NULL){
        fast = fast->next;
        if(fast != NULL){
            slow = slow->next;
            fast = fast->next;
        }
    }

    // slow should be before the midpoint in the list
    *frontHead = currHead;
    *backHead = slow->next;

    slow->next = NULL;
}

void mergeSort(Node** headNode){
    Node *head = headNode;
    Node *a, *b;

    // base case
    if(head == NULL || head->next == NULL)
        return;

    // split the list into two halves, a and b
    frontBackSplit(head, &a, &b);

    // recursively split each sublist
    mergeSort(&a);
    mergeSort(&b);

    // sort and merge the two list
    *headNode = merge(a, b);
}

Heap Sort

Reference: https://www.geeksforgeeks.org/heap-sort/

Heap Sort is a comparison based sorting technique based on Binary Heap data struture. It is similar to Selection Sort where we first find the maximum element and place the maximum element at the end. Repeat the same process for remaining element.

What is Binary Heap

A complete Binary Tree is a Binary Tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

A Binary Heap is a Complete Binary Tree where items are stored in a special order, such that value in a parent node is greater (or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by Binary Tree or array.

Why array based representation for Binary Heap

Since a Binary Heap is a Complete Binary Tree, it can be easily represented as array and array based representation is space efficient. If the parent node is stored at index i, the left child can be calculated by 2 * i + 1 and right child by 2 * i + 2, assuming the indexing starts at 0.

Heap Sort Algorithm for Sorting in Increasing Order

  1. Build a max heap from the input data.
  2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
  3. Repeat above steps while size of heap is greater than 1.

How to Build the Heap

Heapify procedure can be applied to a node only if its children nodes are heapified. So, the heapification must be performed in the bottom up order.

Applications of Heap Sort

Heap Sort algorithm has limited uses because Quick Sort and Merge Sort are better in practice. Nevertheless, the Heap data structure itself is enormously used.

Code Snippet

Properties

Time Complexity: O(n log n)
Time complexity of heapify is O(log n).
Time complexity of createAndBuildHeap() is O(n).

Heap Sort is an in-place algorithm

Its typical implementation is not stable, but can be made stable.

Quick Sort

Reference: https://www.geeksforgeeks.org/quick-sort/

Similar to Merge Sort, Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the giving array around the picked pivot. There are many different versions of Quick Sort that pick pivot in different ways.

  1. Always pick the first element as pivot.
  2. Always pick the last element as pivot (implemented below).
  3. Pick a random element as pivot.
  4. Pick median as pivot.

The key process in Quick Sort is partition(). Target of partition is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Pseudo Code for Recursive quickSort Function

Pseudo Code for quickSort function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// low -> Starting index
// high -> Ending index
quickSort(arr[], low, high)
{
    if (low < high)
    {
        // pi is partitioning index
        // arr[pi] is now at right place
        pi = partition(arr, low, high);

        quickSort(arr, low, pi-1);   // before pi
        quickSort(arr, pi+1, high);  // after pi
    }
}

Partition Algorithm

There can be many ways to do partition, following pseudo code adopts the method given in CLRS book. The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) element as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise, we ignore current element.

Pseudo Code for Partition function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// This function takes last element as pivot,
// places the pivot element at its correct position in sorted array,
// and places all smaller (smaller than pivot) to left of pivot,
// and all greater elements to right of pivot
partition(arr[], low, high)
{
    // pivot (element to be placed at right position)
    pivot = arr[high];

    i = low;  // initial index of smallest element

    for(j = low; j < high; j++)
    {
        // if current element is smaller than the pivot
        if(arr[j] < pivot)
        {
            swap arr[i] and arr[j];
            i++;
        }
    }
    swap arr[i] and arr[high];
    return i;
}

When does the Worst Case of Quick Sort Occur

The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases:

  1. Array is already sorted in the same order.
  2. Array is already sorted in reverse order.
  3. All elements are same (especially the case of 1 and 2)

Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition, or (especially for longer partitions) choosing the median of the first, middle, and last element of the partition for the pivot. With these modifications, the worst case of Quick Sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.

Why QuickSort is Preferred over MergeSort for Sorting Arrays

Quick Sort in its general form is an in-place (i.e. it doesn’t require any extra storage) whereas Merge Sort requires O(n) extra storage, n denoting the array size, which may be quite expensive.

Allocating and de-allocating the extra space used by Merge Sort increases the running time of the algorithm. Comparing average complexity, we find that both type of sorts have O(n log n) average complexity, but the constants differ. For arrays, Merge Sort loses due to the use of extra O(n) storage space.

Most Practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of O(n log n). The worst case is possible in randomized version also, but worst case doesn’t occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice.

Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.

Quick Sort is also tail recursive, therefore tail call optimizations is done.

Why MergeSort is Preferred over QuickSort for Linked Lists

In case of linked lists, the case is different mainly due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike array, in linked list, we can insert item in the middle in O(1) time and O(1) extra space. Therefore, merge operation of Merge Sort can be implemented without extra space for linked lists.

In arrays, we can do random access as elements are continuous in memory. Let us say, we have an integer (4-byte) array A and let the address of A[0] be x, then to access A[i], we can directly access the memory at (x + i*4). Unlike arrays, we cannot do random access in linked list. Quick Sort requires a lot of this kind of access. In linked list, to access i-th index, we have to travel each and every node from the head to i-th node, as we don’t have continuous block of memory. Therefore, the overhead increases for Quick Sort. Merge Sort accesses data sequentially and the need of random access is low.

Code Snippet

Quick Sort in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <vector>

// take the last element as pivot
// place pivot element at correct position in sorted array
// all elements smaller than pivot to the left of pivot
// all elements greater than pivot to the right of pivot
// using Lomuto partition scheme
int partition(std::vector<int>& vec, int l, int r){
    int pivot = vec[r];
    int i = l;  // initial index

    for(int j = l; j < r; j++){
        if(vec[j] < pivot)
            std::swap(vec[i++], vec[j]);  // increment index i, then swap
    }
    std::swap(vec[i], vec[r]);

    return i;
}

// l -> starting index
// r -> ending index
void quickSort(std::vector<int>& vec, int l, int r){
    if(l < r){
        // pi is partition index
        int pi = partition(vec, l, r);   // pick the last element as pivot
        // vec[pi] is now at right place

        quickSort(vec, l, pi-1);  // sort elements befor pi
        quickSort(vec, pi+1, r);  // sort elements after pi
    }
}

Properties

The time taken by Quick Sort depends upon the input array and partition strategy.

  • Worst Case: The worst case occurs when the partition process always picks greatest or smallest element as pivot. If we consider above partition strategy where last element is always picked as pivot, the worst case would occur when the array is already sorted in increasing or decreasing order. The recurrence for worst case is O(n^2).
  • Best Case: The best case occurs when the partition process always picks the middle element as pivot. The recurrence for best case is O(n log n).
  • Average Case: To do average case analysis, we need to consider all possible permutation of array and calculate time taken by every permutation which does not look easy. We can get an idea of average case by considering the case when partition puts O(n/9) elements in one set and O(9n/10) elements in other set. The recurrence is also O(n log n).

Although the worst case time complexity of Quick Sort is O(n^2), which is more than many other sorting algorithm, like Merge Sort and Heap Sort, but Quick Sort is faster in practice, because its inner loop can be efficiently implemented on most architectures, and in most real-world data. Quick Sort can be implemented in different ways by changing the choice of pivot, so that the worst case rarely occurs for a given type of data. However, Merge Sort is generally considered better when data is huge and stored in external storage.

Is Quick Sort Stable
The default implementation is not stable. However, any sorting algorithm can be made stable by considering indexes as comparison parameter.

Is Quick Sort In-Place
As per the broad definition of in-place algorithm, it qualifies as an in-place sorting algorithm as it uses extra space only for storing recursive function calls, but not for manipulating the input.

How to Optimize QuickSort So That It Takes O(log n) Extra Space in Worst Case

Tail Call Optimization

In Quick Sort, partition function is in-place, but we need extra space for recursive function calls. A simple implementation of Quick Sort makes two calls to itself and in worst case requires O(n) space on function call stack.

The worst case happens when the selected pivot always divides the array such that one part has 0 element and other part has (n-1) elements.

Can we reduce the auxiliary space for function call stack?
We can limit the auxiliary space to O(log n). The idea is based on tail call elimination. We can convert the code so that it makes only one recursive call in Quick Sort.

Apply Tail Call Elimination to Quick Sort
1
2
3
4
5
6
7
8
// space complexity: O(n)
void quickSortRecursive_optimization(std::vector<int>& vec, int low, int high){
    while(low < high){
          int pi = partition(vec, low, high);
          quickSortRecursive_optimization(vec, low, pi-1);
          low = pi + 1;
    }
}

Although we have reduced number of recursive calls, the above code can still use O(n) auxiliary space in worst case. In worst case, it is possible that array is divided in a way that the first part always has (n-1) elements. For example, this may happen when the last element is chosen as pivot and array is sorted in decreasing order.

We can optimize the above code to make a recursive call only for the smaller part after partition.

If the left part becomes smaller, then we make recursive call for left part. Else, for the right part. In worst case (for space), when both parts are of equal sizes in all recursive calls, we use O(log n) extra space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// space complexity: O(log n)
void quickSortRecursive_furtherOptimization(std::vector<int>& vec, int l, int r){
    while(l < r){
          int pi = partition(vec, l, r);

          if((pi - l) < (r - pi)){
              quickSortRecursive_furtherOptimization(vec, l, pi-1);
              l = pi + 1;
          }
          else{
              quickSortRecursive_furtherOptimization(vec, pi+1, r);
              r = pi - 1;
          }
    }
}

Quick Sort is also tail recursive.

Note that Merge Sort is NOT tail recursive, this is also one of the reasons why Quick Sort performs better.

Hoare’s Partition Scheme

Hoare’s partition scheme works by initializing two indexes that start at two ends, the two indexes move toward each other until an inversion is found. (A smaller value on left side and greater value on right side.) When an inversion is found, two values are swapped and process is repeated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// take the first element as pivot
// place pivot element at correct position in sorted array
// all elements smaller than pivot to the left of pivot
// all elements greater than pivot to the right of pivot
// using Hoare's partition scheme
int partition(std::vector<int>& vec, int l, int r){
    int pivot = vec[l];
    int i = l, j = r;  // initial index

    while(i < j){
        // find leftmost element greater than or equal to pivot
        while(vec[i] < pivot)
            i++;

        // find rightmost element smaller than or equal to pivot
        while(vec[j] > pivot)
            j--;

        if(i < j)
            std::swap(vec[i], vec[j]);
    }

    return j;
}

Random Pivoting

In Quick Sort, we first partition the array in place such that all elements to the left of the pivot element are smaller, and all elements to the right of the pivot are greater than the pivot element. Then, we recursively call the same procedure for left and right subarrays.

Unlike Merge Sort, we don’t need to merge the two sorted arrays. Thus, Quick Sort requires lesser auxiliary space than Merge Sort, which is why it is often preferred to Merge Sort. Using a randomly generated pivot, we can further improve the time complexity of Quick Sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// pick a random index for randomized partition
void pickRandomIndex(std::vector<int>& vec, int l, int r){
    int ri = l + rand() % (r-l+1);  // choose a random index between [l, r]
    std::swap(vec[ri], vec[r]);     // swap the end element with element present at random index
}

void quickSortRecursive(std::vector<int>& vec, int l, int r){
    if(l < r){
        // pi is partition index
        pickRandomIndex(vec, l, r);      // pick a random index for randomized partition
        int pi = partition(vec, l, r);   // pick the last element as pivot
        // vec[pi] is now at right place

        quickSortRecursive(vec, l, pi-1);  // sort elements befor pi
        quickSortRecursive(vec, pi+1, r);  // sort elements after pi
    }
}

Counting Sort

Reference: https://www.geeksforgeeks.org/counting-sort/

Counting Sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then, doing some arithmetic to calculate the position of each object in the output sequence.

The problem with the above counting sort was that we could not sort the elements if we have negative numbers in it. It is because there are no negative array indices. So, what we do is to find the minimum element and store count of that minimum element at zero index.

Points to be noted:

  1. Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. Consider the situation where the input sequence is between range 1 to 10k and the data is 10, 5, 10k, 5k.

  2. It is not a comparison based sorting. Its run time complexity is O(n) with space proportional to the range of data.

  3. It is often used as a sub-routine to another sorting algorithm, like radix sort.

  4. Counting sort uses a partial hashing to count the occurrence of the data object in O(1).

  5. Counting sort can be extended to work for negative inputs also.

Code Snippet

Properties

Time Complexity: O(n+k), where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)