Logical error in a C++ selection sort algorithm?

Question

I'm brand new to C++ and am trying to write this simple selection sort function. Apologies if the answer is simple to the more experienced coders, but I am beginner and have been staring at this for a long time to no avail. Here is my code:

#include <iostream>
#include <array>
using namespace std;
array<int, 10> unsorted {3, 4, 1, 5, 7, 2, 8, 9, 6, 0};

void printarray(array<int, 10> arr) {
    int count = 0;
    for (int i : arr) {
        if (count < arr.size()-1) {
            cout << i << ", ";
        } else {
            cout << i << endl;
        }
        count++;
    };
}

int selection_sort(array<int, 10> arr) {
    int test;
    array<int, 10> newarr;
    for(int j = 0; j < arr.size(); j++) {
        test = arr[j];
        for(int i = j; i < arr.size(); i++) {
            if(arr[i+1] < test) {
                test = arr[i];
            }
        }
        newarr[j] = test;
    }
    printarray(newarr);
    return 0;
}


int main() {
    selection_sort(unsorted);
    return 0;
}

When I run this function it prints an int array containing 10 zeros. Is there an error with the way I am assigning values to the array (in C++), or rather is there a problem with the logic itself?

It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: How to debug small programs and Debugging Guide — NathanOliver
– NathanOliver, Commented Feb 24, 2020 at 22:38
What are the values in arr? If the smallest value is at the end of arr it will be copied into every element — Alan Birtles
– Alan Birtles, Commented Feb 24, 2020 at 22:39
In addition to NathanOliver's suggestion about debugging, we need a minimal reproducible example to answer your questions. This should include a main() function that illustrates how you call the selection_sort() function. — Code-Apprentice
– Code-Apprentice, Commented Feb 24, 2020 at 22:39
@AlanBirtles As a matter of fact the last value is a zero! the values of arr are {3, 4, 1, 5, 7, 2, 8, 9, 6, 0}. That absolutely makes sense now, I see the logical error there, thanks! — josephshanks7
– josephshanks7, Commented Feb 24, 2020 at 22:46
Some Bad at if(arr[i+1] < test). When i reaches its maximum value of arr.size() - 1, arr[i+1] will be out of bounds. — user4581301
– user4581301, Commented Feb 24, 2020 at 23:04

Ta_Req · Accepted Answer · 2020-03-11 00:08:08Z

1

Both of the implementations are wrong. I just corrected @Adrisui3's answer. Correct solution:

#include<iostream>
#include<vector>

using namespace std;

int main()
{   
    vector<int> array(5);
    int aux;

    array[0] = 10;
    array[1] = 2;
    array[2] = 45;
    array[3] = -5;
    array[4] = 0;

    for(int i = 0; i < array.size(); i++)
    {
        int min = i;
        for(int j = i+1; j < array.size(); j++)
        {
            if(array[j] < array[min])
            {
                min = j;

            }
        }

        if (i != min)
        {
            aux = array[i];
            array[i] = array[min] ;
            array[min] = aux;
        }
    }
    for(int k = 0; k < array.size(); k++)
    {
        std::cout << array[k] << std::endl;
    }

}

Reference : wikipidia

answered Mar 11, 2020 at 0:08

Ta_Req

1066 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Adrisui3 · Accepted Answer · 2020-02-25 00:34:54Z

1

That's quite a strange way to implement Selection Sort. You've made several mistakes there, as far as I can see. First of all, you can't use arr.size() in the first for loop, as it would cause the second one to just go off the limits, which causes unexpected behaviour. If by chance those were regular arrays you'd get a nice segmentation fault. Even though you don't get a run-time error, that's something you need to be aware of. On the other hand, the main problem here is caused by the way in which you are using indexes, as well as the fact that you don't really need a second array.

Here you have an example of this algorithm.

#include<iostream>
#include<vector>

using namespace std;

int main()
{   
    vector<int> array(5);
    int aux;

    array[0]=10;
    array[1]=2;
    array[2]=45;
    array[3]=-5;
    array[4]=0;

    for(int i=0; i<array.size()-1; i++)
    {
        for(int j=i+1; j<array.size(); j++)
        {
            if(array[j]<array[i])
            {
                aux=array[j];
                array[j]=array[i];
                array[i]=aux;
            }
        }
    }
}

Aditionally, I'd recommend you to use vector instead of array, both are STL's containers, but vector is way more flexible and useful, although it consumes some extra memory.

I hope my answer was clarifying enough. I'm here if you need any extra help. Good luck!

edited Feb 25, 2020 at 0:34

answered Feb 24, 2020 at 23:30

Adrisui3

941 silver badge8 bronze badges

1 Comment

Adrisui3 Over a year ago

Hey! You're right, vector consumes more memory! My bad, sorry.

Collectives™ on Stack Overflow

Logical error in a C++ selection sort algorithm?

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related