# Sort an array of 0’s, 1’s, and 2’s

• Brute force is to sort the array O(NlogN) we can do a lot better than that
• Efficient approach is to just count the no of 1’s, 2’s and 3’s in one for loop and then put the values in the array in another loop O(N) time but it requires 2 traversals
• Can we do this in just 1 traversal ? Yes !! DUTCH NATIONAL FLAG !!

# ALGORITHM -

• Take three-pointers, namely — low, mid, high.
• We use low and mid pointers at the start, and the high pointer will point at the end of the given array.
• low is for 0’s, mid is for 1’s and high is for 2’s (you would have figured this out already…I hope so xD)
1. Index `0` to `low` - this is the "bottom group" (O’s)
2. Index `low` to `mid` - this is the "middle group" (1’s)
3. Index `mid` to `high` - this is the "top group" (2’s)

# CASES :

• If array [mid] =0, then swap array [mid] with array [low] and increment both pointers once.
• If array [mid] = 1, then no swapping is required. Increment mid pointer once.
• If array [mid] = 2, then we swap array [mid] with array [high] and decrement the high pointer once.

## Time to get our hands dirty !!

`int n = arr.size(); int low = 0, mid =0,high = n - 1;while (mid <= hi) {        switch (a[mid]) {                         // If the element is 0        case 0:            swap(a[low++], a[mid++]);            break;                        // If the element is 1 .        case 1:            mid++;            break;                       // If the element is 2        case 2:            swap(a[mid], a[high--]);            break;        }    }}`
`low = 0    high = arr_size - 1    mid = 0    while mid <= high:       if arr[mid] == 0:         arr[low],arr[mid] = arr[mid],arr[low]         low = low + 1        mid = mid + 1      elif arr[mid] == 1:         mid = mid + 1      else:         arr[mid],arr[high] = arr[high],arr[mid]         high = high - 1    return arr`

## Three way partitioning of an array around a given range

`Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}         lowVal = 14, highVal = 20Output: arr[] = {1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54}`

`vector<int> threeWayPartition(vector<int> &arr, int a, int b){    int n = arr.size();    int low = 0, high = n - 1;    int index = 0;               // Traverse all elements of array    while (index <= high)    {              // Place elements less than a to front        if (arr[index] < a)        {            swap(arr[index], arr[low]);            index++;            low++;        }             // Place elements greater than b to back        else if (arr[index] > b)        {            swap(arr[index], arr[high]);            high--;        }        else            index++;    }return arr;}`

# Thank You !

--

--

--

## More from Vidhu Verma

A full stack developer and a curious person

Love podcasts or audiobooks? Learn on the go with our new app.

## Vidhu Verma

A full stack developer and a curious person