# Sorting

###### tags: `Sorting`

>Prerequisite: None

## Content
[ToC]

## Problem Statement

Input: sequence of n numbers (a1, a2,..., an).

Output: A permutation (reordering) (b1, b2,...bn) of the input sequence 
        such that b1≤b2≤...≤bn.
        
Example:
    Input:  (1,3,2,4,5,33,56,44,677,24,532,3446,76,446,5,4,43)
    OUtput: (1,2,3,4,4,5,5,24,33,43,44,56,76,446,532,677,3446)

## Insertion Sort

### Algorithm

Insertion sort is an efficient algorithm for sorting a small number of elements. In insertion sort, we will visit a number and remove the number from the array. We will find the correct position and insert into it.

The algorithm is operated as the following graph:


### Pseudo Code

function Insertion-Sort(A[]):
    for j = 2 to A.length:
        key = A[j];
        i = j-1;
        while key < A[i] && i > 0:
            A[i+1] = A[i];
            i--;
        A[i+1] = key;

### Complexity
In the worst case, for each j, we will need to compare the value of j-1 numbers at most. Therefore, if we have a size n array, the complexity will be $O(n^2)$.

## Merge Sort

### Algorithm

Merge sort is a classical "Divide and Conquer" problem. We will need to divide the original array into two smaller arrays. For example,

A = (1,4,5,6,3,3,6,7) can be divided into two smaller arrays:
A1 = (1,4,5,6) A2 = (3,3,6,7)

Once We finish sorting A1, A2, we can merge A1 and A2 into the original array.

Therefore, we will need to implement two functions: how to divide and how to merge. We will first introduce the merging part. For example,

Two arrays:
    A1 = (2,4,5,7)
    A2 = (1,2,3,6)
    
Let i be the index of A1 array; j be the index of A2 array, in the beginning:
    A1 = (2,4,5,7)
          i 
    A2 = (1,2,3,6)
          j  
We will also prepare the empty array to store the final result of the merged array.
    If A[i] < A[j], we will store A[i] into the final array, vice versus.

We will need to add one additional infinity number to let index i and j not to exceed the size of A1 and A2. We will always add the number of the other array, when we meet the number of the last index. As the graph below:


function Merge(A[], p, q, r):
    n1 = q-p+1;
    n2 = r-q;
    for i = 1 to n1:
        L[i] = A[p+i-1];
    for j = 1 to n2:
        R[j] = A[q+j];
    L[n1+1] = inf;
    R[n2+1] = inf;
    i = j = 1;
    for k = p to r:
        if L[i] > R[j]:
            A[k] = R[j];
            j++;
        else:
            A[k] = L[i];
            i++;

Finally, we can divide the original array into two smaller arrays with recursion. As the following pseudo code:

### Pseudo Code

function Merge-Sort(A[], p, r):
    if(r > p):
        q = (p+r)/2;
        Merge-Sort(A, p, q);
        Merge-Sort(A, q+1, p);
        Merge(A, p, q, r);

### Merge-Insertion Sort

Since the insertion sort will be more efficient than merge in small input size. Therefore, we can set the minimum size for merge sort. Once the input size is smaller than the minimum size, we will use insertion sort to sort the problem. As the following code:

function Merge-Insertion-Sort(A[], p, r, k):
    if r-p+1 < k :
        Insertion-Sort(A, p, r);
    else r > p:
        q = (p+r)/2;
        Merge-Insertion-Sort(A, p, q, k);
        Merge-Insertion-Sort(A, q+1, r, k);
        Merge(A, p, q, r);

### Complexity
Easy analysis will be the recursion tree method. However, the strict method will be the substitution method. The recursion tree of the algorithm will be as the following graph:

In the recursion tree, we will have the tree with $log(n)$ height, for each level of the tree, we will need to compare several pairs of subarrays for the merging function. Also, we will need to compare all the elements of the arrays to merge. TThat's, we will need to compare all the elements of the array. The complexity of the merging function will be $O(n)$. The overall complexity will be O(nlogn).

## Quick Sort

### Algorithm

Quick Sort is also a "Divide and Conquer" problem. In quick sort, we will need to find a pivot and place the pivot into the correct position. Using the position of the pivot, we will divide the array based on the position.

A = (2,8,7,1,3,5,6,4). Let A[length] = 4 be the pivot.

As we can see the correct position of pivot should be index 4.

Therefore, A = (2,1,3,4,7,5,6,8).

In order to find the correct position of the pivot, we will set the two index i and j for comparing the value of numbers. Index j will represent the current position for comparing, and index i will represent the current right-most value that is smaller than pivot. As following algorithm:

function Partition(A[], p, r):
    key = A[r];
    i = p-1;
    for j = p to r-1:
        if A[i] < key:
            i++;
            Swap(A[i], A[j]);
    Swap(A[i+1], A[length]);
    return i+1;

We will need to proceed with the function partition, in order to get the correct position of the pivot. After we get the correct position of the pivot, we can next divide the array based on the pivot position.

### Pseudo Code

function Quick-Sort(A[], p, r):
    if(r > p):
        q = Partition(A, p, r);
        Quick-Sort(A, p, q);
        Quick-Sort(A, q+1, p);

### Complexity

The worst case of quicksort will be $O(n^2)$, when we get the input array that is already sorted. The size of the following recursion will be n-1 since we will not change the position of pivot. However, the average of quick sort will be $O(nlogn)$. The proof of average complexity will be extremely complicated. Knuth offers a brilliant proof for the average complexity.

## Heap Sort

### Algorithm

Heap-Sort uses the identity of data structure max-heap. A heap is an array object that we can nearly view as the complete binary tree. As the figure below:

If the index of node is i, then index of node's children will be 2i and 2i+1

Max-heap is the data structure that the value of one node will always be larger than the value of its children. Therefore, the concept of heap-sort is that we will always get the root of the max-heap, the root of the max-heap will always be the largest of the heap. Once we take away the root of the max-heap, we can do some function to maintain the correctness of the max-heap. The maintenance function of a heap will be as follow:

The condition of the function heapify will be that the subtree of the node is also a heap. Therefore, we will need to compare whether the parent is smaller than the largest of children.

function Max-Heapify(int A[], index):
    left = 2*index;
    right = 2*index+1;
    largest = index;
    if left ≤ A.size && A[left] > A[largest]:
        largest = left;
    if right ≤ A.size && A[right] > A[largest]:
        largest = right;
    if largest != index:
        swap(A[index], A[largest]);
        max-heapify(A, largest);

We will require that the subtree of the node should be the max-heap Therefore, we will need to compare whether the parent is smaller than the largest of children. If the value of parent is smaller than that of children, then we will exchange the position of parent and child and keep doing function heapify for the original child's position.

In order to build a heap, we will need to construct from the leaves since the parent of leaves will always be the root of a max-heap.

Build-Max-Heap(A[])
    for i = A.size/2 to 1:
        Max-Heapify(A, i):

We have mentioned how to sort from the max-heap. We will need to extract the value of the root and keep maintaining the max-heap.

### Pseudo Code

function Heap-Sort(A[]):
    Build-Max-Heap(A);
    for i = size down to 1:
        Swap(A[1], A[i]);
        Max-Heapify(A, 1);

### Complexity

The complexity of heap-sort should be separated into two parts: the complexity of building heap and complexity of heap-sort.

Obviously, the complexity of max-heapify is $O(h)$, where h is the height of the max-heap tree. The complexity of building heap can be calculate as follow:


Therefore, the overall complexity will be $O(nh) = O(nlogn)$.

## Linear Sort

### Comparison Sort

Comparison sorts will determine the sorted order based only on comparisons between the input elements (<, >, =, ≤, ≥). We may not inspect the values of the elements or gain order information about them in any other way.

Now we introduce the decision tree, a decision tree is a full binary tree that represents the comparisons performed by a sorting algorithm that operates on an input of a given size. In a decision tree, each internal node is annoted by ai:aj, and each leaf is annoted by a permutation (π(1), π(2),..., π(n)).


Worst case number of comparisons is equal to the height (the longest path from root to a leaf). A binary tree of height h contains at most $2^h$ leaves. We have $n!≤2^h$. With the Stirling's formula, we will get $h≥O(nlogn)$.

### Counting Sort

Consider the biggest value of the array is k. Construct a Count[] array for counting the frequency of each number in the array.

function Counting-Sort(A[], k):
    for i = 0 to k:
        C[i] = 0;
    for i = 1 to A.size:
        C[A[i]]++;
    for i = 1 to k:
        C[i] += C[i-1];
    for i = A.size down to 1:
        B[C[A[i]]] = A[i];
        C[A[i]]--;

The prefix sum of C[A[i]] will be the last position of number A[i]. Therefore, we can assign the number A[i] into the position C[A[i]] of the array B[].


The complexity of the counting will be $O(n+k)$. The complexity will be linear when $k = O(n)$.

### Radix Sort

Radix sort is the algorithm based on counting sort which radix sort use counting sort to sort the each digit as the graph below:


The code for radix sort is straightforward. The following procedure assumes that each element in the n-element array A has d digits, where digit 1 is the lowest-order digit and digit d is the highest-order digit.

function Radix-Sort(A[], d):
    for i = 1 to d:
        countingSort(A, d);

The complexity will be the digit times the complexity of counting sort. Therefore, the overall complexity will be $O(d(k+n))$.

## C++ Code

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

void Merge(int A[], int p, int q, int r){
    int n = q-p+1;
    int m = r-q;
    int L[n+1], R[m+1];
    for(int i = 0; i < n; i++){
        L[i] = A[p+i];
    }
    for(int i = 0; i < m; i++){
        R[i] = A[q+1+i];
    }
    L[n] = INT_MAX;
    R[m] = INT_MAX;
    int i = 0;
    int j = 0;
    for(int k = p ; k <= r; k++){
        if(L[i] <= R[j]){
            A[k] = L[i];
            i++;
        }
        else{
            A[k] = R[j];
            j++;
        }
    }
}
void MergeSort(int A[], int p, int r){
    if(p < r){
        int q = (p+r)/2;
        MergeSort(A, p, q);
        MergeSort(A, q+1, r);
        Merge(A, p, q, r);
    }
}
/*****************************************/
void swap(int &a, int & b){
    int tmp = a;
    a = b;
    b = tmp;
}
int Partition(int A[], int p, int r){
    int i = p-1;
    int pivot = A[r];
    for(int j = p; j < r; j++){
        if(A[j] <= pivot){
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i+1], A[r]);
    return i+1;
}
void QuickSort(int A[], int p, int r){
    if(p < r){
        int q = Partition(A, p, r);
        QuickSort(A, p, q-1);
        QuickSort(A, q+1, r);
    }
}
int RandomizedPartition(int A[], int p, int r){
    srand(time(NULL));
    int i = (rand()%(r-p)) + p;
    swap(A[r], A[i]);
    return Partition(A, p, r);
}
void RandomizedQuickSort(int A[], int p, int r){
    if(p < r){
        int q = Partition(A, p, r);
        RandomizedQuickSort(A, p, q-1);
        RandomizedQuickSort(A, q+1, r);
    }
}

/*****************************************/
void insertionSort(int A[], int p, int r){
    for(int j = p+1; j <= r ; j++){
        int i = j-1;
        int key = A[j];
        while(i >= p && A[i] >= key){
            A[i+1] = A[i];
            i--;
        }
        A[i+1] =key;
    }
}
/*****************************************/
void Merge_InsertionSort(int A[], int p, int r, int k){
    if(r-p+1 < k){
        insertionSort(A, p, r);
        return;
    }
    else if(r > p){
        int q = (p+r)/2;
        Merge_InsertionSort(A, p, q, k);
        Merge_InsertionSort(A, q+1, r, k);
        Merge(A, p, q, r);
    }
}
/*****************************************/
void MaxHeapify(int A[], int i, int size){
    int l = 2*i+1;
    int r = 2*i+2;
    int largest = i;
    if(l < size){
        if( A[l] > A[i]) largest = l;
    }
    else largest = i;
    if(r < size){
        if(A[r] > A[largest]) largest = r;
    }
    if(largest != i){
        swap(A[i], A[largest]);
        MaxHeapify(A, largest, size);
    }
}
void BuildHeap(int A[], int size){
    for(int i = size/2-1; i >= 0; i--){
        MaxHeapify(A, i, size);
    }
}
void HeapSort(int A[], int size){
    BuildHeap(A, size);
    for(int i = size-1; i >= 0; i--){
        swap(A[0], A[i]);
        MaxHeapify(A, 0, i);
    }
}
/***********************************/
void CountingSort(int A[], int size, int k){
    int C[k+1];
    int B[size];
    memset(B, 0, sizeof(B));
    memset(C, 0, sizeof(C));
    for(int i = 0; i < size; i++){
        C[A[i]]++;
    }
    for(int i = 1; i <= k; i++){
        C[i] = C[i] + C[i-1];
    }
    for(int i = size-1; i >= 0; i--){
        B[C[A[i]]-1] = A[i];
        C[A[i]] = C[A[i]]-1;
    }
    for(int i = 0; i < size; i++){
        A[i] = B[i];
    }
}
/*************************************/
int findMax(int A[], int size){
    int max = A[0];
    for(int i = 1; i <size; i++){
        if(A[i] > max) max = A[i];
    }
    return max;
}
void CountSortforRadixSort(int A[], int digit, int size){
    int B[size];
    int C[10];
    memset(B, 0, sizeof(B));
    memset(C, 0, sizeof(C));
    for(int i = 0; i < size; i++){
        C[(A[i]/digit)%10]++;
    }
    for(int i = 1; i < 10; i++){
        C[i] += C[i-1];
    }
    for(int i = size-1; i >= 0; i--){
        B[C[(A[i]/digit)%10]-1] = A[i];
        C[(A[i]/digit)%10]--;
    }
    for(int i = 0; i < size; i++){
        A[i] = B[i];
    }
}
void radixSort(int A[], int size){
    int max = findMax(A, size);
    for(int i = 1; max/i > 0; i*=10){
        CountSortforRadixSort(A, i, size);
    }
}

int main(){
    int A[] = {1,3,2,4,5,33,56,44,677,24,532,3446,76,446,5,4,43};
    int n = sizeof(A)/sizeof(A[0]);
    MergeSort(A, 0, n-1);
    QuickSort(A, 0, n-1);
    insertionSort(A, 0, n-1);
    Merge_InsertionSort(A, 0, n-1, 8);
    RandomizedQuickSort(A, 0, n-1);
    HeapSort(A, n);
    CountingSort(A, n, 3446);
    radixSort(A, 17);
    return 0;
}