Implementing Selection Sort for Linked Lists

Question

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

ValarDohaeris-fuck-OpenAI · Accepted Answer · 2013-04-29 14:34:53Z

1

When you do itr2 = ++itr you also change the value of itr, so instead you should do something like

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

Furthermore, you have to keep a pointer to the smallest element, if you want to swap it later, like this:

 int* smallest = &(*itr);

This also requires some other changes, you can find a working example of your code here.

answered Apr 29, 2013 at 14:34

ValarDohaeris-fuck-OpenAI

6,3885 gold badges34 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

eugene_che · Accepted Answer · 2013-04-29 14:24:47Z

1

The problem is you spoil itr while initializing itr2.

answered Apr 29, 2013 at 14:24

eugene_che

1,99712 silver badges12 bronze badges

1 Comment

Stanimirovv Over a year ago

I changed the code to: list<int> :: iterator itr2 =itr; ++itr2; for(; itr2 != a.end(); ++itr2) however now I get only 1's Edit: I edited the original code with the parcial solution we have at the moment

Collectives™ on Stack Overflow

Implementing Selection Sort for Linked Lists

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related