4
\$\begingroup\$

This started as a simple exercise in sorting an array. I wanted to make it a bit more complex which is why I made it a 2D array.

I then noticed that each pass that checked and swapped values, it was checking all ten values. This seemed unnecessary because with each pass the highest value gets moved all the way to its final position. So I made it check one less element each pass until it finished.

I did not want to use std::sort, this was an exercise in finding my own solution.

The program was "falling off" the end of the array, and although I managed to work around it, I'm not sure I did it in the right way, or even why it was doing it in the first place.

The program seems to work as intended but would like some feedback on how it can be improved, or any issues etc.

#include "stdafx.h"

#include<iostream>

using std::cout;
using std::cin;
using std::endl;


int main()
{
    const int ROWS = 10;
    const int COLUMNS = 2;

    int person[ROWS][COLUMNS] =
    {
        { 1,100 },
        { 2,20 },
        { 3,80 },
        { 4,10 },
        { 5,50 },
        { 6,150 },
        { 7,30 },
        { 8,60 },
        { 9,40 },
        { 10,1 } 
    };

    for (int i = 0; i < ROWS; ++i)
    {
        cout << "Person " << person[i][0] << " ate: " << person[i][1] << " pancakes";
        {
            cout << endl;
        }
    }

    // Sort lowest to highest

    int loop = 1;
    int count;           // for counting the number of loops
    int limit = ROWS;    // reduced by 1 each loop to skip uneceassary checks

    for (int j = ROWS - 1; j > 0; --j, loop++, limit--)
    {
        cout << "Loop " << loop << endl;
        cout << "Loop limit: " << limit << endl;
        count = 0;

        for (int i = 0; i < ROWS; ++i, ++count )
        {
            if (loop + count == ROWS + 1)   // skips unnecessary checks
            {
                break;
            }
            if (person[i][1] > person[i + 1][1] && i != ROWS - 1)
    // The && condition stopped the  program falling off the end of the array
    // but not sure why it was in the first place
            {
                int temp = person[i][1];
                person[i][1] = person[i + 1][1];
                person[i + 1][1] = temp;
            }
            //cout << person[i][0] << " " << person[i][1] << endl;
            //un-comment ^ to display inner loop passes
        }
        cout << "Number of inner loops: " << count << "\n" << endl;
    }

    // display final order
    for (int i = 0; i < ROWS; ++i)
    {
        cout << person[i][0] << "   " << person[i][1] << endl;
    }

    int pause;
    cin >> pause;

    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ (Welcome to Code Review!) wanted to make it a bit more complex say challenging. \$\endgroup\$ – greybeard Jan 5 at 19:11
  • \$\begingroup\$ Making the array "2 Dimensional" does not make the sorting harder (or more interesting). \$\endgroup\$ – Martin York Jan 5 at 19:29
6
\$\begingroup\$

The are lots of different sorting algorithms out there. You seem to have re-implemented "Bubble Sort". This is one of my favorite algorithms as it is very easy to write and sufficient (or even preferable) for very small data sets.

The problem with bubble sort is that it has a very bad complexity so when the data sets become large it becomes very expensive and there are other much better algorithms for large data sets.

Overview

This started as a simple exercise in sorting an array.

Good thing to work on when you are a beginner.

I wanted to make it a bit more complex which is why I made it a 2D array.

I don't think this adds anything to the problem. One of the main concepts of computer science is abstraction. In sorting we usually abstract the comparison out so that it simply becomes a comparison operation (usually less than i.e. operator<). If you abstract out the comparison you are simply left with the sorting algorithm (which then is the same for every type). So you should have written a less than operation and then you could have re-used the sorting algorithm for any type.

I then noticed that each pass that checked and swapped values, it was checking all ten values. This seemed unnecessary because with each pass the highest value gets moved all the way to its final position. So I made it check one less element each pass until it finished.

This is a standard optimization for "Bubble Sort". Unfortunately it does not reduce the complexity that much. Still making this the worst sort for large data sets.

One other optimization (which is a very make Bubble Sort great) is that if you do a full inner loop and there was not a single swap then the array is sorted. You can not break out of the outer loop. This optimization is great as it turns the best case situation (where the data is already sorted (or very close to sorted)) into an O(n) (i.e. linear) operation.

I did not want to use std::sort, this was an exercise in finding my own solution.

Yes. Experimenting with sorting is good. But you should read up on the different types of algorithm and try and re-implement them. Doing this is great experience and will teach you the advantages of the different types.

The program was "falling off" the end of the array, and although I managed to work around it, I'm not sure I did it in the right way, or even why it was doing it in the first place.

Can't help with that unless I see the code from before your fix. But even if you did this is the wrong site for that. We only review working code.

OK. I found the the bug you mentioned (and fixed). It seems like a common one so I will talk about that below.

The program seems to work as intended but would like some feedback on how it can be improved, or any issues etc.

OK. Lets have a look.

Code Review

Your Bug:

    if (person[i][1] > person[i + 1][1] && i != ROWS - 1)
    // The && condition stopped the  program falling off the end of the array
    // but not sure why it was in the first place

So you have a loop:

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

This will allow you to loop over the array so you can accesses all the elements with person[i]. Where ROWS is the number of rows in the array. So this allows you to access all the valid rows. Remember that valid rows in an array are counted from 0 so the last valid row is ROWS - 1 (this is why most loops use less than operator< as you do in the loop test.

The problem is that you also accesses the element person[i + 1]. The largest value of i is ROW-1 so the largest element accessed is person[ROW-1+1] or person[ROW] that is one past the end of the array.

int  array[3] = {1,2,3};
std::cout << array[0];   // first  element
std::cout << array[1];   // second element
std::cout << array[2];   // third  element
// Only 3 elements in the array
std::cout << array[3];   // This is one beyond the end.

Abstraction and self documenting code

Pull out simple pieces of code into their own well named function. This documents what you are doing and makes the underlying algorithm easier to read.

            {
                int temp = person[i][1];
                person[i][1] = person[i + 1][1];
                person[i + 1][1] = temp;
            }

This is obviously a swap. Why not write a function called swapPerson(person[i], person[i+1]); that swaps the values of two people. This will make the sort algorithm easier to read. This also moves the actual swapping processes out of the algorithm allowing you to more easily replace it with another one when you use a different type.

Note: This is so common that the standard library has a std::swap() that swaps two values of a the same type.

Now looking at the comparison:

            if (person[i][1] > person[i + 1][1])

Your code is comparing two elements adding the extra [1] on the end does not change much. But I would change it so that I was comparing two people.

             if (lessPerson(person[i + 1], person[i]) {
             }

Still looks a bit ugly. But it shows you can use a function to do the test. But C++ lets you define functions that look like maths operations. So you can change the named lessPerson() function into operator<() function that allows you to compare two people.

             if (person[i + 1] < person[i]) {
             }

Optimizing the loop

        for (int i = 0; i < ROWS; ++i, ++count )
        {
            if (loop + count == ROWS + 1)   // skips unnecessary checks
            {
                break;
            }

This seems like a very complex way of writing:

        for (int i = 0; i < j; ++i) {

Now if we look at your sort Algorithm after these changes:

    for (int j = ROWS - 1; j > 0; --j) {
        for (int i = 0; i < j; ++i) {
            if (person[i + 1] < person[i + 1]) {
                std::swap(person[i], person[i+1]);
            }
        }
    }

Boiled Down Code.

We seem to have boiled down your code to the absolute minimum. I would add the optimization I mentioned above and wrap this in its own function to make it:

void sort(Person person[], int const ROWS)
{
    for (int j = ROWS - 1; j > 0; --j) {
        bool swapped = false;
        for (int i = 0; i < j; ++) {
            if (person[i + 1] < person[i + 1]) {
                swapped  = true
                std::swap(person[i], person[i+1]);
            }
        }
        if (!swapped) {
            break;
        }
    }
}

Notice I have added the type Person so can explicitly write functions to swap and compare objects of type Person. Now you can write a less than (operator<) and assignment (operator= used by std::swap) specifically for people that would allow the algorithm to work without having to be specific to the algorithm.

The next step is then to make the sort work for any type. Usually we do this with templates. So we can pass any type into the sort function and allow it to be sorted (as long as the type has an operator< and an operator=).

template<typename T>
void sort(T array[], int const ROWS)
{
    for (int j = ROWS - 1; j > 0; --j) {
        bool swapped = false;
        for (int i = 0; i < j; ++) {
            if (array[i + 1] < array[i + 1]) {
                swapped  = true
                std::swap(array[i], array[i+1]);
            }
        }
        if (!swapped) {
            break;
        }
    }
}

The next step is to learn about the concepts of Iterators and how that can make the above function even more useful. But I will leave that as an exercise for now.

Bad Habits

Please don't do this:

using std::cout;
using std::cin;
using std::endl;

Is it that much harder to write std::cout over cout? This is a kind of habit that will get you into a lot of trouble. Especially when you put using at the top level of a file. If you must do this, do it inside a function so it does not pollute the code.

Not sure what the extra level of braces is for.

        {
            cout << endl;
        }

But prefer to use '\n' rather than std::endl. The only difference is that std::endl performs a forced flush of the stream. The stream will auto flush so there is no need to force a flush to start with. Also manually flushing the stream (by the programmer) is nearly always going to cause sub optimal flushing and lead to performance degradation.

You don't need a return 0 in main().

    return 0;
\$\endgroup\$
  • \$\begingroup\$ Thank you Martin, that was the type of response I was hoping for. I know a 2D array isn't really that much more complicated, but I suppose it's hard to remember what it feels like to be a beginner ;) Wait... No "return 0"? That's a new one to me, you'll have to expand on that one. \$\endgroup\$ – MrSteve Jan 6 at 0:09
  • 1
    \$\begingroup\$ @MrSteve In main() as it is special (for C++ only). The compiler automatically plants a return 0 at the end. Thus it is common when an application has no other error states to NOT explicitly put a return 0 to indicate that that the application has no error state. Conversely if you see a manual return 0 at the end of main you are implying there are other error states and programmers will look for other returns in the main() function. \$\endgroup\$ – Martin York Jan 7 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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