selection sort algorithm using vectors [closed]

Question

Closed. This question is not reproducible or was caused by typos. It is not currently accepting answers.

---

This question was caused by a typo or a problem that can no longer be reproduced. While similar questions may be on-topic here, this one was resolved in a way less likely to help future readers.

Closed 9 years ago.

Improve this question

I am trying to get the selection sort to work with vectors. I run the program and it does the first part unsorted but then says Expression: vector subscript out of range. Can't figure out what is causing it.

#include <iostream> 
#include <vector> 
using namespace std; 

template<typename Comparable> 
void selectionSort(vector<Comparable> & toSort) 
{
    int pos, min, i;

    for( pos = 0; pos < 30; ++pos)
    {
        min = toSort[pos];

        for( i = toSort[pos + 1]; i < toSort[30]; ++i)
        {   
            if( i < min)
            {
                min = i;
            }
        }

        if( min != pos)
        {   
            std::swap(toSort.at(min), toSort.at(pos));

        }
    }
}

int main(int argc, const char * argv[]) 
{ 
    const int NUM_ITEMS = 5; 
    int array[NUM_ITEMS] = { 16, 271, 77, 40, 120 }; 
    vector<int> sortingVector; 


    for(int i=0;i<NUM_ITEMS;i++) { 
        sortingVector.push_back(array[i]); 
    } 

    cout << "Before sort \n"; 

    for(int i=0;i<NUM_ITEMS;i++) { 
        cout << sortingVector[i] << "\n"; 
    } 

    selectionSort(sortingVector); 

    cout << "After sort \n"; 

    for(int i=0;i<NUM_ITEMS;i++) { 
        cout << sortingVector[i] << "\n"; 
    } 
    system("pause");
    return 0; 
}

Answer 1

Nobody knows what this magic number 30 means in your function

template<typename Comparable> 
void selectionSort(vector<Comparable> & toSort) 
{
    int pos, min, i;

    for( pos = 0; pos < 30; ++pos)
    {
        min = toSort[pos];

        for( i = toSort[pos + 1]; i < toSort[30]; ++i)

and even the function itself does not know what this magic number 30 means.

If you are using standard container std::vector then it has member function size that can always report how many elements there are in the container.

In any case if you will use size() instead of 30 the code is invalid because the inner loop will access the element with the position equal to size()

for( i = toSort[pos + 1]; i < toSort[30]; ++i)

I think there should be

for( i = pos + 1; i < toSor.size(); ++i)

This condition

if( min != pos)

is also invalid because you are comparing different entities.

The function could be defined the following way

template<typename Comparable> 
void selectionSort( std::vector<Comparable> & toSort ) 
{
    for ( std::vector<Comparable>::size_type pos = 0; pos < toSort.size(); ++pos )
    {
        std::vector<Comparable>::size_type min = pos;

        for ( std::vector<Comparable>::size_type i = pos + 1; i < toSort.size(); ++i )
        {   
            if ( toSort[i] < toSort[min] ) min = i;
        }

        if ( min != pos )
        {   
            std::swap( toSort[min], toSort[pos] );
        }
    }
}

Answer 2

for( pos = 0; pos < 30; ++pos)
{
    min = toSort[pos];

if you have to do it in this specific way then consider using NUM_ITEMS as a range check inside your sorting function instead of taking 0 to 29.

for( i = toSort[pos + 1]; i < toSort[30]; ++i)
{  

You are accessing element 30 here directly although the vector only has 5 elements. Be sure to check for pos + 1 as this may result in errors later on.