Sorting list using iterators won't sort last element C++

Question

so I'm trying to sort a list of lists. Inside of each sublist the elements are classes that contains a runtime. This is the integer variable I am using to sort my list.

However, the list will not 100% sort itself if the smallest runtime is at the end of the list. I have a attached an image below of the terminal output for visualization.

Here is the code:

void sort( list<list<MetaData> > &omegaList )
{
// variables
list<list<MetaData> >::iterator cursor = omegaList.begin();
list<list<MetaData> >::iterator ptr    = omegaList.begin();
list<list<MetaData> >::iterator end    = omegaList.end();

// start the bubble sort...
for(; cursor != end; cursor++)
{
    // iterate through the list
    for(; ptr != end; ptr++)
    {
        // compare runtimes of different lists
        if( ptr->front().getProcessRunTime() < cursor->front().getProcessRunTime() )
            {
            // swap locations of lists in omegaList
            swap( *ptr, *cursor );
            // reset
            cursor = ptr = omegaList.begin();
            }
        }
    }
}

And the output:

If anybody could please explain to me WHY it won't look at the very last element and then tell me how to fix it I would appreciate it.

I'm not sure where your bug is, but I think your bubble sort implementation is incorrect. — Jason
– Jason, Commented Oct 28, 2015 at 3:38
Eh, it was just more or less a "this is horribly inefficient like bubble sort so I'm just going to call it bubble sort." — Jason
– Jason, Commented Oct 28, 2015 at 3:41
Good question. I didn't know about it and I'm not sure how I would implement it given that I have a list of lists and it is the sublists that need to be sorted within the larger list. — Jason
– Jason, Commented Oct 28, 2015 at 3:54

Tony Delroy · Accepted Answer · 2015-10-28 04:05:12Z

5

The proper way to do the sort is with std::list::sort as follows:

omegaList.sort(
    [](const list<MetaData>& lhs, const list<MetaData>& rhs) {
       return lhs.front().getProcessRunTime() <
              rhs.front().getProcessRunTime();
});

You can see that run here.

In your bubble sort, the reason your first element is not getting sorted is that as soon as you find an out-of-order element, you do this...

cursor = ptr = omegaList.begin();

...then the ptr++ for-loop operation kicks in and your sorting therefore restarts at begin() + 1. That cursor = ptr = omegaList.begin(); is pretty wild - first O(n^3) sort implementation I've ever seen.

edited Oct 28, 2015 at 4:05

answered Oct 28, 2015 at 3:46

Tony Delroy

107k16 gold badges188 silver badges265 bronze badges

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

5 Comments

Claudiu Over a year ago

Nice, forgot that you can't use std::sort on std::lists

Tony Delroy Over a year ago

@Claudiu: be nice if it were specialised to call through to std::list::sort, but AFAIK that hasn't been done; I haven't thought through the implementation issues to know whether it's practical though.

Claudiu Over a year ago

Yeah. This is one of the many design decisions of C++ that saddens me - 99% of the time I'm doing some_function(x.begin(), x.end(), ...), it would be cleaner IMO to do some_function(x, ...) instead. Especially relevant if x is anything but the shortest expression. And to your point, it would then allow std::sort to specialize through to std::list::sort.

Tony Delroy Over a year ago

@Claudiu: it's a longstanding, niggling hassle, but at least the range proposal should fix it soonish.

Jason Over a year ago

Haha, glad I could surprise you and glad you could guide me on the correct path. I knew it was a bad algorithm (like really bad) but I'm more worried about getting this program written than how long it takes to execute. I was planning on rewriting it tomorrow via a better implementation but now you've shown me these gold mine. Thank you so much.

Collectives™ on Stack Overflow

Sorting list using iterators won't sort last element C++

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related