#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8c3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAp2b2lkIHRocmVlV2F5UGFydGl0aW9uKGludCBkYXRhW10sIGludCBzaXplLCBpbnQgbG93LCBpbnQgaGlnaCkgewogICAgaW50IHAgPSAtMTsKICAgICAgICBpbnQgcSA9IHNpemU7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBxOykgewogICAgICAgICAgICAgICAgaWYgKGRhdGFbaV0gPT0gbG93KSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHN3YXAoZGF0YVtpXSwgZGF0YVsrK3BdKTsKICAgICAgICAgICAgICAgICAgICAgICAgKytpOwogICAgICAgICAgICAgICAgfSBlbHNlIGlmIChkYXRhW2ldID49IGhpZ2gpIHsKICAgICAgICAgICAgICAgICAgICAgICAgc3dhcChkYXRhW2ldLCBkYXRhWy0tcV0pOwogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICAgICAgKytpOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KfQogCnN0cmluZyBwcmludEFycmF5KGludCBhcnJbXSwgaW50IHNpemUpIHsKICAgICAgICBvc3RyaW5nc3RyZWFtIHJlc3VsdDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHNpemU7ICsraSkgewogICAgICAgICAgICAgICAgcmVzdWx0IDw8IGFycltpXSA8PCAiICI7CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXN1bHQuc3RyKCk7Cn0KIAppbnQgbWFpbigpIHsKaW50IGFycltdID0gezUsIDUsIDUsIDEsIDEsIDEsIDgsIDgsIDh9OwogICAgaW50IGFycl9zaXplID0gc2l6ZW9mKGFycikvc2l6ZW9mKGFyclswXSk7CiAgICAgICAgY291dCA8PCAiYXJyYXkgYmVmb3JlIHNvcnRpbmc6ICIgPDwgcHJpbnRBcnJheShhcnIsIGFycl9zaXplKSA8PCBlbmRsOwogICAgICAgIHRocmVlV2F5UGFydGl0aW9uKGFyciwgYXJyX3NpemUsIDMsIDcpOwogICAgICAgIGNvdXQgPDwgImFycmF5IGFmdGVyIHNvcnRpbmcgdXNpbmcgPT06ICIgPDwgcHJpbnRBcnJheShhcnIsIGFycl9zaXplKSA8PCBlbmRsOwogICAgICAgIHJldHVybiAwOwp9