Выполнение выбора Сортировка для связанных списков

Question

Я пытаюсь реализовать алгоритм сортировки выбора, который будет работать со связанными списками и будет использовать итераторы для прокрутки через них. Алгоритм сортировки выбора выглядит следующим образом: для каждого элемента списка, кроме последнего (назовем его K), он будет искать наименьшее значение из позиции, в которой мы сейчас находимся (поэтому он начнется с K до последнего элемента). После этого будет swap K and the smallest element.

Я думаю, что моя ошибка в первом цикле; Я очень не уверен, что --a.end() является последним элементом. Я получаю некоторый результат, хотя это неправильно.

#include <iostream> 
#include <list> 

using namespace std; 

void sort_list(list<int>& a) 
{ 
    //from the first until the pre-last element 
    for(list<int> :: iterator itr = a.begin(); itr != (--a.end()); ++itr) 
    { 
      int smallest = *itr; 

     //get smallest element after current index 
     list<int> :: iterator itr2 =itr; 
      ++itr2; 
    for(; itr2 != a.end(); ++itr2) 
     { 
       if (smallest > *itr2) 
        { 
         smallest = *itr2; 
        } 
     } 
     //swap smallest and current index 
     int tmp = *itr; 
     *itr = smallest; 
     smallest = tmp; 
    } 
} 

int main() 
{ 
    //create a list and some elements 
    list<int> listi; 
    listi.push_back(5); 
    listi.push_back(4); 
    listi.push_back(3); 
    listi.push_back(2); 
    listi.push_back(1); 

    // sort the list 
    sort_list(listi); 
    //print all of the elements 
    for(list<int> :: iterator itr = listi.begin(); itr != listi.end(); ++itr) 
    { 
      cout << *itr << endl; 
    } 

    return 0; 
} 

Answer 1

Когда вы делаете itr2 = ++itr вы также изменить значение itr, так что вместо этого вы должны сделать что-то вроде

list<int> :: iterator itr2 = itr; 
for(++itr2; itr2 != a.end(); ++itr2) { 
    ... 
} 

Кроме того, вы должны держать указатель на наименьший элемент, если вы хотите поменять его позже , как это:

int* smallest = &(*itr); 

Это также требует некоторых других изменений, вы можете найти рабочий пример кода here.

Answer 2

Проблема заключается в том портите itr при инициализации itr2.