Реализация сортировки выбора с векторами

Question

Я пытаюсь реализовать функцию, которая сортирует случайно сгенерированный вектор, используя сортировку выбора. Я пытаюсь наивным способом просто посмотреть, смогу ли я заставить его работать правильно. Вот моя попытка:

void selection_sort(std::vector<int>& v)
{
    int pos, min, i;
    //std::vector<int>::iterator pos, min, i;

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

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

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

        }
    }
}

Однако по какой-то причине, когда я снова отображаю вектор, все элементы находятся в том же порядке, в котором они были изначально. Я не уверен, правильно ли я использую std::swap или сортировка моего выбора написана неправильно. Я уверен, что ответ тривиально прост, но я не вижу его. Заранее спасибо за помощь.

Answer 1

Ваша проблема в том, что вы пытаетесь основывать свои циклы на фактических значениях в векторе, а не на индексах в векторе.

Так что, если ваш вектор генерируется случайным образом, и вы говорите это:

for( pos = v[0]; pos < v[30]; ++pos)

Есть вероятность, что значение в v [0] больше, чем v [30]. Таким образом, цикл никогда не будет работать. Я вижу ту же проблему в этом цикле:

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

Так что я бы рекомендовал использовать индексы для реального цикла. Попробуйте что-то вроде:

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

и т.д ...

РЕДАКТИРОВАТЬ: Как упомянуто ниже, было бы также лучше, чтобы ваш цикл основывался на размере вектора. Однако, чтобы уберечь себя от вызова дорогостоящего метода size () при каждом запуске цикла, просто захватите размер до начала цикла. Например:

size_t size = v.size();
for(size_t pos = 0; pos < size; ++pos)

Answer 2

Вы должны использовать 0, pos+1 и v.size() в качестве конечных точек в своих for -петлях.