алгоритм сортировки выбором с использованием векторов

Я пытаюсь заставить сортировку выбора работать с векторами. Я запускаю программу, и она делает первую часть несортированной, но затем говорит, что выражение: векторный индекс вне допустимого диапазона. Не могу понять, чем это вызвано.

#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; 
}

c++ sorting vector selection-sort
person user3424390    schedule 13.05.2014    source источник
comment
Ваш вектор имеет размер 5, и вы относитесь к нему так, как если бы он был размером 31.   -  person juanchopanza    schedule 13.05.2014
comment
Вы хотите сказать, что не видели этого? for( pos = 0; pos < 30; ++pos), а затем вы обращаетесь к tosort[30]?   -  person PaulMcKenzie    schedule 13.05.2014
comment
см. эти вопросы и ответы для STL-стиля selection_sort с использованием итераторов   -  person TemplateRex    schedule 13.05.2014
comment
ммм, я не знаю, как я положил 30 там. Я чувствую себя идиотом. спасибо, что указали на мою глупую неудачу   -  person user3424390    schedule 13.05.2014
comment
ТАК Хороший вопрос: что означает компилятор/среда выполнения, когда он говорит X? ТАК Хороший вопрос: почему этот (очень-очень короткий, т.е. 10 строк или меньше) созданный для SO пример кода генерирует ошибку X? ТАК Плохой вопрос: я получаю ошибку времени выполнения X в этом беспорядке кода, пожалуйста, отладьте его для меня   -  person dspyz    schedule 13.05.2014
comment
Почему вы жестко кодируете размер вместо использования toSort.size()?   -  person Blastfurnace    schedule 13.05.2014
comment
доменная печь. Думаю, я новичок в этом, и да, размер имел бы больше смысла.   -  person user3424390    schedule 14.05.2014
comment
Я откатился на исходную версию. Вы полностью изменили вопрос, исправив петлю и сделав ответы устаревшими.   -  person juanchopanza    schedule 14.05.2014
comment
Хорошо, я просто пытался это исправить, чтобы не получать дублирующихся ответов. но я думаю, это имеет смысл, если все читают комментарии.   -  person user3424390    schedule 14.05.2014

Ответы (2)


arrow_upward
1
arrow_downward

Никто не знает, что означает это магическое число 30 в вашей функции.

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)

и даже сама функция не знает, что означает это магическое число 30.

Если вы используете стандартный контейнер std::vector, у него есть функция-член size, которая всегда может сообщить, сколько элементов находится в контейнере.

В любом случае, если вы будете использовать size() вместо 30, код недействителен, потому что внутренний цикл будет обращаться к элементу с позицией, равной size()

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

я думаю должно быть

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

Это условие

if( min != pos)

также недействителен, потому что вы сравниваете разные объекты.

Функция может быть определена следующим образом

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] );
        }
    }
}
person Vlad from Moscow    schedule 13.05.2014
comment
Я переключил его на 5, как и должно быть. Я не знаю, откуда я взял 30 ... но я все еще получаю сообщение об ошибке - person user3424390; 14.05.2014
comment
@ user3424390: Знаете ли вы, что std::vector знает, сколько элементов оно содержит? Используйте toSort.size(). - person Blastfurnace; 14.05.2014
comment
@ user3424390 Смотрите мой обновленный пост. - person Vlad from Moscow; 14.05.2014
comment
что делает min != pos) недействительным? мне просто нужно избавиться от всего после этого или заменить его чем-то? извините я нуб в этом - person user3424390; 14.05.2014
comment
@ user3424390 pos — это индекс, а min — это значение в каком-то другом индексе. См. мой обновленный пост заново. - person Vlad from Moscow; 14.05.2014
comment
Ух ты. это имеет абсолютный смысл. Мне нужно копнуть намного глубже в изучении этих вещей. Это помогло! Большое спасибо всем! - person user3424390; 14.05.2014

arrow_upward
0
arrow_downward 

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

если вам нужно сделать это определенным образом, рассмотрите возможность использования NUM_ITEMS в качестве проверки диапазона внутри вашей функции сортировки вместо того, чтобы принимать от 0 до 29.

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

Здесь вы напрямую обращаетесь к элементу 30, хотя вектор имеет только 5 элементов. Обязательно проверьте pos + 1, так как это может привести к ошибкам позже.

person Floris Velleman    schedule 13.05.2014