Sorting algorithms implemented in C++

Question

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

Jerry Coffin · Accepted Answer · 2011-09-05 03:48:43Z

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. — Loki Astari, Commented Sep 5, 2011 at 18:34

Loki Astari · Accepted Answer · 2011-09-04 18:50:07Z

Standard functions

There is already a standard swap.
No need o pollute your code with one.

void swap(std::vector<int> & data, int i, int j)

template<typename T>
void std::swap(T& lhs, T& rhs) // Implements optimal swap for T

OK your shuffle algorithm is ok (better than most people I see try this). But again there is one in the standard

void Shuffle(std::vector<int> & data)

template<typename Iterator>
void random_shuffle (Iterator first, Iterator last ); // shuffle a container.

Random numbers

Random nmber generation.
NEVER call srand() more than once in a program.
Call it on entry to main and never again.

Don't reinvent the wheel:

int numDigits(int n)

Is this just not implementing

int numDigits(int n) { return int(log10(n) + 1);}

Variable Names

Make your variables names unique and easy to find.

for (int i = 0; i < length; ++i)

Here i is a horrible name.
Imagine the code gets longer over the years and you need to maintain it. Now you need to find all occurences of the variable 'i' to validate that they are being used in the correct array. Think of how many falso positives a search on i is going to give you.

Also it gives no indication as to its use.
I like loop personally (But a lot of people think this is horrible because it does not expresses intention (I disagree with them)). Alternatives would be index, outerLoop etc.

Yes i and 'j` were standard variable names for integer loop variables in fortran and old lecturers who can not get out of the old practice have carried this forward into their teaching of modern languages. In real life where you have good consistent code reviews this would fail a code review and you would be told go go change it (especially on big code bases). Get into the habit of using expressive names.

Indent Style

Your indent style is unique. That is bad. Pick a style that everybody else uses (or one of the big religious groups) but stay consistent (this also helps when tools get involved having a unique style means the some tools may not work as effectively for you).

// Style 1
  if (max < numd)
  {
      max = numd;
  }
// Style 2
  if (max < numd)
      {
      max = numd;
      }
// Style 3
  if (max < numd) {
      max = numd;
  }
// Not a standard style
  if (max < numd)
    {
      max = numd;
    }

And it does not match your outer style:

int numDigits(int n)
{
}

why NEVER call srand() more than once? does it take too much time? — Medicine, Commented Sep 4, 2011 at 18:06
@Medicine: No. You are only supposed to call it once. If you call it more than once you ruin the random numbers (as you are restarting the sequence). Thus if you call it before rand() each time you are NOT getting random numbers. It's NEVER because all beginners do this and get its irritating to tell them again and again and again and again .... — Loki Astari, Commented Sep 4, 2011 at 18:41
I use style1 at work which is taken care by my .emacs. at home I use Mac and I have Aquamacs whose default indentation is what I am using..the non-standard style. — Medicine, Commented Sep 4, 2011 at 18:48

Deduplicator · Accepted Answer · 2021-01-12 23:26:59Z

It might be suitable for something like a homework exercise in a data structures class, but my biggest objection to this is you've tied everything to sorting the entirety of a std::vector. One of the strengths of the STL iterator approach and what you might find in the <algorithm> header is that you can fairly easily replace the backing data structure. If you specify the data to be sorted as a "begin" and an "end" iterator, you get all this for free:

Sorting the entirety of a vector
Sorting just a range of a vector
Replacing that vector with a raw C array. Same sorting code works!
... Or some other data structure you might not have envisioned.
Most importantly, being able to do all the above while producing binary code that beats what you'd write doing generics in plain C.

The C++ iterator syntax looks strange and counter-intuitive to many... Many people writing C++ don't really understand the benefits; I myself was writing C++ for a long time without really getting it. I think the turning point for me was reading Stroustrup's HOPL-III paper; as a longtime (ab)user of the "C-style" the parts about STL were helpful for me to clearly explain the approach, where it comes from, and the benefits.

Stack Exchange Network

Sorting algorithms implemented in C++

3 Answers 3

Standard functions

Random numbers

Don't reinvent the wheel:

Variable Names

Indent Style

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
algorithm
sorting
or ask your own question.

Hot Network Questions

Sorting algorithms implemented in C++

3 Answers 3

Standard functions

Random numbers

Don't reinvent the wheel:

Variable Names

Indent Style

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++algorithmsorting or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c++
algorithm
sorting
or ask your own question.