Selection sorting. not getting the required output-CodePudding

What is wrong with this code? Not getting the right output.

void selectionSort(vector<int>& arr, int n)
{   
       for(int i = 0; i < n-1; i   )
       {   
           int min = arr[i];
           for(int j = i 1; j < n; j  )
           {
               if(arr[j] < min)
                   min = arr[j];
           }
           swap (min, arr[i]);
       }
}

CodePudding user response：

You are using the local variable min in the swap where you needed to use the vector element.

swap(arr[index_min], arr[i]) // `index_min` is the index of the current min value.

CodePudding user response：

The variable min stores the value of the element arr[i]

int min = arr[i];

After this call of the function swap

swap (min, arr[i]);

the value stored in the element arr[i] can be lost. You need to swap values of two elements of the vector.

Also the second parameter of the function only confuses.

void selectionSort(vector<int>& arr, int n)

For example the vector can have less elements than the value of n.

Either declare the function like

void selectionSort(vector<int>& arr );

and use the member function size() to determine the number of elements in the vector.

Or declare the function like

void selectionSort( std::vector<int>::iterator first, 
                    std::vector<int>::iterator last );

Or declare the function as a template function that uses forward iterators.

Here is a demonstration program.

#include <iostream>
#include <utility>
#include <vector>
#include <iterator>

void selectionSort( std::vector<int> &v )
{
    for ( std::vector<int>::size_type i = 0; i < v.size(); i   )
    {
        auto min_i = i;
        for ( auto j = i   1; j < v.size(); j   )
        {
            if ( v[j] < v[min_i] ) min_i = j;
        }

        if ( min_i != i ) std::swap( v[i], v[min_i] );
    }   
}

int main()
{
    std::vector<int> v = { 9, 7, 6, 5, 4, 3, 2, 1, 0 };

    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    selectionSort( v );


    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

The program output is

9 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 9

Or if to use iterators then the function can look the following way as shown in the demonstrative program below.

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

template <typename ForwardIterator>
void selectionSort( ForwardIterator first, ForwardIterator last )
{
    for ( ; first != last;   first )
    {
        auto min_it = first;

        for ( auto next = std::next( first ); next != last;   next )
        {
            if ( *next < *min_it ) min_it = next;
        }

        if ( min_it != first ) std::iter_swap( min_it, first );
    }   
}

int main()
{
    std::vector<int> v = { 9, 7, 6, 5, 4, 3, 2, 1, 0 };

    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';

    selectionSort( std::begin( v ), std::end( v ) );


    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

Again the program output is

9 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 9

Using iterators you can sort any subrange of a vector.

Instead of the inner for loop in the function definition above you can use standard algorithm std::min_element. In this case the function will look the following way

template

template <typename ForwardIterator>
void selectionSort( ForwardIterator first, ForwardIterator last )
{
    for ( ; first != last;   first )
    {
        auto min_it = std::min_element( first, last );

        if ( min_it != first ) std::iter_swap( min_it, first );
    }   
}