Output
Before sorting
1 3 3 2 1
After sorting
1 1 2 3 3
Press any key to continue . . .
Solution
It is actually a Dutch National Flag problem
Ref: http://en.wikipedia.org/wiki/Dutch_national_flag_problem
#include <iostream>
using namespace std;
void Swap(int& a, int& b)
{
int t = a;
a = b;
b = t;
}
void ThreeWayPartition(int data[], int size, int low, int high) {
int bottom = -1;
int top = size;
for (int i = 0; i < top;) {
if (data[i] == low) {
Swap(data[i], data[++bottom]);
++i;
} else if (data[i] >= high) {
Swap(data[i], data[--top]);
} else {
++i;
}
}
}
int main(int argc, char* argv[])
{
int arr[] = {1, 3, 3, 2, 1};
int arrLen = sizeof(arr)/sizeof(int);
cout << "Before sorting" << endl;
for(int i = 0; i < arrLen; ++i){
cout << arr[i] << " ";
}
cout << endl;
ThreeWayPartition(arr, arrLen, 1, 3);
cout << "After sorting" << endl;
for(int i = 0; i < arrLen; ++i){
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Problem
You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third.
Ex: Input [1, 3, 3, 2, 1]
Output [1, 1, 2, 3, 3]
But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts.
You are only permitted to swap elements.