[Re-view] Common Sorting Algorithms: Concepts and Implementations

Common Sorting Algorithms: Concepts and Implementations  

Introduction

Understanding the basic concepts of the popular sorting algorithms, can not only help you better understand the data structure and algorithm from a different perspective, but also helps you make the computational complexity clearer in your mind. Besides, sorting related questions, are also hot questions in your software engineering job interview.

Many books, courses, and websites are providing massive materials of sorting algorithms.  From my own experiences, among the long and tedious sources, http://www.sorting-algorithms.com/, and https://en.wikipedia.org/wiki/Sorting_algorithm are two good places you can learn the sorting algorithm intuitively, because there are animations shown in the website. If you have already familiar or have the basic concept of the sorting algorithms, it would help you easily memorize the details of specific algorithm.

In this blog, I'd like to review the common popular sorting algorithms, with the basic concepts, and tries to explain each one intuitively. Also the C++ implementation is the core content and are provided detailed with comments. This blog is more suitable for who have already implemented some of the sorting algorithms (at least you may write the selection sorting or bubble sorting in 1 or 2 minutes), but I will try to explain more for the novices.

1. What algorithms are covered ?

1.     Bubble sort  
2.     Selection sort
3.     Inset sort
4.     Merge sort
5.     Quick sort
6.     Heap sort
7.     Bucket sort

2. Computational Complexity   

1.     Bubble sort                       O(n^2 )
2.     Selection sort                    O(n^2)
3.     Inset sort                           O(n^2)
4.     Merge sort                        O(nlogn)
5.     Quick sort                         O(nlogn)
6.     Heap sort                          O(nlogn)
7.     Bucket sort                       O(n+k)

    How to know these in a fast way?  Just memorize them!  My experience is that 

• If there are 2 loops in the code, it is O(n^2)
• If the algorithm is easily implemented, it is O(n^2)" 
• Otherwise it is O(nlogn), expect the bucket sort.

3. Concepts and Implementations

The sorting problem is quite straightforward----sort the data array (ascending order). We will not go into the detail that what kind of data structure or data type are used, and not interested in the comparison function.

Here we define the general case:
Input: 
    int n; //array length
    int* A[n];  // unsorted int array
Output:
   int* A;      // sorted array (ascending order)

Function:
  swap(int a, int b) // swap the value of a and b
  

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

In the following, I'll show the key concept and the way how I  remember these sorting algorithms.
NOTE that there may have different forms for  one sorting algorithm, here just shows one of them.
NOTE that to better understand the following, I personally suggest read the code directly along with the explanations.

Bubble sort

-----------------------------------------------------------------------------------
Concept: 

Scan from start to end, compare every two elements, swap the max to the end.
Scan from start to end-1, compare every two elements, swap the max to the end-1.
Scan from start to end-2, compare every two elements, swap the max to the end-2.
...
Scan from start to start, end.

Key Point:
if A[j]>A[j+1], swap(A[j], A[j+1]);

How to Memorize:
Compare each pair and bubble the max value out and move to the last.

Code:

//Bubble Sort
void bubbleSort(int *A, int n){
  for (int i=n-1;i>0;i--){
    for (int j=1;j<=i;j++){
      if (A[j]<A[j-1]){
        swap(A[j],A[j-1])       
      }
    }
  }
}

Selection sort

-----------------------------------------------------------------------------------
Concept:
From 1st to last, find the min value,  store to the 1st position.
From 2nd to last, find the min value, store to the 2nd position.
From 3rd to last, find the min value, store to the 3rd position.
...
From last-1 to last, find the smaller one, store to the last-1 position. End.

Key Point:
k=i;  // store the current start position
if (A[j]<A[k]) {k=j;} // store the index of min value

How to Memorize:
Select the min value and store to the front.

Code:

//Selection Sort
void selectSort(int *A, int n){
  for (int i=0;i<n-1;i++){
    int k=i; // k can be viewed as the index of min value
    for (int j=i+1;j<n;j++){ // find the min value
      if (A[j]<A[k]){k=j;}
    }
    swap(A[i],A[k]);  // store the min value to the start
  }
}

Inset sort

-----------------------------------------------------------------------------------
Concept:
For each element A[i], the array A[0..i-1] is already sorted. Scan A[0..i-1], find the correct place and insert A[i].

Key Point:
Find the correct place and insert the A[i] in sorted A[0..i-1].
Consider A[0..i]:   [1,3,4,5,8,2],
So, A[i]=2.
Store it to a variable: tmp = A[i];
What we need to do now?
[1,3,4,5,8,2] ---->  [1,2,3,4,5,8]
How to do this?
Keep moving each element to its right (A[j]=A[j-1]), until the next element is less than  A[i].

How to Memorize:
Insert every element to its previous sorted array.

Code:

//Insert Sort
void insertSort(int *A, int n){
  for (int i=0;i<n;i++){
    int tmp = A[i];
    int j=i;
    while (j>0 && tmp<A[j-1]){
        A[j]=A[j-1];
        j--;
    }
    A[j]=tmp;   
  }
}

Merge sort

-----------------------------------------------------------------------------------
Concept:
Here I interpret merge sort using the recursion. So hopefully you have the basic idea what recursion is.
The idea is mainly considering the array into smaller subsets,  merge the smallest subsets to smaller subset, merge smaller subsets to small subset ... until merge subset to the whole array. Merging process itself handles the sorting.

This figure (from wikipedia) shows the exact process of merge sort. Please go through the whole tree at the same time thinking it as a recursive problem, this will greatly help you understand the implementation of this algorithm.

Key Point:
Merge sort consist two parts:
(1) Recursion Part.
(2) Merge Part.

Recursive part, handles divided the current set to two parts, just like the concept of divide-and-conquer: Find the middle, divide into left and right subset and continue dividing in each subset. Recursion also keeps the two subset sorted for the merging.

Merge Part, is very very important for this algorithm, which merges two array to make a new sorted array.
How to do it ? Let's take a example.
Assume: A1=[1,5,7,8] and A2=[2,6,9,10,11,12,13]
What we need ?  A new sorted array A = [1,2,5,6,7,8,9,10,11,12,13]
OK, now at least we need a new array
A of length A1+A2, say,  A[ , , , , , , , ,].
How to put element in A and considering the order?
Set 3 pointers i,j,k, for A1, A2, and target array A.
A1=[1,5,7,8]
        i
A2=[2,6,9,10,11,12,13]
        j
A =[ , , , , , , , ,].
       k
From above one can clearly see, the 1st element in A (A[k]), should be min(A1[i],A2[j]), it is A1[i] = 1. So A1[i] is already in A, then we go to the next element in A1 using i++.  And the 1st element in A is filled, we have to go to the next one, so k++.
A1=[1,5,7,8]
            i
A2=[2,6,9,10,11,12,13]
        j
A =[1, , , , , , , ,].
          k
Next,  similarly compare A[i] and A[j],  get the smaller one and fill into the array A, and set the pointers properly.
A1=[1,5,7,8]
            i
A2=[2,6,9,10,11,12,13]
            j
A =[1,2, , , , , , ,].
             k    
In such a way, the loop goes until the end of A1. At this time, the merge is NOT finished, we have to combine the rest elements of A2 into A.
Finally,  A = [1,2,5,6,7,8,9,10,11,12,13].


How to Memorize:
(1) Recursion Part: divide from the middle
(2) Merge Part:  merge two sorted array into one sorted array


Code:

//Merge Sort
void mergeSort(int *A, int st, int ed){
  if (st>=ed) {return;}
  int m = st+(ed-st)/2;
  mergeSort(A,st,m);
  mergeSort(A,m+1,ed);
  
  int *tmp = new int[ed-st];
  int k=0; 
  int i=st;
  int j=m+1;
  
  while (i<m+1 && j<=ed){   
    if (A[i]<A[j]){
       tmp[k++]=A[i++];
    }else{
 tmp[k++]=A[j++];    
    }
  }
  while (i<m+1){tmp[k++]=A[i++];}
  while (j<=ed){tmp[k++]=A[j++];}
  
  for (int ii=0;ii<k;ii++){cout <<tmp[ii] <<" ";}
  cout << endl;
  
  for (int ii=st; ii<=ed;ii++){ A[ii] = tmp[ii-st];}

  delete [] tmp; 
 
}

Quick sort

-----------------------------------------------------------------------------------
Concept:
This is also a Divide and Conquer algorithm. The idea is:  for an element pivot in the array, place the elements less than pivot to its left, and elements greater than pivot to its right. Do this same procedure to the two subsets (left and right), until all the elements are sorted.

Key Point:
Quick sort mainly consisted two parts:
(1) Recursive part: recursively apply the for the subsets.
(2) Reorder the set, where elements < pivot value are placed to its left, and vice versa.
     This is the important part of the algorithm:
     Consider the array
     A=[8,3,5,6,4,1,9]
     Here we choose the middle element as the pivot (also can select the 1st one or randomly select)
     What we want to do ?
    A[1,3,5,4,6,8,9],  then sort[1,3,5,4,6] and [8,9] recursively.

     First, put pivot to the front (swap(A[0],A[pivot])):
     A=[6,3,5,8,4,1,9]
    Then set two pointers i and p, start from the 2nd element. p points to the first element which is bigger than pivot. 
     A=[6,3,5,8,4,1,9]
               i        
              p
    Compare A[i] with A[0], if A[i] < A[0], swap A[i] and A[p], goto next.
     A=[6,3,5,8,4,1,9]
                  i        
                 p
     and
     A=[6,3,5,8,4,1,9]
                     i        
                    p
     here A[i]>A[0], no swap, i++
     A=[6,3,5,8,4,1,9]
                        i        
                    p
     4<6, swap A[i] and A[p], because A[p] was found larger than A[0]
     A=[6,3,5,4,8,1,9]
                           i        
                       p
     Still have to swap:
     A=[6,3,5,4,1,8,9]
                              i        
                          p
     No swap, i goes to the end, and now p is the place where 0..p-1 < pivot, and p..n > pivot.
     Last step is to swap A[0] and A[p-1]:
    A[1,3,5,4,6,8,9]

How to Memorize:
(1) Recursion (divide-and-conquer)
(2) Select a Pivot
(3) Aim: reorder elements<pivot to the left and elements>pivot to the right
(4) Set pivot to front
(5) Set two pinter


Code:

//Quick Sort
void quickSort(int *A, int st, int ed){
 if(st>=ed){return;}
 int pivot = st+(ed-st)/2;
 swap(A[st],A[pivot]);
 int pos = st+1;
 for (int i=st+1;i<ed;i++){
   if (A[i]<A[st]){
     swap(A[i],A[pos]);
     pos++;
   }
 }
 swap(A[pos-1],A[st]);
 quickSort(A,st,pos-1);
 quickSort(A,pos,ed);
 
}

Heap sort

-----------------------------------------------------------------------------------
Concept:
Heap sort is based on the data structure heap, which is a tree structure with a nice ordering property, can be used for sorting.  The heap sort algorithm consists of two parts:
(1) Construct the heap
(2) Get the root node each time, update the heap, until all the node are removed.

First let's see what is heap (in my own word):
A heap, briefly speaking, is a tree structure, where the value of each parent node is greater/smaller than its children. Practically in the heap sort, we use the specific kind of heap----binary heap.

Binary heap,  is a complete binary tree, also keeps the property that each root value is greater or smaller than its left and right children. Thus, the root of the tree is the biggest (called max heap) or the smallest (called min heap) element in the tree.

Caution!!!  A Heap is NOT a binary search tree(BST)! A BST can apply in-order traversal to get the sorted  array, heap CANNOT guarantee the ordering within same level, so it does not have a specific requirement of the order for the left and right children. e.g. see the figure below(from wikipedia)
A heap structure: 
A binary search tree structure: 

• How to construct the heap?

          Consider a unsorted array, we want to construct a heap. The intuitive way is to obtain every node and add to the tree structure(TreeNode* blablabla...), but a simpler way is just use the array itself, to represent the tree and modify the value to construct the heap.

       Tree  (Array  representation):
            Root node: A[0].
            Left child   of A[i]:  2*i+1
            Right child of A[i]:  2*i+2
            Parent of A[i]:        (i-1)/2

      Construct a heap:
           An operation downshift is used here.
           The idea of downshift is to adjust the current node to its proper position in its downside direction.
           Given a node, compare the value to the bigger one of its left and right children, is the value is smaller than the bigger children, then swap them. And keep checking the node (here in the new position after swapping), until it is no less than its children.
            To construct the heap, from the end of the array, we downshift every node to the first in the array.
         

• How to get the sorted array according to the heap?

         Given a max heap, the value of root node is the biggest in the heap, each time remove the top node and store to the array. But it's not enough! We have to keep the heap, so there needs a update of the remaining nodes.  An efficient way is just swap the root node and the last element of the tree, remove the last node (just let the length of the array -1), downshift the new root node, a heap is updated.



Key Point:
(1) How to construct the heap?
      Use array to represent the tree structure.
      Recursively downshift every node.
(2) How to get the sorted array according to the heap?
      Each time remove the root of the heap, swap the last node to the root and downshift it.
      Until all the nodes are removed.

How to Memorize:
This algorithm is very particular and requires the skill of heap operations (construct, downshift, update, etc.).
In my opinion, first you get to know the data structure heap, then the heap sort suddenly becomes a piece of cake!

Code:

//Heap Sort
void downshift(int* A, int n, int parent){
  if (parent<0 ){return;}
  int left = parent*2+1;
  int right = parent*2+2;
  int mxch;
  if (left>=n) {return;}
  if (right>=n) {mxch=left;}
  else{mxch = A[left]>=A[right]?left:right;}
  if (A[parent]<A[mxch]){
    swap(A[parent],A[mxch]);
    downshift(A, n,mxch);
  } 
}

void constructHeap(int *A, int n){
  int parent=(n-2)/2;
  for ( ;parent>=0;parent--){ 
    downshift(A, n, parent);
  } 
}

void heapSort(int *A, int n){
constructHeap(A,n);
int i=n-1;
int *B=new int[n];
while (i>=0){
  B[n-i-1]=A[0]; //get the biggest in the heap
  swap(A[0],A[i]);
  downshift(A,i,0);
  i--;
}
A=B;
}

Bucket sort (coming soon)

-----------------------------------------------------------------------------------
Concept:
Key Point:
How to Memorize:
Code:

aaa

leetcode Question 130: Sum Root to Leaf Numbers

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Analysis:

Once we see this kind of problem, no matter what sum is required to output, "all root-to-leaf" phrase reminds us the classic Tree Traversal or Depth-First-Search algorithm. Then according to the specific problem, compute and store the values we need. Here in this problem, while searching deeper, add the values up (times 10 + current value), and add the sum to final result if meet the leaf node (left and right child are both NULL).

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void dfs(TreeNode* root,int cur, int &res){
        if (root->left==NULL && root->right==NULL){
            cur=cur*10+root->val;
            res+=cur;
        }else{
            cur=cur*10+root->val;
            if (root->left){
                dfs(root->left,cur,res);
            }
            if (root->right){
                dfs(root->right,cur,res);
            }
        }
    }
    int sumNumbers(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int res=0;
        if (!root){return res;}
        dfs(root,0,res);
        return res;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    res = 0
    def search(self, root, path):
        if root.left == None and root.right == None:
            self.res += path + root.val
        else:
            if root.left != None:
                self.search(root.left, (path + root.val)*10)
            if root.right != None:
                self.search(root.right, (path + root.val)*10)
            
    def sumNumbers(self, root):
        self.res = 0
        if root == None:
            return 0
        else:
            self.search(root, 0)
            return self.res
            
        
        

leetcode Question 129: Longest Consecutive Sequence

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Analysis:

At first glance, the "longest" requirement may lead us to DP. But this problem actually tests data structure rather than a certain algorithm.

If there is no O(n) requirement, we can just sort the array (O(n log n)), then find then longest sequence after a scan.

With the time limit O(n), first of all, what comes to my mind is HASH MAP! Because hash map searches value by key in O(1) time. Note that in C++ STL, the map<> data structure is implemented by BST, so the insert in O(log n), therefore we need to use the unordered_map<>, which has O(1) time complexity.

Firstly, we put all the element into a map.
Secondly, how to find the consecutive elements? Since the O(n) requirement, scan the array is a must.
For each element, we need to find its consecutive elements. Consecutive means +1 or -1, a while loop is enough to handle. Search two directions respectively (+1, -1),  during the search if the key is found, remove the current item in the map. This is because if two items are consecutive, the longest elements for this two are the same, no need to search again. In this way, the length of longest consecutive elements can be easily found.

Note that in C++ map<>, find(key) function will return  the end() iterator if key does not exist, But if we use (mp[key]==false), when key is not in the map, the program will insert the key into the map with a default value, so use find function is a safer way.

Code (C++):

class Solution {
public:

    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,bool>mp;
        for (int i=0;i<num.size();i++){
            mp[num[i]]=true;
        }
        
        int res=0;
        for (int i=0;i<num.size();i++){
            int mx=1;      
            int fd = num[i];
            
            mp.erase(num[i]);
            while (mp.find(fd+1)!=mp.end()){
                mx++;
                mp.erase(fd+1);
                fd++;
            }
            
            fd = num[i];
            while (mp.find(fd-1)!=mp.end()){
                mx++;
                mp.erase(fd-1);
                fd--;
            }
            
            if (mx>res){res=mx;}
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        dic = {}
        maxlen = 1
        for n in num:
            dic[n] = 1
        for n in num:
            if dic.has_key(n):
                tmp = n + 1
                l = 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp+=1
                tmp = n - 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp-=1
                maxlen = max(l, maxlen)
            else:
                continue
        return maxlen

leetcode Question 126: Valid Palindrome

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Analysis:
This is an easy and fundamental problem about string and char.

Set two pointers from the start and the end of the string to test Palindrome, skip the chars that are not alphanumeric and compare the lower case of each pair of chars.

Here are some tricks:
(1) upper lower cases:  #include <cctype>, there is a function called "tolower()"
(2) alphanumeric: also in <cctype>(or <ctype.h>), a function called "isalnum()"

Code (updated 2013.08) :

class Solution {
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size()==0)   {return true;}
        
        int st = 0;
        int ed = s.size()-1;
        
        while (st<ed){
            if (isalnum(s[st])==false){st++; continue;}
            if (isalnum(s[ed])==false){ed--; continue;}
            
            if (tolower(s[ed])!=tolower(s[st])){
                return false;
            }else{
                st++;
                ed--;
            }
        }
        
        return true;
    }
};

leetcode Question 105: Subsets II

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Analysis:
Be careful with the question, for [1,2,2], [2,2] is needed.
Here we use another way different from the previous problem to solve this problem.

First, consider there is no duplicates, how to generate the subsets?
Say n is the # of the elements,
when n=1, subsets :  {}, {"1"},  "i" means the ith element.
when n=2, subsets:   {}, {"1"}, {"2"}, {"1", "2"}
when n=3, subsets:   {}, {"1"}, {"2"}, {"1", "2"}, {"3"}, {"1","3"}, {"2","3"}, {"1", "2","3"}
So, the way of generating subsets is:
From 2 to n, COPY the previous subsets, add the current element, push back to the subsets list.

Then we take the duplicates into account, the same example:
when n=1, subsets :  {}, {"1"},  "i" means the ith element.
when n=2, subsets:   {}, {"1"}, {"2"}, {"1", "2"}
when n=3, but "2"=="3" subsets:
   {}, {"1"}, {"2"}, {"1", "2"}, {"3"}, {"1","3"}, {"2","3"}, {"1", "2","3"}
since "2"=="3", which truly is:
   {}, {"1"}, {"2"}, {"1", "2"}, {"2"}, {"1","2"}, {"2","2"}, {"1", "2","2"}
where the bold ones are not needed.
So, how these two subsets are generated? They are from the subsets of n=1.

In sum up, when meet the same element as previous one, then generate new subsets ONLY from the subsets generated from previous iteration, other than the whole subsets list.

See code below for more details.

Code(Updated 201309):

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    sort(S.begin(),S.end());
    vector<vector<int> > res;
    vector<int> r;
    res.push_back(r);
    r.push_back(S[0]);
    res.push_back(r);
    int pre = S[0];
    int count = 1;
    for (int i=1;i<S.size();i++){
      int st=0;  
      int sz = res.size();
      if (S[i]==pre){st = sz-count;}
      count =0;
      for (int j=st;j<sz;j++){
        r = res[j];
        r.push_back(S[i]);
        res.push_back(r);
        count++;
      }
      pre=S[i];
    }
    return res;
  }
};

Code:

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(S.begin(),S.end());
        vector<vector<int> > res;
        vector<int> ss;
        res.push_back(ss);
        ss.push_back(S[0]);
        res.push_back(ss);
        int count=1;
        int pre = S[0];
        for (int i=1;i<S.size();i++){
                int sz = res.size();                
                if (S[i]!=pre){
                    count=0;
                    for (int j=0;j<sz;j++){
                        ss=res[j];
                        ss.push_back(S[i]);
                        res.push_back(ss);
                        count++;
                    }
                }else{
                    int ind=count;
                    count=0;
                    for (int j=sz-ind;j<sz;j++){
                        ss=res[j];
                        ss.push_back(S[i]);
                        res.push_back(ss);
                        count++;
                    }
                    
                }              
            pre = S[i];
        }
        return res;
    }
};