Sort Colors

 from geeksforgeeks
The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-1] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi–
       
    

     void sortColors(int A[], int n) {
        int lo=0,mid=0,hi=n-1;
        while(mid<=hi){
            switch(A[mid]){
                case 0:swap(A[lo++],A[mid++]); break;
                case 1:mid++; break;
                case 2:swap(A[mid],A[hi--]);
            }
        }
    }