5_sort012.md

Sort 0 1 2

O(N log N) Time Complexity with sort function.

• sort the vector using stl sort() function.

O(N)+O(N) Time using counting sort.

• count number of 0's, 1's, and 2's and push them in increasing order according to their frequency.

O(N) Time, 3 Pointers, dutch national flag algorithm.

• We take 3 pointers low, mid and high.
• low and mid points to 0 while high points to the last element.
• we assume following conditions.
  • Towards the left of low everything is 0.
  • Towards the right of high everything is 2.
  • In between low and high, everything is 1.
• while(mid<=high) we do following.
  • When we encounter 0.
    • we swap low and mid.
    • we increment low and mid.
  • When we encounter 1.
    • we increment mid.
  • When we encounter 2.
    • we swap mid and high.
    • we decrement high.

Code

#include <bits/stdc++.h>
void sort012(int *arr, int n)
{
    int low = 0, mid = 0, high = n-1;
    while(mid<=high){
        switch(arr[mid])
        {
            case 0:
                swap(arr[low++],arr[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(arr[mid],arr[high--]);
                break;
        }
    }
}