SortingAlgorithms.cpp

//
//  main.cpp
//  SortingAlgorithms
//
//  Created by Stephen Baidu on 9/8/14.
//  Copyright (c) 2014 Stephen Baidu. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void swap(std::vector<int> & data, int i, int j)
{
    int tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}

void print(std::vector<int> const & data)
{
    std::vector<int>::const_iterator iter = data.begin();
    
    for (; iter != data.end(); ++iter)
    {
        cout << *iter << " ";
    }
    
    if (data.size() > 0)
    {
        cout << endl;
    }
}

int generateRandom(int low, int high);
void Shuffle(std::vector<int> & data)
{
    int length = (int)data.size();
    
    for (int i = 0; i < length-1; ++i)
    {
        swap(data, i, generateRandom(i+1, length-1));
    }
    
    print(data);
}

int generateRandom(int low, int high)
{
    srand(low);
    int gen = 0;
    gen = rand() % (high - low + 1) + low;
    return gen;
}

//useful for small lists, and for large lists where data is
//already sorted
void BubbleSort(std::vector<int> & data)
{
    int length = (int)data.size();
    
    for (int i = 0; i < length; ++i)
    {
        bool swapped = false;
        for (int j = 0; j < length - (i+1); ++j)
        {
            if (data[j] > data[j+1])
            {
                swap(data, j, j+1);
                swapped = true;
            }
        }
        
        if (!swapped) break;
    }
}

//useful for small lists and where swapping is expensive
// does at most n swaps
void SelectionSort(std::vector<int> & data)
{
    int length = (int)data.size();
    
    for (int i = 0; i < length; ++i)
    {
        int min = i;
        for (int j = i+1; j < length; ++j)
        {
            if (data[j] < data[min])
            {
                min = j;
            }
        }
        
        if (min != i)
        {
            swap(data, i, min);
        }
    }
}

//useful for small and mostly sorted lists
//expensive to move array elements
void InsertionSort(std::vector<int> & data)
{
    int length = (int)data.size();
    
    for (int i = 1; i < length; ++i)
    {
        bool inplace = true;
        int j = 0;
        for (; j < i; ++j)
        {
            if (data[i] < data[j])
            {
                inplace = false;
                break;
            }
        }
        
        if (!inplace)
        {
            int save = data[i];
            for (int k = i; k > j; --k)
            {
                data[k] = data[k-1];
            }
            data[j] = save;
        }
    }
}

void Merge(std::vector<int> & data, int lowl, int highl, int lowr, int highr);
void MergeSort(std::vector<int> & data, int low, int high)
{
    if (low >= high)
    {
        return;
    }
    
    int mid = low + (high-low)/2;
    
    MergeSort(data, low, mid);
    
    MergeSort(data, mid+1, high);
    
    Merge(data, low, mid, mid+1, high);
}

void Merge(std::vector<int> & data, int lowl, int highl, int lowr, int highr)
{
    int tmp_low = lowl;
    std::vector<int> tmp;
    
    while (lowl <= highl && lowr <= highr)
    {
        if (data[lowl] < data[lowr])
        {
            tmp.push_back(data[lowl++]);
        }
        else if (data[lowr] < data[lowl])
        {
            tmp.push_back(data[lowr++]);
        }
        else
        {
            tmp.push_back(data[lowl++]);
            tmp.push_back(data[lowr++]);
        }
    }
    
    while (lowl <= highl)
    {
        tmp.push_back(data[lowl++]);
    }
    
    while (lowr <= highr)
    {
        tmp.push_back(data[lowr++]);
    }
    
    std::vector<int>::const_iterator iter = tmp.begin();
    
    for(; iter != tmp.end(); ++iter)
    {
        data[tmp_low++] = *iter;
    }
}

int Partition(std::vector<int> & data, int low, int high);
void QuickSort(std::vector<int> & data, int low, int high)
{
    if (low >= high) return;
    
    int p = Partition(data, low, high);
    
    QuickSort(data, low, p-1);
    QuickSort(data, p+1, high);
}

int Partition(std::vector<int> & data, int low, int high)
{
    int p = low;
    for (int i = p+1; i <= high; ++i)
    {
        if (data[i] < data[p])
        {
            swap(data, i, p);
            if (i != p+1)
            {
                swap(data, i, p+1);
            }
            p = p + 1;
        }
    }
    
    return p;
}

//O(kN) k is max number of digits
int findMaxDigits(std::vector<int> & data);
void PutInQueues(std::queue<int>  q[], int qcount, std::vector<int> & data, int digit);
void GetPartialSorted(std::queue<int>  q[], int qcount, std::vector<int> & data);

void RadixSort(std::vector<int> & data)
{
    std::queue<int> q[10];
    int maxDigits = findMaxDigits(data);
    
    for (int i = 0; i < maxDigits; ++i)
    {
        PutInQueues(q, 10, data, i+1);
        data.clear();
        GetPartialSorted(q, 10, data);
    }
}

int getDigitAt(int n, int digit);
void PutInQueues(std::queue<int>  q[], int qcount, std::vector<int> & data, int digit)
{
    std::vector<int>::const_iterator iter = data.begin();
    for(; iter != data.end(); ++iter)
    {
        int qpos = getDigitAt(*iter, digit);
        q[qpos].push(*iter);
    }
}

int getDigitAt(int n, int digit)
{
    int dig = 0;
    while (digit--)
    {
        dig = n % 10;
        n = n / 10;
    }
    return dig;
}

void GetPartialSorted(std::queue<int>  q[], int qcount, std::vector<int> & data)
{
    for (int i = 0; i < qcount; ++i)
    {
        if (q[i].size() > 0)
        {
            int length = q[i].size();
            while (length--)
            {
                data.push_back(q[i].front());
                q[i].pop();
            }
        }
    }
}

int numDigits(int n);
int findMaxDigits(std::vector<int> & data)
{
    std::vector<int>::const_iterator iter = data.begin();
    int max = 0;
    for (; iter != data.end(); ++iter)
    {
        int numd = numDigits(*iter);
        if (max < numd)
        {
            max = numd;
        }
    }
    
    return max;
}

int numDigits(int n)
{
    int count = 0;
    while(n != 0)
    {
        n = n/10;
        ++count;
    }
    
    return count;
}

int main(int argc, const char * argv[])
{
    int a[] = {5, 6, 1, 2, 0, 8, -1, -2, 8, 0};
    std::vector<int> data(a, a + sizeof(a)/sizeof(int));
    
    //Bubble sort
    BubbleSort(data);
    print(data);
    
    //Selection sort
    Shuffle(data);
    SelectionSort(data);
    print(data);
    
    //Insertion sort
    Shuffle(data);
    InsertionSort(data);
    print(data);
    
    //Merge sort
    Shuffle(data);
    MergeSort(data, 0, data.size()-1);
    print(data);
    
    //Quick sort
    Shuffle(data);
    QuickSort(data, 0, data.size()-1);
    print(data);
    
    //Radix Sort
    int b[] = {123, 6, 24, 4567, 45, 989834, 98, 23, 8, 0};
    std::vector<int> rdata(b, b + sizeof(b)/sizeof(int));
    RadixSort(rdata);
    print(rdata);
    
    return 0;
}