CODEWITHSUNDEEP
c++listsortingstliterator
Jason
Jason

Reputation: 51

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

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: Output from running program.

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.

Upvotes: 0

Views: 819

Answers (1)

Tony Delroy
Tony Delroy

Reputation: 106136

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.

Upvotes: 5

Related Questions