4

i have an array like this:
1,2,3,5,6,4 it is 99% sorted and has 40K elements.
i can put them in an array, list, linked list, ...
but i don`t know the fastest way to sort them!

Improve this question
8
  • what language are you programming in? Commented Dec 10, 2009 at 12:08
  • Im programming in C#.net Commented Dec 10, 2009 at 12:12
  • @andy , why one should bother about programming laguage ? Commented Dec 10, 2009 at 13:31
  • I think Dror's answer is more accurate and it should be the accepted answer. For almost sorted array, insertion sort works best because number of comparisons required at each insertion step is less. Commented Dec 10, 2009 at 13:32
  • FWIW I agree. I still think Bubblesort (and/ or Elevator sort) should be considered due to their simplicity Commented Dec 10, 2009 at 14:12

7 Answers 7

Reset to default
21

The following site has a comparison between common sorting algorithms - it seems that insertion sort wins when the collection is nearly sorted.

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

4 Comments

@behrooz click on each individual image to see how they function
Doesn't look like Bubblesort is that far behind Insertion sort, though I appreciate if you have a single value that's at the opposite end, that will ruin it quite a bit.
Yeah, how far the out-of-order elements are from their target permissions is going to be the killer for Bubblesort, especial for large collections.
A new algorithm called "Dual-Pivot Quicksort" by Vladimir Yaroslavskiy has been recently been making the rounds: gdtoolbox.com/DualPivotQuicksort.pdf
6

"They laughed when I sat down at the keyboard and coded a bubblesort..."

But seriously: Bubblesort is close but not quite. Bubblesort repeatedly moves in one direction, so if there's a low-key value near the top end of the array it and the comparison site "bubbles" upward all the time, it takes many iterations of the main loop for the data item to bubble down against the current. That's pretty much worst case behavior, which for Bubblesort is disastrous.

But there's a refinement to BubbleSort, sometimes called ElevatorCocktail Sort, where the bubble moves in alternating directions: One pass up, one pass down, repeat. This permits single elements to move a long distance in a single pass (or actually, 2 passes), and the number of passes is proportional to the number of elements that need moving. For a small number of unsorted elements, this can approach efficiency.

I believe that for the general case, the second link in marek's answer will be faster. The advantage of Bubble/ElevatorCocktail sort is that it's so simple, it's virtually foolproof, and not a lot of work.

Improve this answer

2 Comments

The alternatig variant is usually called CocktailSort. en.wikipedia.org/wiki/Cocktail_sort
Thanks for the pointer on CocktailSort. It's exactly what I needed. (I've got a bunch of sprites, essentially, that need to stay sorted in Y order. This is efficient enough that I can call it on every frame, with no perceptible speed hit.)
3

If it's already ordered to such a high degree, and the not-quite-sorted elements are not far from their correct positions, then this may be one of the few cases that bubblesort is useful.

Improve this answer

Comments

2

Google gives a lot of results for this, e.g. this one with an overview of various methods how to accomplish that: http://home.tiac.net/~cri/2004/ksort.html

Improve this answer

1 Comment

I haven't quite understood the "ksort" worked out in the 2nd link, but it looks like someone gave it a lot of thought. Probably a good choice, +1.
1

Put them in an array. You don't want to mess with a 40k linked-list.

There is a very narrow case for CocktailSort (bubblesort in 2 directions). But that depends on what exactly that 1% unsorted means. If there are a few elements displaced, but close to their target positions it might work.

But InsertionSort or ShellSort are almost always going to win. Even in the cases where CocktailSort would theoretically be better, the difference will be small. So they are the (much) safer bet.

Improve this answer

Comments

0

As with most questions of this sort, the answer is "That depends...". Do you care if the sort is stable, i.e. if elements whose keys are equal retain their original relative ordering after being sorted? Do you just care about raw speed? Is simplicity of implementation important? Does memory consumption matter?

Personally, I will always choose a stable sort algorithm, as I'm willing to sacrifice some raw speed for what I consider to be "reasonable" behavior, and non-stable sorting is too often "unreasonable". So I tend to go with the merge-sort algorithm, which is fast and reasonably simple, but it does use extra memory. Another advantage of merge-sort is that if the data is already sorted its complexity is O(n), so for nearly-sorted data it should be close to O(n).

YMMV.

Improve this answer

1 Comment

it is a sql primary key column witch is stored in an in-memory cache to be used offline. so i don`t need stable sort. my output is an array so it can use an array of size N r more.
0

Is performance critical (as verified by a profiler)? Otherwise, just use your framework/langauge's default sort (probably quicksort). It will perform decently.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.