Sorting algorithms

sorts.cpp

//
// Created by shrubb on 16.08.15.
//
#include <iostream>
#include <algorithm>

void radixSort(int *arr, size_t size) {

    for (size_t i = 0; i < size; ++i) {
        arr[i] ^= (1 << 31);
    }

    int *temp = new int[size];
    size_t zeros[32] = {};

    int mask;

    for (size_t i = 0; i < size; ++i) {
        mask = 1;

        for (int k = 0; k < 32; ++k) {
            zeros[k] += (arr[i] & mask) == 0;
            mask <<= 1;
        }
    }

    mask = 1;

    for (int k = 0; k < 32; ++k) {

        size_t zeroCnt = 0, oneCnt = zeros[k];

        for (size_t i = 0; i < size; ++i) {
            size_t & place = ((arr[i] & mask) == 0) ? zeroCnt : oneCnt;
            temp[place] = arr[i];
            ++place;
        }

        mask <<= 1;

        for (size_t i = 0; i < size; ++i) {
            arr[i] = temp[i];
        }
    }

    delete[] temp;

    for (size_t i = 0; i < size; ++i) {
        arr[i] ^= (1 << 31);
    }
}

void divide(int *arr, int l, int r) {
    if (r - l < 1)
        return;

    int i = l - 1;
    int j = r;
    int pivot = l + rand() % (r - l);

    std::swap(arr[r], arr[pivot]);

    while (j > i)
    {
        do
            ++i;
        while (arr[i] < arr[r]);

        do
            --j;
        while (j != i && arr[j] > arr[r]);

        if (j > i)
            std::swap(arr[i], arr[j]);
    }

    std::swap(arr[i], arr[r]);

    divide(arr, i + 1, r);
    divide(arr, l, i - 1);
}

void quickSort(int *arr, int n) {
    srand(time(0));
    divide(arr, 0, n - 1);
}

int main() {

    size_t n;
    std::cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    radixSort(arr, n);

    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << ' ';
    }

    return 0;
}