CODEWITHSUNDEEP
c++arrayssortinglogic
josephshanks7
josephshanks7

Reputation: 35

Logical error in a C++ selection sort algorithm?

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?

Upvotes: 0

Views: 175

Answers (2)

Ta_Req
Ta_Req

Reputation: 106

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

Upvotes: 1

Adrisui3
Adrisui3

Reputation: 94

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!

Upvotes: 1

Related Questions