• Advertisement

Archived

This topic is now archived and is closed to further replies.

sorting question

This topic is 5202 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites

  • Advertisement