sorting question
Author
I need a sorting algo that is very fast for sorting arrays that are already almost sorted. QuickSort is very bad at this, so is there an algorithm that is very good?
-CProgrammer
Insertion sort is what you''re after, I expect. It approaches O(N) for almost-ordered data.
Take a look here also, perhaps: http://www.whitsoftdev.com/qsort/
[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]
Take a look here also, perhaps: http://www.whitsoftdev.com/qsort/
[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]
In what way is the array almost sorted? sorted except for a few randomly inserted elements, or what?
"Sneftel is correct, if rather vulgar." --Flarelocke
"Sneftel is correct, if rather vulgar." --Flarelocke
You might just want to go with the old-fashioned bubble sort now.
while (not sorted) {
if (next value < last value) swap the values
}
.bas
[sPiKie] mmorpg isnt hard in vb
quote:Original post by CProgrammer
I need a sorting algo that is very fast for sorting arrays that are already almost sorted. QuickSort is very bad at this, so is there an algorithm that is very good?
-CProgrammer
This seems a very specific request. Can you describe the context for us? It may be that there are other containers that are more appropriate which will keep themselves sorted or it may be better to choose where to insert data so that it remains sorted.
Believe it or not, in some cases it is faster to randomize the data before using quicksort. STL provides the random_shuffle algorithm for this. I dunno about insertion sort approaching O(n) but randomizing will give you a single O(n) followed by a very fast quicksort (since the data is randomized). I''d do some playing around with both insertion sort and randomizing before quicksort.
Author
AP: Wow, so you think shuffling and then sorting with quickSort is faster than just using bubblesort? What do the others think, cause I dunno.
Kylotan: Thanks I'll look into that as well.
-CProgrammer
[edited by - CProgrammer on January 24, 2004 12:48:14 AM]
Kylotan: Thanks I'll look into that as well.
-CProgrammer
[edited by - CProgrammer on January 24, 2004 12:48:14 AM]
Same AP here:
Randomizing the data before a Quicksort will probably always be faster than a bubble sort. Bubble sort is O(n^2) whereas randomizing the data is a single theta(n) cost, plus the randomized data will give the Quicksort nearly best-case performance.
Insertion sort is O(n^2) but it''s expected performance will be a lot better than bubble sort. Insertion sort is probably good on sorted data as the guy above said, but I think his terminology is wrong.
Try both insertion sort and std::random_shuffle+std::sort. I''d guess the guy above is right that insertion sort will win, but you don''t know unless you try.
Randomizing the data before a Quicksort will probably always be faster than a bubble sort. Bubble sort is O(n^2) whereas randomizing the data is a single theta(n) cost, plus the randomized data will give the Quicksort nearly best-case performance.
Insertion sort is O(n^2) but it''s expected performance will be a lot better than bubble sort. Insertion sort is probably good on sorted data as the guy above said, but I think his terminology is wrong.
Try both insertion sort and std::random_shuffle+std::sort. I''d guess the guy above is right that insertion sort will win, but you don''t know unless you try.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
