#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}
string printArray(int arr[], int size) {
ostringstream result;
for (int i = 0; i < size; ++i) {
result << arr[i] << " ";
}
return result.str();
}
int main() {
int arr[] = {5, 5, 5, 1, 1, 1, 8, 8, 8};
int arr_size = sizeof(arr)/sizeof(arr[0]);
cout << "array before sorting: " << printArray(arr, arr_size) << endl;
threeWayPartition(arr, arr_size, 3, 7);
cout << "array after sorting using <: " << printArray(arr, arr_size) << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8c3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAp2b2lkIHRocmVlV2F5UGFydGl0aW9uKGludCBkYXRhW10sIGludCBzaXplLCBpbnQgbG93LCBpbnQgaGlnaCkgewogICAgaW50IHAgPSAtMTsKICAgICAgICBpbnQgcSA9IHNpemU7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBxOykgewogICAgICAgICAgICAgICAgaWYgKGRhdGFbaV0gPCBsb3cpIHsKICAgICAgICAgICAgICAgICAgICAgICAgc3dhcChkYXRhW2ldLCBkYXRhWysrcF0pOwogICAgICAgICAgICAgICAgICAgICAgICArK2k7CiAgICAgICAgICAgICAgICB9IGVsc2UgaWYgKGRhdGFbaV0gPj0gaGlnaCkgewogICAgICAgICAgICAgICAgICAgICAgICBzd2FwKGRhdGFbaV0sIGRhdGFbLS1xXSk7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICArK2k7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQp9CiAKc3RyaW5nIHByaW50QXJyYXkoaW50IGFycltdLCBpbnQgc2l6ZSkgewogICAgICAgIG9zdHJpbmdzdHJlYW0gcmVzdWx0OwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgKytpKSB7CiAgICAgICAgICAgICAgICByZXN1bHQgPDwgYXJyW2ldIDw8ICIgIjsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlc3VsdC5zdHIoKTsKfQogCmludCBtYWluKCkgewppbnQgYXJyW10gPSB7NSwgNSwgNSwgMSwgMSwgMSwgOCwgOCwgOH07CiAgICBpbnQgYXJyX3NpemUgPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsKICAgICAgICBjb3V0IDw8ICJhcnJheSBiZWZvcmUgc29ydGluZzogIiA8PCBwcmludEFycmF5KGFyciwgYXJyX3NpemUpIDw8IGVuZGw7CiAgICAgICAgdGhyZWVXYXlQYXJ0aXRpb24oYXJyLCBhcnJfc2l6ZSwgMywgNyk7CiAgICAgICAgY291dCA8PCAiYXJyYXkgYWZ0ZXIgc29ydGluZyB1c2luZyA8OiAiIDw8IHByaW50QXJyYXkoYXJyLCBhcnJfc2l6ZSkgPDwgZW5kbDsKICAgICAgICByZXR1cm4gMDsKfQ==