Sorting algorithms implemented in C++

  • Implemented
    Bubble Sort, Insertion Sort, Selection Sort,
    Quick Sort, Merge Sort and
    Radix Sort



    https://code.google.com/p/medicine-cpp/source/browse/trunk/cpp/sorting/SortingAlgorithms.cpp



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

  • Starting from (close to) the top, most of your print is basically just a somewhat crippled imitation of std::copy with a std::ostream_iterator as the destination. I'm not excited about its existing at all, but if you're going to have it, I'd use something like this:



    void print(std::vector<int> const &data) { 
    if (!data.empty())
    copy(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    }
    }


    Although it's rarely a matter of much importance, also note that if you're just checking for empty/non-empty, using x.empty() is usually preferable to x.count()!=0.



    Getting to GenerateRandom() and shuffle, @Tux-D has something of a point, but he's stated it incorrectly.



    The way you've used srand doesn't seem very sensible, but in some cases (probably including this one) it can/does make sense to call it more than once in a particular program. In this case, it does make at least some sense to start each sort algorithm with exactly the same input sequence. To do that, however, you want to re-seed the random number generator once before you generate each sequence (and use the same value each time). As @Tux-D also pointed out (but correctly, in this case) you usually want to do this with std::random_shuffle. random_shuffle takes a random-number generating object as a parameter, so you'd normally want to write a small class that calls srand, and provides an operator() that provides the random numbers.



    Getting to the bubble-sort, there's one point worth mentioning: this is the version with an early-out test. That's worth mentioning, because it's a bit of a gamble: while it improves speed quite a lot if the data is already sorted (or very close to sorted) it makes what's already a slow algorithm even slower in nearly every other case. As such, it's generally a net loss unless the data really is quite close to sorted.



    For the selection sort, it's probably worth noting that the standard library already has a min_element, so you can reduce your selection sort to something like:



    for (size_t i=0; i<length-1; i++) {
    size_t least = std::min_element(&data[i], &data[length]);
    swap(&data[i], &data[least]);
    }


    The insertion sort can also be minimized considerably. The basic idea is pretty simple:



    for (size_t i=1; i<length; i++)
    int temp = data[i];
    size_t j;
    for (j=i; j>0 && temp < data[j-1]; j--)
    data[j] = data[j-1];
    data[j-1] = temp;
    }


    Getting to the merge-sort, I notice two things: first, it looks to me like it should be written as a function-object, with merge as a private member function (and note that the same applies in other cases as well, such as partition as a private member function of a quicksort function object). Other than that, I'm still left scratching my head wondering how a merge ended up nearly 40 lines long.



    std::vector<int> merge(std::vector<int> &a, std::vector<int> &b) {
    std::vector<int> result;
    size_t i=0, j=0;
    while (i<a.size() && j<b.size())
    if (a[i] <= b[j])
    result.push_back(a[i++]);
    else
    result.push_back(b[j++]);
    // Copy tail. Only one of these loops will execute per invocation
    while (i<a.size())
    result.push_back(a[i++]);
    while (j<b.size())
    result.push_back(b[j++]);
    return result;
    }


    Other than that, I'd probably start with a base class (sort, or something on that order):



    struct sort { 
    virtual void operator()(std::vector<int> &) = 0;
    };


    and have each sort algorithm derive from that:



    struct bubblesort : sort {
    void operator()(std::vector<int> &array) {
    // ...
    }
    };

    struct insertionsort : sort {
    void operator()(std::vector<int> &array) {
    // ...
    }
    };

    // etc.


    Then in main, you can have something like:



    sort sorts[] = {bubblesort, insertionsort, selectionsort, mergesort, quicksort};

    for (int i=0; i<sizeof(sorts)/sizeof(sorts[0]); i++) {
    std::vector<int> data = fill_random(size);

    sorts[i](data);
    }

    DOn't agree that I was wrong about srand(). In the general case you should only be calling it once. If you are doing testing and want to repeatedly get the sane random sequence then fine you can re-use it (with he same seed). But let teach beginners basics first before we start getting them onto advanced techniques.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM