0

I am trying to implement a selection sort algorithm that will work with linked lists and will use iterators to scrool through them. The selection sort algorithm is the following: for each element of the list except the last one(let's call it K), it will seek out the smallest on from the position we are currently on(so it will start from K until the last element). After that it will swap K and the smallest element.

I think that my mistake is in the first for loop; I am very unsure that --a.end() is the pre-last element. I get some output, though it is wrong.

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

2 回答 2

1

当你这样做时，itr2 = ++itr你也会改变 的值itr，所以你应该做类似的事情

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

此外，如果您想稍后交换它，您必须保留一个指向最小元素的指针，如下所示：

 int* smallest = &(*itr);

这还需要一些其他更改，您可以在此处找到代码的工作示例。

于 2013-04-29T14:34:53.113 回答
1

itr问题是你在初始化时破坏了itr2。

于 2013-04-29T14:24:47.887 回答