#include <cstdio>
#include <algorithm>

#define XOR_SWAP(x,y) do { x ^= y; y ^= x; x ^= y; } while (0)

// Quicksort with XOR_SWAP
void qsort1(int *a, int lo, int hi) {
    if (lo >= hi) { return; }

    int pivot = a[hi];
    int i = lo-1;

    for (int j = lo; j <= hi; j++) {
        if (a[j] <= pivot) {
            i = i+1;
            XOR_SWAP(a[i], a[j]);
        }
    }

    qsort1(a, lo , i-1);
    qsort1(a, i+1, hi );
}

// Quicksort with std::swap
void qsort2(int *a, int lo, int hi) {
    if (lo >= hi) { return; }

    int pivot = a[hi];
    int i = lo-1;

    for (int j = lo; j <= hi; j++) {
        if (a[j] <= pivot) {
            i = i+1;
            std::swap(a[i], a[j]);
        }
    }

    qsort2(a, lo , i-1);
    qsort2(a, i+1, hi );
}

int main(int argc, char **args) {
    int test1[] = { 10, 7, 3, 9, 4, 1, 2, 6, 5, 8 };
    int test2[] = { 10, 7, 3, 9, 4, 1, 2, 6, 5, 8 };

    qsort1(test1, 0, 9);
    qsort2(test2, 0, 9);

    std::printf("\nTest 1 (XOR swap):\n\n");
    for (int i = 0; i < 10; i++) {
        std::printf("%d\n", test1[i]);
    }

    std::printf("\nTest 2 (std::swap):\n\n");
    for (int i = 0; i < 10; i++) {
        std::printf("%d\n", test2[i]);
    }
}