Написание сортировки выбора для списка STL?

Question

Я пишу определенную программу на c ++ для использования сортировки выбора в списке STL, как того требует мой профессор.

Я использую Netbeans 9.2. В настоящее время я застрял с моим алгоритмом. Первые несколько раз программа компилируется, но список после выбора всегда заканчивается одинаковыми значениями (скажем, это должно было быть 99, 24, 15, 80, 27, это всегда будет 1, 1, 1, 1, 2 после сортировки). Теперь алгоритм прямо вверх не будет компилироваться. Я относительно новичок в кодировании. Может кто-нибудь сказать мне, что я ошибся и как мне это сделать? Большое спасибо!

Вот мой код:

void selectionSort(list<short> l, int size) {
    list<short>::iterator it1;
    list<short>::iterator it2;
    list<short>::iterator it3;
    short min, temp; 
    for(it1 = l.begin(); it1 != l.end(); it1++) {
        temp = min = *it1;
        it2 = it1;
        for(it2 = it1; it2 != l.end(); it2++) {
            if(*it2 < min) {
                min = *it2;
                it3 = it2;
            }    
        }
        *it1 = min;
        *it3 = temp;
        //Increment the first counter at the end
        temp = min = *it1;
    }
}

Answer 1

В вашем коде есть ошибка, которая может привести к сбою.Я исправил это в следующем коде.

Но я до сих пор не знаю, почему он выводит странные числа, такие как 1, 1, 1, 1, 2. Возможно, это вызвано остальной частью вашего кода.Было бы полезно, если бы можно было предоставить больше кода или информации.

void selectionSort(list<short> l, int size) {
    list<short>::iterator it1;
    list<short>::iterator it2;
    list<short>::iterator it3;
    short min, temp;
    for(it1 = l.begin(); it1 != l.end(); it1++) {
        temp = min = *it1;
        it2 = it1;
        it3 = l.end();  // NOTE: to fix the bug
        for(it2 = it1; it2 != l.end(); it2++) {
            if(*it2 < min) {
                min = *it2;
                it3 = it2;
            }
        }
        if (it3 != l.end()) {  // NOTE: to fix the bug
            *it1 = min;
            *it3 = temp;
        }  // NOTE: to fix the bug
        //Increment the first counter at the end
        temp = min = *it1;  // NOTE: This is unnecessary
    }
}

Answer 2

Вы передаете параметр l по значению, а не по ссылке. Вот почему манипуляции, которые вы выполняете в функции selectionSort, не изменяют список. Вот версия, которая работает:

#include <iostream>
#include <list>

void selectionSort(std::list<short>& l) {
  std::list<short>::iterator it1;
  std::list<short>::iterator it2;
  std::list<short>::iterator it3;
    short min, temp;
    for(it1 = l.begin(); it1 != l.end(); it1++) {
        temp = min = *it1; 
        it3 = l.end();
        for(it2 = it1; it2 != l.end(); it2++) {
            if(*it2 < min) {
                min = *it2;
                it3 = it2;
            }
        }
        if (it3 != l.end()) {
            *it1 = min;
            *it3 = temp;
        }
    }
}

int main()
{
  std::list<short> mylist= {10,1,8,13,14,7,6,5,18,9,19,12,17,15,4,2};
  selectionSort(mylist);
  std::list<short>::iterator it;
  std::cout << "elements in list\n";
  for (it = mylist.begin(); it != mylist.end(); it++) {
      std::cout << *it << std::endl;
    }
  return 0;
}

Короче говоря, вам нужно добавить & после типа l в объявлении вашей функции selectionSort.

Обновление

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