### Sorting algorithms implemented in C++

• Medicine

10 years ago

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

``#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 sortedvoid 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 swapsvoid 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 elementsvoid 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 digitsint 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;  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;}``

• 10 years ago

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); 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.