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!

skaffman
  • 398,947
  • 96
  • 818
  • 769
Behrooz
  • 1,696
  • 2
  • 32
  • 54
  • what language are you programming in? – Andy E Dec 10 '09 at 12:08
  • Im programming in C#.net – Behrooz Dec 10 '09 at 12:12
  • @andy , why one should bother about programming laguage ? – atv Dec 10 '09 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. – atv Dec 10 '09 at 13:32
  • FWIW I agree. I still think Bubblesort (and/ or Elevator sort) should be considered due to their simplicity – philsquared Dec 10 '09 at 14:12
  • you can use insertion sort with binary insert, which improves insertion sort a bit better. – DarthVader Dec 11 '09 at 07:13
  • after a lot of benchmarks with lots of different data, the answer is, MergeSort. – Behrooz Aug 28 '10 at 13:09
  • possible duplicate of [which-sort-algorithm-works-best-on-mostly-sorted-data](http://stackoverflow.com/questions/220044/which-sort-algorithm-works-best-on-mostly-sorted-data) – nawfal Jun 28 '14 at 21:07

7 Answers7

21

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

Dror Helper
  • 30,292
  • 15
  • 80
  • 129
  • @behrooz click on each individual image to see how they function – James Dec 10 '09 at 12:22
  • 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. – Wim Dec 10 '09 at 12:26
  • 1
    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. – philsquared Dec 10 '09 at 13:24
  • A new algorithm called "Dual-Pivot Quicksort" by Vladimir Yaroslavskiy has been recently been making the rounds: http://gdtoolbox.com/DualPivotQuicksort.pdf – JasDev Dec 10 '09 at 14:29
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.

Carl Smotricz
  • 66,391
  • 18
  • 125
  • 167
  • The alternatig variant is usually called CocktailSort. http://en.wikipedia.org/wiki/Cocktail_sort – H H Dec 10 '09 at 13:04
  • 1
    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.) – Joe Strout May 27 '13 at 15:38
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.

philsquared
  • 22,403
  • 12
  • 69
  • 98
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

Marek
  • 10,307
  • 8
  • 70
  • 106
  • 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. – Carl Smotricz Dec 10 '09 at 12:22
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.

H H
  • 263,252
  • 30
  • 330
  • 514
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.

Bob Jarvis - Слава Україні
  • 48,992
  • 9
  • 77
  • 110
  • 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. – Behrooz Dec 10 '09 at 13:25
0

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

erikkallen
  • 33,800
  • 13
  • 85
  • 120