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