Cardinality Sorting

cardinality-sorting.cc

#include <iostream>

using namespace std;

// a utility function that returns total set bits
// count in an integer
// http://www.geeksforgeeks.org/sort-array-according-count-set-bits/
int countBits(int a) {
    int count = 0;
    while (a) {
        if (a & 1)
            count += 1;
        a = a >> 1;
    }
    return count;
}

// http://www.algolist.net/Algorithms/Sorting/Quicksort
void quickSort(int arr[], int left, int right, bool bin = true) {
    int i = left, j = right;
    int tmp;
    int pivot = (bin) ? countBits(arr[(left + right) / 2]) : arr[(left + right) / 2];

    /* partition */
    while (i <= j) {
        while (((bin) ? countBits(arr[i]) : arr[i]) < pivot)
            i++;
        while (((bin) ? countBits(arr[j]) : arr[j]) > pivot)
            j--;
        if (i <= j) {
            // swap
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

    /* recursion */
    if (left < j)
        quickSort(arr, left, j, bin);
    if (i < right)
        quickSort(arr, i, right, bin);
}

int main() {
    // denoting the size of the array.
    int n;
    cin >> n;

    // reads decimal numbers
    int nums[n];
    for (int i = 0; i < n; i++)
        cin >> nums[i];

    quickSort(nums, 0, n - 1);

    // we do one more time because quicksort is unstable.
    int pi = 0;
    for (int i = 1; i <= n; i++) {
        if (countBits(nums[i]) != countBits(nums[pi + 1]) || i == n) {
            quickSort(nums, pi, i - 1, false);
            pi = i;
        }
    }

    // print an array
    for (int i = 0; i < n; i++)
        cout << nums[i] << endl;

    return 0;
}