CODEWITHSUNDEEP
c++listsorting
Juiceyboxers
Juiceyboxers

Reputation: 1

C++ Best way to sort a linked list in place?

I have a linked list of elements with a texture index. They are unsorted. I need them sort them so that the texture index is ascending in order. I could always declare another list and read into that but I am curious about ways to sort in place. Anyone have a suggest or link of where I should start/what I should start looking for to do this? Also I am not using the STL list.

Thank you!

Upvotes: 0

Views: 3498

Answers (2)

Mark B
Mark B

Reputation: 96241

Sorting a linked list is probably best served by mergesort (still O(n log n) even for a list) since you don't have random element access. If you can switch to std::list the list::sort function will take care of it for you.

Alternately use a non-list container instead of list and you can use any sort method you please.

Upvotes: 2

Seth Carnegie
Seth Carnegie

Reputation: 75130

Sorting a linked list in place is not so efficient because of the lack of random access. You could always use a simple algorithm like bubble sort if you know your list won't be very long, or perhaps if you can afford the small bit of extra complexity, insertion sort would be better.

An alternative method that is probably better than trying to sort a linked list is to just insert each new node in the right place, so that after adding an element the list is sorted.

Upvotes: -1

Related Questions