Sorting algorithms #sorting

README.md

How to build it

Clone it and cd into the repo's folder, then run:

$ make
...
...
g++ -Wall --std=c++11 test.o selection_sort.o insertion_sort.o bubble_sort.o merge_sort.o quick_sort.o -o run_test
$ ./run_test
Source:                 13 13 12 4 13 2 6 10 1 6 18 15 20 0
Selection sort:         0 1 2 4 6 6 10 12 13 13 13 15 18 20
Insertion sort:         0 1 2 4 6 6 10 12 13 13 13 15 18 20
Bubble sort:            0 1 2 4 6 6 10 12 13 13 13 15 18 20
Merge sort:             0 1 2 4 6 6 10 12 13 13 13 15 18 20
Quick sort:             0 1 2 4 6 6 10 12 13 13 13 15 18 20
$ make clean
rm *.o run_test

TODO

• Apply insertion sort in quick sort to speed up
• Add a summary/comparison table
• Improve the implementation after reviewing algorithm books

bubble_sort.cpp

#include <algorithm>  // for std::swap
#include <cassert>
#include "sorting.h"

/*
 * Bubble sort: O(n^2)
 */
void bubbleSort(int list[], unsigned int length)
{
  assert(length);

  // <--  unsorted  -->|<--  sorted  -->
  // +---+---+---------+---+-------+---+
  // | 0 | 1 | ....... | m | ..... | M |
  // +---+---+---------+---+---+---+---+
  //                     ^           ^
  //              current min        Max
  for (unsigned int i = 0 ; i < length - 1 ; ++i) {
    for (unsigned int j = 0 ; j < length - 1 - i ; ++j) {
      if (list[j] > list[j+1]) {
        std::swap(list[j], list[j+1]);
      }
    }
  }
}

heap_sort.cpp

#include <algorithm>  // for std::swap
#include <cassert>
#include "sorting.h"

// Tree structrue:
//            0
//          /   \
//        1      2
//       / \    / \
//      3  4   5  6
//     .. ..  ..  ..
unsigned int getParent(unsigned int index)
{
  // (index - 1) / 2 will be a very large number when index is 0
  // since it's unsigned.
  unsigned int p = index ? (index - 1) / 2 : 0; // floor((index - 1)/2).
  assert(p >= 0 && p <= index); // prevent overflow.
  return p;
}

unsigned int getLeftChild(unsigned int index)
{
  unsigned int c = index * 2 + 1;
  assert(c > index); // prevent overflow.
  return c;
}

unsigned int getRightChild(unsigned int index)
{
  unsigned int c = index * 2 + 2;
  assert(c > index); // prevent overflow.
  return c;
}

/*
// Suppose we have a max-heap tree whose root is s.
// If we insert x into this heap tree(as tree's last leaf)
//     ^          s
//   h |       /    \
//   e |      /      \
//   a |     l       r    where l = s*2 + 1, r = l + 1 = s*2 + 2, and
//   p |    / \     / \         l's and r's subtrees are all heap tree.
//     |   .   .   .   .
//     v  . . . . . . . x <- Move this to make sure list[s:e] is heap structure.
void siftUp(int list[], unsigned int start, unsigned int end)
{
  unsigned int child = end;
  while (child > start) { // while (getParent(child) >= start) {
    unsigned int parent = getParent(child);
    if (list[parent] >= list[child]) {
      return;
    }
    // Swap parent node with child node when list[parent] < list[child
    std::swap(list[parent], list[child]);
    child = parent;
  }
}

// In-place sort list in heap order.
void heapify(int list [], unsigned int length)
{
  // |<--           non-heap          -->|
  // +---+---------------------------+---+
  // | 0 | ......................... | e |
  // +---+---------------------------+---+
  for (unsigned int i = 0 ; i < length ; ++i) {
    // |<-- heap -->|<--    non-heap    -->|
    // +---+--------+---+--------------+---+
    // | 0 | ...... | i | ............ | e |
    // +---+--------+---+--------------+---+
    siftUp(list, 0, i);
    // |<--   heap   -->|<--  non-heap  -->|
    // +---+--------+---+--------------+---+
    // | 0 | ...... | i | ............ | e |
    // +---+--------+---+--------------+---+
  }
  // |<--             heap            -->|
  // +---+---------------------------+---+
  // | 0 | ......................... | e |
  // +---+---------------------------+---+
}
*/

// Suppose we have a max-heap tree.
// If the root is removed and inserted a new value, we need to restructure
// it into a heap tree.
//
//               s <- Move this to make sure list[s:e] is heap structure.
//             /  \
//  h  ^     l     r    where l = s*2 + 1, r = l + 1 = s*2 + 2, and
//  e  |    / \   / \         l's and r's subtrees are all heap tree.
//  a  |   .  .  .  .
//  p  v   .  .  .  .
void siftDown(int list[], unsigned int start, unsigned int end)
{
  assert(start >= 0 && end >= 0);
  unsigned int node = start;

  // While the root still has at least one child.
  while (getLeftChild(node) <= end) {
    unsigned int max = node;
    unsigned int leftChild = getLeftChild(node);
    unsigned int rightChild = getRightChild(node);
    assert(leftChild + 1 == rightChild);

    // Get the larger one between root and its left child.
    if (list[leftChild] > list[max]) {
      max = leftChild;
    }

    // If root has a right child, then find the largest one among
    // root, left child, and right child.
    if (rightChild <= end && list[rightChild] > list[max]) {
      max = rightChild;
    }

    // ******************************************************
    // Now, max = Max(root, left child) or
    //            Max(Max(root, left child), right child).
    // ******************************************************

    // If root is already larger than all its children,
    // it implies that the tree is already structured!
    if (max == node) {
      return;
    }

    // Otherwise, we need to swap max with root, as new parent,
    // so the new root(max) is definitely larger than all its children.
    std::swap(list[max], list[node]);

    // Repeat the procedures from the swapped node.
    node = max;
  }
}

/*
// Calculate one path, from start to the returned leaf, that
// all the nodes from on the path are larger than their siblings.
unsigned int leafSearch(int list[], unsigned int start, unsigned int end)
{
  unsigned int node = start;

  // While the node still has at least one child.
  while(getLeftChild(node) <= end) {
    unsigned int leftChild = getLeftChild(node);
    unsigned int rightChild = getRightChild(node);
    assert(leftChild + 1 == rightChild);

    // Pick the larger child as the new node.
    node = (rightChild <= end && list[rightChild] > list[leftChild]) ?
      rightChild : leftChild;
  }

  // Now we get a leaf node.
  return node;
}

void siftDown(int list[], unsigned int start, unsigned int end)
{
  unsigned int anchor = leafSearch(list, start, end);
  // All the nodes from on the path from start to anchor
  // are larger than their siblings.

  // We find the first node that is greater than start.
  while (list[anchor] < list[start]) {
    anchor = getParent(anchor);
  }
  // path:
  //             start
  //              /
  //             q      // All the nodes from p
  //            /       // to q are larger than
  //          ...       // start's value.
  //          /
  //         p <- The first node whose value > start's value
  //        /
  //      ...
  //      /
  //    leaf <- the leaf returned from leafSearch


  // Now we should move upward all the nodes on the path and
  // insert the start's value(list[start]) to the anchor we found,
  // so we can keep the heap structure.
  //
  //
  //             start                      q
  //  m           /                        /
  //  o  ^       q                       ...
  //  v  |      /       siftDown         /
  //  e  |    ...         ===>          p
  //     |    /                        /
  //  u  v   p  <- insert           start
  //  p     /      start's value     /
  //      ...      here            ...
  //      /                        /
  //    leaf                     leaf
  //
  // The reason why we can just move up all the nodes to sort list
  // in heap order is because all the nodes on the path are larger
  // than their siblings. Thus, they must be larger than all their
  // children after being moved up.
  int temp = list[anchor];
  list[anchor] = list[start];

  while (anchor > start) {
    unsigned int parent = getParent(anchor);
    std::swap(temp, list[parent]);
    anchor = parent;
  }
}
*/

/*
// In-place sort list in heap order.
void heapify(int list [], unsigned int length)
{
  // |<--             non-heap            -->|
  // +---+-------------------------------+---+
  // | 0 | ............................. | e |
  // +---+-------------------------------+---+
  for (int start = length - 1 ; start >= 0 ; --start) {
    // |<-- non-heap -->|<--      heap      -->|
    // +---+--------+---+------------------+---+
    // | 0 | ...... | s | ................ | e |
    // +---+--------+---+------------------+---+
    siftDown(list, start, length - 1);
    // |<-- non-heap -->|<--      heap      -->|
    // +---+------------+---+--------------+---+
    // | 0 | .......... | s | ............ | e |
    // +---+------------+---+--------------+---+
  }
  // |<--               heap              -->|
  // +---+-------------------------------+---+
  // | 0 | ............................. | e |
  // +---+-------------------------------+---+
}
*/

// In-place sort list in heap order.
void heapify(int list [], unsigned int length)
{
  // |<--             non-heap            -->|
  // +---+-------------------------------+---+
  // | 0 | ............................. | l |
  // +---+-------------------------------+---+
  //                                       ^
  //                                   last leaf
  unsigned int lastLeaf = length - 1;
  // All leaf nodes are naturally heap structures, so we can just build heap
  // from the last non-leaf node(last node who has children).
  for (int start = getParent(lastLeaf) ; start >= 0 ; --start) {
    // |<-- non-heap -->|<--      heap      -->|
    // +---+--------+---+------------------+---+
    // | 0 | ...... | s | ................ | l |
    // +---+--------+---+------------------+---+
    siftDown(list, start, length - 1); // heap(list[s], list[s+1:l])
    // |<-- non-heap -->|<--      heap      -->|
    // +---+------------+---+--------------+---+
    // | 0 | .......... | s | ............ | l |
    // +---+------------+---+--------------+---+
  }
  // |<--               heap              -->|
  // +---+-------------------------------+---+
  // | 0 | ............................. | l |
  // +---+-------------------------------+---+
}

/*
 * Heap sort: O(n * log(n))
 */
void heapSort(int list [], unsigned int length)
{
  // Build heap tree in list:
  // |<--               heap              -->|
  // |<--             unsorted            -->|
  // +---+-------------------------------+---+
  // | 0 | ............................. | e |
  // +---+-------------------------------+---+
  heapify(list, length);

  int end = length - 1;
  while (end > 0) {
    // |<--     heap     -->|
    // |<--   unsorted   -->|<--   sorted   -->|
    // +---+------------+---+------------------+
    // | 0 | .......... | e | ................ |
    // +---+------------+---+------------------+
    //   ^                ^
    // largest     end of the unsorted part
    std::swap(list[0], list[end]);
    // |<-- non-heap -->|
    // |<-- unsorted -->|<--     sorted     -->|
    // +---+------------+---+------------------+
    // | 0 | .......... | e | ................ |
    // +---+------------+---+------------------+

    end = end - 1;
    // |<-- non-heap -->|
    // |<-- unsorted -->|<--     sorted     -->|
    // +---+--------+---+----------------------+
    // | 0 | .......| e | .................... |
    // +---+--------+---+----------------------+

    siftDown(list, 0, end);
    // |<--   heap   -->|
    // |<-- unsorted -->|<--     sorted     -->|
    // +---+--------+---+----------------------+
    // | 0 | .......| e | .................... |
    // +---+--------+---+----------------------+
  }
}

insertion_sort.cpp

#include <algorithm>  // for std::swap
#include <cassert>
#include "sorting.h"

/*
 * Insertion sort: O(n^2)
 */
void insertionSort(int list[], unsigned int length)
{
  assert(length);

  // <-- sorted -->|<-- unsorted -->
  // +---+-----+---+---------------+
  // | 0 | ... | t | ............  |
  // +---+-----+---+---------------+
  //             ^
  //       tail is the index of last item of sorted list.
  for (unsigned int tail = 1 ; tail < length; ++tail) { // list[0] is sorted!
    for (unsigned int j = tail; j > 0 && list[j - 1] > list[j] ; --j) {
      std::swap(list[j], list[j - 1]);
    }
  }
}

// void insertionSort(int list[], unsigned int length)
// {
//   assert(length);
//
//   for (unsigned int tail = 1 ; tail < length; ++tail) {
//     int current = list[tail];
//     unsigned int j = tail;
//     while(j > 0 && list[j-1] > current) {
//       list[j] = list[j - 1];
//       --j;
//     }
//     list[j] = current;
//   }
// }

makefile

CC=g++
CFLAGS=-Wall --std=c++11

SOURCES=test.cpp\
        selection_sort.cpp\
        insertion_sort.cpp\
        bubble_sort.cpp\
        merge_sort.cpp\
        quick_sort.cpp\
        heap_sort.cpp
OBJECTS=$(SOURCES:.cpp=.o)

# Name of the executable program
EXECUTABLE=run_test

all: $(EXECUTABLE)

# $@ is same as $(EXECUTABLE)
$(EXECUTABLE): $(OBJECTS)
	$(CC) $(CFLAGS) $(OBJECTS) -o $@

# ".cpp.o" is a suffix rule telling make how to turn file.cpp into file.o
# for an arbitrary file.
#
# $< is an automatic variable referencing the source file,
# file.cpp in the case of the suffix rule.
#
# $@ is an automatic variable referencing the target file, file.o.
# file.o in the case of the suffix rule.
#
# Use -c to generatethe .o file
.cpp.o:
	$(CC) -c $(CFLAGS) $< -o $@

clean:
	rm *.o $(EXECUTABLE)

merge_sort.cpp

#include <algorithm>  // for std::min, std::swap
#include <cassert>
#include <cstring>    // for memcpy
#include "sorting.h"

/*
 * Merge sort: O(n * log(n))
 */
// Basic merge: O(n)
// The following is the most straightforward way to merge two sorted array.
// However, it allocates extra memory for sorted results in every recursion.
void merge(int list[],
           unsigned int left,
           unsigned int division,
           unsigned int right)
{
  assert(left <= right);
  //      |<-- sorted -->|<-- sorted -->|
  // -----+---+------+---+---+------+---+-----
  //  ... | l | .... | m | n | .... | r | ...
  // -----+---+------+---+---+------+---+-----
  //        ^          ^   ^          ^
  //      left       div  div+1    right
  unsigned int i = left;
  unsigned int j = division + 1;
  const unsigned int size = right - left + 1;
  int array[size];

  // When left <= i <= div and div + 1 <= j <= right:
  // Compare list[i] and list[j], if list[i] < list[j], then copy list[i] into
  // the new array and let i = i + 1. Otherwise, copy list[j] into the new array
  // and let j = j + 1. If i > div, it means list[left...div] is all compared
  // and already copied, so we just need to put the rest list[j...right] into
  // the array. In the same way, if j > right, then put the rest list[i...div]
  // into the array.
  unsigned int k = 0;
  for (k = 0 ; k < size; ++k) {
    array[k] = (j > right || (i <= division && list[i] < list[j])) ? list[i++] : list[j++];
  }

  // while (i <= division && j <= right) {
  //   array[k++] = (list[i] < list[j]) ? list[i++] : list[j++];
  //   // if (list[i] < list[j]) {
  //   //   array[k] = list[i];
  //   //   ++i;
  //   // } else {
  //   //   array[k] = list[j];
  //   //   ++j;
  //   // }
  //   // ++k;
  // }
  //
  // // In this case, j > right, so we put the rest list[i...div] into the array.
  // while (i <= division) {
  //   array[k++] = list[i++];
  //   // array[k] = list[i];
  //   // ++i;
  //   // ++k;
  // }
  //
  // // in this case, i > div, so we put the rest list[j...right] into the array.
  // while (j <= right) {
  //   array[k++] = list[j++];
  //   // array[k] = list[j];
  //   // ++j;
  //   // ++k;
  // }

  assert(k == size);
  assert(i == division + 1);
  assert(j == right + 1);

  // Overwrite list[left...right] by the new sorted array.
  for (k = 0 ; k < size ; ++k) {
    list[left + k] = array[k];
  }
  assert(left + k == right + 1);
}

// Append ∞ as the last sentinel element to the both ordered arrays for merging.
void mergeWithSentinel(int list[], unsigned int left, unsigned int division, unsigned int right)
{
  assert(left <= right);
  //      |<-- sorted -->|<-- sorted -->|
  // -----+---+------+---+---+------+---+-----
  //  ... | l | .... | m | n | .... | r | ...
  // -----+---+------+---+---+------+---+-----
  //        ^          ^   ^          ^
  //      left       div  div+1    right
  //      |<---  A'  --->|<---  B'  --->|

  // Allocate list A = A' ∪ [INFINITY] and list B = B' ∪ [INFINITY]
  const static int INFINITY = ((unsigned int)(-1) >> 1);
  const unsigned int sizeA = division - left + 2; // (division - left + 1) + 1
  const unsigned int sizeB = right - division + 1; // (right - (division + 1) + 1) + 1
  int *A = new int[sizeA]; // 1 is for [ INFINITY ]
  int *B = new int[sizeB];
  // Copy elements from list[left...division] to A'[0...(sizeA - 2)].
  memcpy((void*)A, (void*)(list + left), sizeof(int) * (sizeA - 1));
  // Copy elements from list[(division + 1)...right] to B'[0...(sizeB - 2)].
  memcpy((void*)B, (void*)(list + division + 1), sizeof(int) * (sizeB - 1));
  // Set the last elements of A and B to INFINITY.
  A[sizeA - 1] = B[sizeB - 1] = INFINITY;
  // Move the sorted elements of A and B to list[left...right].
  unsigned int i, j;
  for (i = j = 0 ; left <= right ; ++left) {
    list[left] = A[i] < B[j] ? A[i++] : B[j++];
  }
  free(A);
  free(B);
}

// The following method demonstrates a in-place version of merge method.
// However, it downgrades mergesort overall performance to quadratic O(n^2)!
// Naive in-place merge: O(n^2)
void naiveInplaceMerge(int list[],
                       unsigned int left,
                       unsigned int division,
                       unsigned int right)
{
  assert(left <= right);
  //      |<-- sorted -->|<-- sorted -->|
  // -----+---+------+---+---+------+---+-----
  //  ... | l | .... | m | n | .... | r | ...
  // -----+---+------+---+---+------+---+-----
  //        ^          ^   ^          ^
  //      left       div  div+1    right
  unsigned int anchor = left;
  for (unsigned int i = division + 1 ; i <= right ; ++i) {
    for (unsigned int j = i ; j > anchor ; --j) { // Replace anchor with left is fine.
      // The following condition is definitely true and will be triggered.
      // list[division + k + 1] >= list[division + k] where k >= 1
      // is assertive because list[division + 1 .... right] is a sorted from
      // minimal item to maximal one.
      if (list[j] >= list[j-1]) {
        anchor = j;
        break;
      }
      std::swap(list[j], list[j-1]);
    }
  }
}

void topDownMergeSort(int list[], unsigned int left, unsigned int right)
{
  if (left >= right) {
    return;
  }

  const unsigned int middle = (left + right) / 2;
  topDownMergeSort(list, left, middle);
  topDownMergeSort(list, middle + 1, right);
  merge(list, left, middle, right);
  // mergeWithSentinel(list, left, middle, right);
  // naiveInplaceMerge(list, left, middle, right); // Slower!
}

void bottomUpMergeSort(int list[], unsigned int length)
{
  // <----------  l = 2^k + r  ---------->  where k, r are integers, k >= 0,
  // <-----  2^k  ----->|<-----  r  ----->  and 0 <= r < 2^k.
  // +---+---+---------+---+---------+---+
  // | 0 | 1 | ....... | n | ....... | m |
  // +---+---+---------+---+---------+---+
  //
  // l            k  r
  // 1 : 2^0 + 0  0  0
  // 2 : 2^1 + 0  1  0
  // 3 : 2^1 + 1  1  1
  // 4 : 2^2 + 0  2  0
  // 5 : 2^2 + 1  2  1
  // 6 : 2^2 + 2  2  2
  // 7 : 2^2 + 3  2  3
  // 8 : 2^3 + 0  3  0
  // 9 : 2^3 + 1  3  1
  // ...
  // ...
  //
  // When r = 0:  The length of list is powers of 2, denoted 2^k, so all the
  //              size of blocks for merging must be same. At the round (k+1),
  //              the size is 2^k, where k >= 0 is a integer.
  // When r != 0: We can consider there are extra 'r' elements added into the
  //              above list whose length is powers of 2.
  //              The extra 'r' elements will be merged when the block size is
  //              grown to 2^k, where k >= 0 and 0 < r < 2^k.
  //
  // Each round, the list is divided into blocks and then merged
  // from size 1, 2, 4, ... to lenght/2.
  for (unsigned int size = 1 ; size < length ; size *= 2) {
    // If i >= length - size, then the rest elements list[i .. length - 1]
    // is smaller than or equal to one block size, so there is nothing to be
    // merged. These rest elements will be merged when size = 2^k
    // and 2^(k-1) < length - 2^k < 2^k,.
    for (unsigned int i = 0 ; i < length - size ; i += 2 * size) {
      // Merge the adjacent two blocks.
      merge(list, i, i + size - 1, std::min(i + 2 * size - 1, length - 1));
      // mergeWithSentinel(list, i, i + size - 1, min(i + 2 * size - 1, length - 1));
      // naiveInplaceMerge(list, i, i + size - 1, min(i + 2 * size - 1, length - 1)); // Slower!

      // Uncomment below to check when the rest items will be merged.
      // if ((size/2 < length - size/2) && (length - size < size)) {
      //   std::cout << "List length: " << length << std::endl;
      //   std::cout << "Merge the last " << length - size <<
      //                " items when size is " << size << std::endl;
      //   assert(min(i + 2 * size - 1, length - 1) == length - 1);
      // }
    }
  }
}

void mergeSort(int list[], unsigned int length)
{
  assert(length);

  // topDownMergeSort(list, 0, length - 1);
  bottomUpMergeSort(list, length);
}

quick_sort.cpp

#include <algorithm>  // for std::swap
#include <cassert>
// #include <queue>
#include <stack>
#include "sorting.h"

/*
 * Quick sort: O(n * log(n))
 */
unsigned int partition(int list[], unsigned int left, unsigned int right)
{
  // The j is moved anyway. The i is moved if the element at i > p.
  // -----+---+---------------------------------+-------------+---+
  //  ... | l | ............................... | .. i,j<- .. | r |
  // -----+---+---------------------------------+-------------+---+
  //      | p |                                 | ... > p ....... |
  //
  // Stop moving i if the element at i <= p. j is moved anyway.
  // Make sure the next(right) element of i is > p.
  // -----+---+-------------------------+---+---+-------------+---+
  //  ... | l | ....................... | j | i | .. i,j<- .. | r |
  // -----+---+-------------------------+---+---+-------------+---+
  //      | p |                             |<=p| ... > p ....... |
  //
  // Swap elements at i and j when element j > p (before swapping).
  // -----+---+-----------+---+---+---------+---+-------------+---+
  //  ... | l | ......... |   | j | ....... | i | .. i,j<- .. | r |
  // -----+---+-----------+---+---+---------+---+-------------+---+
  //      | p |               | >p| ..<=p.. |<=p| ... > p ....... |
  //
  // Swap elements at i and j when element j > p (after swapping).
  // -----+---+-----------+---+---+---------+---+-------------+---+
  //  ... | l | ......... |   | j | ....... | i | .. i,j<- .. | r |
  // -----+---+-----------+---+---+---------+---+-------------+---+
  //      | p |               |<=p| ..<=p.. |> p| ... > p ....... |
  //
  // After swapping, move i. Remember that j is moved anyway.
  // The next(right) element of j must be <= p after first swapping.
  // -----+---+-----------+---+---+-----+---+---+-------------+---+
  //  ... | l | ......... | j |   | ... | i |   | .. i,j<- .. | r |
  // -----+---+-----------+---+---+---------+---+-------------+---+
  //      | p |               |<=p| ..<=p.. |> p| ... > p ....... |
  //
  // ...
  // ...
  // Swap elements at i and j again until element j > p
  // -----+---+-----+---+-----+---+-----+---+---+-------------+---+
  //  ... | l | ... | j | ... |   | ... | i |   | .. i,j<- .. | r |
  // -----+---+-----+---+-----+---+-----+---+---+-------------+---+
  //      | p |     | >p| ..<=p.. | ..<=p.. | ....... > p ....... |
  //
  // ...
  // ...
  // Stop moving j down to left:
  // -----+---+------------------+---+----------+-------------+---+
  //  ... | j | ................ | i |..........| .. i,j<- .. | r |
  // -----+---+------------------+---+----------+-------------+---+
  //      | p | ...... <=p ..... |<=p| .......... > p ........... |
  //
  // Swap elements at left and i:
  // -----+---+------------------+---+----------+-------------+---+
  //  ... | j | ................ | i |..........| .. i,j<- .. | r |
  // -----+---+------------------+---+----------+-------------+---+
  //      |<=p| ...... <=p ..... | p | .......... > p ........... |
  int& pivot = list[left];
  unsigned int i = right;
  for (unsigned int j = right; j >= left + 1 ; --j) {
    if (list[j] > pivot) {
      std::swap(list[j], list[i]);
      --i;
    }
  }
  std::swap(list[i], pivot);
  return i;

  // int& pivot = list[right];
  // unsigned int i = left; // Index of the place for swapping.
  // for (unsigned int j = left ; j <= right - 1 ; ++j) {
  //   if (list[j] <= pivot) {
  //     std::swap(list[i], list[j]);
  //     ++i;
  //   }
  // }
  // std::swap(list[i], pivot);
  // return i;
}

// -----+---+-----------+---+-----+---+----------+---+-----
//  ... | l | .. ->i .. | i | ... | j | .. j<- ..| r | ...
// -----+---+-----------+---+-----+---+----------+---+-----
//      | p | .. <=p .. | >p| ... |<=p| .... >p .... |
//      | .... <=p .... |
// 1. Keep movinj j to left til finding one element <= p or j = i
// 2. Keep moving i to right til finding one element > p or i = j
// 3. Swap i and j iteratively until j = i.
// 4. Finally, the p should be swapped with an element whose next is >p,
//    which is the element at j.
// unsigned int partition(int list[], unsigned int left, unsigned int right)
// {
//   assert(left <= right);
//   int& pivot = list[left];
//   unsigned int i = left;
//   unsigned int j = right;
//   while (i < j) {
//     // -----+---+-----------+------+----------+---+-----
//     //  ... | l | .. ->i .. | i, j | .. j<- ..| r | ...
//     // -----+---+-----------+------+----------+---+-----
//     //      | p | .. <=p .. |  >p  | .... >p .... |
//     // Consider the above case, if we move i before j, the p will be
//     // swapped with one element > p, and the list will be:
//     // | >p | .. <=p .. | p | .. >p .. |
//     // It's obviously wrong! The p should be swapped with an element whose next
//     // is > p and it is own value <= p, instead of the one whose value is > p.
//     if (list[j] > pivot) {
//       --j;
//     } else if (list[i] <= pivot) {
//       ++i;
//     } else {
//       std::swap(list[i], list[j]);
//     }
//   }
//   std::swap(list[i], pivot); // Currently, i = j.
//   return j;
// }

// -----+---+-----------+---+-----+---+----------+---+-----
//  ... | l | .. ->i .. | i | ... | j | .. j<- ..| r | ...
// -----+---+-----------+---+-----+---+----------+---+-----
//      | p | .. <=p .. | >p| ... |<=p| .... >p .... |
//      | .... <=p .... |
// 1. Keep moving i to right til finding one element > p
// 2. Keep movinj j to left til finding one element <= p
// 3. Swap i and j iteratively until j >= i.
// 4. Finally, the p should be swapped with an element whose next is >p,
//    which is the element at j.
// unsigned int partition(int list[], unsigned int left, unsigned int right)
// {
//   assert(left <= right);
//   int& pivot = list[left];
//   unsigned int i = left;
//   unsigned int j = right;
//   while (1) {
//     while(list[i] <= pivot && i < right) {
//       ++i;
//     }
//     while(list[j] > pivot && j > left) {
//       --j;
//     }
//     // Stop when j > i:
//     // -----+---+-----------+---+---+----------+---+-----
//     //  ... | l | .. ->i .. | j | i | .. j<- ..| r | ...
//     // -----+---+-----------+---+---+----------+---+-----
//     //      | p | .. <=p .. |<=p| >p| .... >p .... |
//     //
//     // Stop when i = j:
//     // -----+---+-----------+---------+-----
//     //  ... | l | .. ->i .. | i, j, r | ...
//     // -----+---+-----------+---------+-----
//     //      | p | .. <=p .. |   <=p   |
//     if (i >= j) {
//       break;
//     }
//     std::swap(list[i], list[j]);
//   }
//   std::swap(list[j], pivot);
//   return j;
// }

// Go through all list[left...right]: Pick the left most as the pivot.
// If the element is < pivot, then throw it into "lessequal" array. Otherwise,
// throw it into "greater" array. Finally, we return the concatenated array
// that is lessequal + [pivot] + greater.
// unsigned int partition(int list[], unsigned int left, unsigned int right)
// {
//   assert(left <= right);
//   int& pivot = list[left];
//   const unsigned int size = right - left + 1;
//
//   int lessequal[size];
//   unsigned int l = 0; // Size of the lessequal array.
//
//   int greater[size];
//   unsigned int g = 0; // Size of the greater array.
//
//   for (unsigned int i = left + 1 ; i <= right ; ++i) {
//     if (list[i] < pivot) {
//       lessequal[l] = list[i];
//       ++l;
//     } else {
//       greater[g] = list[i];
//       ++g;
//     }
//   }
//
//   lessequal[l] = pivot;
//   ++l;
//
//   assert(g + l == size);
//
//   // Overwrite list[left...right] by the lessequal and greater.
//   for (unsigned int i = left ; i <= right ; ++i) {
//     unsigned int k = i - left;
//     list[i] = (k < l) ? lessequal[k] : greater[k - l];
//   }
//   // unsigned int k = 0;
//   // for (unsigned int i = left ; i <= right ; ++i, ++k) {
//   //   list[i] = (k < l) ? lessequal[k] : greater[k - l];
//   // }
//   // assert(k == size && k == l + g);
//
//   return left + l - 1;
// }

void recursiveQuickSort(int list[], unsigned int left, unsigned int right)
{
  if (left >= right) {
    return;
  }

  // Partition the subarray list[left ... right] so that
  // list[left ... j-1] <= list[j] <= list[j+1 ... right]
  unsigned int pivot = partition(list, left, right); // Index of the pivot item.
  // Since the type of left and right is "unsigned", we need to prevent overflow
  // issues that pivot - 1 > pivot or pivot + 1 < pivot by checking pivot's range.
  // e.g., if pivot = 0, (signed)pivot - 1 = -1 = (unsigned)0xFF..F
  //       = max value of a unsigned int!
  recursiveQuickSort(list, left, (pivot == left) ? left : pivot - 1);
  recursiveQuickSort(list, (pivot == right) ? right : pivot + 1, right);

  // We could just use the following code if left and right both are
  // const (signed) int:
  // if (left >= right) {
  //   return;
  // }
  //
  // int pivot = partition(list, left, right); // Index of the pivot item.
  // recursiveQuickSort(list, left, pivot - 1);
  // recursiveQuickSort(list, pivot + 1, right);
  // It's more easier, but we will lose half of bits of int size to use.
}

// void iterativeQuickSort(int list[], unsigned int left, unsigned int right)
// {
//   std::queue<int> queue;
//   queue.push(left);
//   queue.push(right);
//
//   while (!queue.empty()) {
//     unsigned int l = queue.front();
//     queue.pop();
//     unsigned int r = queue.front();
//     queue.pop();
//
//     int pivot = partition(list, l, r); // Index of the pivot item.
//
//     if (l + 1 < pivot) {
//       queue.push(l);
//       queue.push(pivot - 1);
//     }
//     if (pivot + 1 < r) {
//       queue.push(pivot + 1);
//       queue.push(r);
//     }
//   }
// }

void iterativeQuickSort(int list[], unsigned int left, unsigned int right)
{
  std::stack<int> stack;
  stack.push(left);
  stack.push(right);

  while (!stack.empty()) {
    unsigned int r = stack.top();
    stack.pop();
    unsigned int l = stack.top();
    stack.pop();

    int pivot = partition(list, l, r); // Index of the pivot item.

    if (l + 1 < pivot) {
      stack.push(l);
      stack.push(pivot - 1);
    }

    if (pivot + 1 < r) {
      stack.push(pivot + 1);
      stack.push(r);
    }
  }
}

// void iterativeQuickSort(int list[], int left, int right)
// {
//   std::stack<int> stack;
//   stack.push(left);
//   stack.push(right);
//
//   while (!stack.empty()) {
//     int r = stack.top();
//     stack.pop();
//     int l = stack.top();
//     stack.pop();
//
//     if (r <= l) {
//       continue;
//     }
//
//     int pivot = partition(list, l, r); // Index of the pivot item.
//
//     stack.push(pivot + 1);
//     stack.push(r);
//
//     stack.push(l);
//     stack.push(pivot - 1);
//   }
// }

void quickSort(int list[], unsigned int length)
{
  assert(length);
  // recursiveQuickSort(list, 0, length - 1);
  iterativeQuickSort(list, 0, length - 1);
}

selection_sort.cpp

#include <algorithm>  // for std::swap
#include <cassert>
#include "sorting.h"

/*
 * Selection sort: O(n^2)
 */
void selectionSort(int list[], unsigned int length)
{
  assert(length);

  // <--  sorted  -->|<--  unsorted  -->
  // +---+---+-------+---+---+---------+
  // | 0 | 1 | ..... | h | i |  .....  |
  // +---+---+-------+---+---+---------+
  //                   ^
  //                head is the begin index of unsorted list.
  for (unsigned int head = 0 ; head < length - 1 ; ++head) {
    // Assume the current head value is the minimal item.
    int minIndex = head;
    for (unsigned int i = head + 1 ; i < length ; ++i) {
      if (list[i] < list[minIndex]) {
        minIndex = i;
      }
    }

    if (head != minIndex) {
      std::swap(list[head], list[minIndex]);
    }
    // After swap with the minimal value of unsorted list, the head now
    // is the tail of the sorted list.
    //
    // <--    sorted    -->|<-- unsorted -->
    // +---+---+-------+---+---------------+
    // | 0 | 1 | ..... | h | ............  |
    // +---+---+-------+---+---------------+
    //                   ^
    //  head now is the last index of the sorted list.
  }
}

sorting.h

/*
 * Simple sorting examples by using int array
 */
#ifndef SORTING_H
#define SORTING_H

/*
 * Sorting algorithms
 *   Sort an array from minimal to maximal
 *
 * @param list    The source array need to be sorted
 * @param length  The size of the input array
 */

void selectionSort(int list[], unsigned int length);

void insertionSort(int list[], unsigned int length);

void bubbleSort(int list[], unsigned int length);

void mergeSort(int list[], unsigned int length);

void quickSort(int list[], unsigned int length);

void heapSort(int list [], unsigned int length);

#endif // #ifndef SORTING_H

test.cpp

#include <cassert>
#include <iostream>
#include <random>

#include "sorting.h"

using std::cout;
using std::endl;

using std::random_device;
using std::default_random_engine;
using std::uniform_int_distribution;

random_device RandDev;
default_random_engine RandEng(RandDev());

int getRandom(int max)
{
  uniform_int_distribution<int> uniDist(0, max);
  return uniDist(RandEng);
}

void generateList(int list[], unsigned int length, int max)
{
  for (int i = 0 ; i < length ; i++) {
    list[i] = getRandom(max);
  }
}

void printList(int list[], unsigned int length)
{
  for (int i = 0 ; i < length ; i++) {
    cout << list[i] << " ";
  }
  cout << endl;
}

void assertSorted(int list[], unsigned int length)
{
  for (unsigned int i = length-1 ; i > 0 ; --i) {
    assert(list[i] >= list[i-1]);
  }
}

bool compare(int a[], int b[], unsigned int length)
{
  int i = 0;
  for (; i < length && a[i] == b[i] ; i++);
  return i == length;
}

int main()
{
  // Randomly generate a list.
  int size = 0;
  while(!size) { // Random a size if it is initialized to zero.
    size = getRandom(15);
  }
  int l[size];
  generateList(l, size, 20);

  // Show the source list.
  cout << "Source: \t\t";
  printList(l, size);

  // Copy a list for selection sort and show its result.
  int sl[size];
  memcpy(sl, l, size * sizeof(int));
  cout << "Selection sort: \t";
  selectionSort(sl, size);
  printList(sl, size);
  assertSorted(sl, size);

  // Copy a list for insertion sort and show its result.
  int il[size];
  memcpy(il, l, size * sizeof(int));
  cout << "Insertion sort: \t";
  insertionSort(il, size);
  printList(il, size);
  assertSorted(il, size);

  // Copy a list for bubble sort and show its result.
  int bl[size];
  memcpy(bl, l, size * sizeof(int));
  cout << "Bubble sort: \t\t";
  bubbleSort(bl, size);
  printList(bl, size);
  assertSorted(bl, size);

  // Copy a list for merge sort and show its result.
  int ml[size];
  memcpy(ml, l, size * sizeof(int));
  cout << "Merge sort: \t\t";
  mergeSort(ml, size);
  printList(ml, size);
  assertSorted(ml, size);

  // Copy a list for quick sort and show its result.
  int ql[size];
  memcpy(ql, l, size * sizeof(int));
  cout << "Quick sort: \t\t";
  quickSort(ql, size);
  printList(ql, size);
  assertSorted(ql, size);

  // Copy a list for heap sort and show its result.
  int hl[size];
  memcpy(hl, l, size * sizeof(int));
  cout << "Heap sort: \t\t";
  heapSort(hl, size);
  printList(hl, size);
  assertSorted(hl, size);

  // Assert all the results are same.
  assert(compare(sl ,il, size));
  assert(compare(il ,bl, size));
  assert(compare(bl ,ml, size));
  assert(compare(ml ,ql, size));
  assert(compare(ql ,hl, size));

  return 0;
}