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

Question

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

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

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

-4

c++selection-sort sorting vector

Решение

Другие решения

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 как это может привести к ошибкам позже.

0

Источник

Accepted Answer

Никто не знает, что это магическое число 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 ()

для (я = toSort [pos + 1]; я < toSort [30]; ++ я)

Я думаю, что должно быть

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] );
}
}
}

1