Gfrktyl

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;

}

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 complicity 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] then is one passed 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;