which sorting algorithms give near / approximate sort sooner?

views:

391

answers:

+8 Q:

which sorting algorithms give near / approximate sort sooner?

Which sorting algorithms produce intermediate orderings which are good approximations?

By "good approximation" I mean according to metrics such as Kendall's tau and Spearman's footrule for determining how "far" an ordered list is from another (in this case, the exact sort)

The particular application I have in mind is where humans are doing subjective pairwise comparison and may not be able to do all n log n comparisons required by, say, heapsort or best-case quicksort.

Which algorithms are better than others at getting the list to a near / approximate sort sooner?

Bubble sort I reckon. Advantage is that you can gradually improve the ordering with additional sweeps of the data.

Jeffrey Kemp 2009-05-27 05:55:36

Using bubble sort he would end with one side of the list perfectly ordered, and the other side not

MartinodF 2009-05-27 05:58:29

Bubble sort starts sorting the top n values, but the rest is almost completely unordered. Plus: You need more comparisons in total.

Georg 2009-05-27 05:59:10

Shell sort is a generalization of bubble sort that runs much faster. In its final step Shell sort is bubble sort.

Neil G 2009-05-27 06:04:11

Actually, the bidirectional bubble sort which I use for my accounting spreadsheet would not have an "unbalanced" state since it alternates between trickling higher values down and lower values up. Hence it correctly places i[n], i[1], i[n-1], i[2] and so on. This is one of the few places I'll ever use bubble sorts, in data that's already heavily sorted and I'm just adding stuff to the end that needs to be placed.

paxdiablo 2009-05-27 06:04:55

+4 A:

You may want to check out the shell sort algorithm.

AFAIK it is the only algorithm you can use with a subjective comparison (meaning that you won't have any hint about median values or so) that will get nearer to the correct sort at every pass.

Here is some more information http://en.wikipedia.org/wiki/Shell_sort

MartinodF 2009-05-27 05:56:46

No. Try not. Sort, or sort not. There is no try. :-)

paxdiablo 2009-05-27 06:00:17

+3 A:

I would suggest some version of quicksort. If you know in what range the data you want to sort is then you can select pivot elements cleverly and possibly divide the problem into more than two parts at a time.

AnnaR 2009-05-27 06:09:40

Quicksort, maybe even with a "guess" pivots, should give pretty well ordered lists after a few recursions and can be easily implemented by human beings using buckets.

stephan 2009-05-27 06:13:56

I did consider having more than a binary partition (where this related question http://stackoverflow.com/questions/913624/sorting-algorithm-where-pairwise-comparison-can-return-more-information-than-1 is relevant)

James Tauber 2009-05-27 06:17:22

I thought that the comparison was subjective, but if you can guess a good pivot element (maybe because it's subjective but "predictable"?) than you should use quicksort.

MartinodF 2009-05-27 06:24:08

it's subject and typically non-numerical so there is no a priori good pivot, however I could ask the user to rank a small random subset then use the middle item as the initial pivot

James Tauber 2009-05-27 06:27:33

Didn't thought of that.Then you are go for quicksort ;)

MartinodF 2009-05-27 06:31:07

how about a left to right radix sort and stopping a bit premature (no pun intended)?

this will be Nb runtime where b is the number of bits you decide to examine. the more bits you examine, the more sorted it will be

unsorted:
5 0101
8 1000
4 0100
13 1101
1 0001

after 1 bits (N):
5 0101
1 0001
4 0100
13 1101
8 1000

after 2 bits (2N)
1 0001
5 0101
4 0100
8 1000
13 1101

and so on...

nategood 2009-05-27 06:10:08

The OP is using humans to do pairwise comparison. His objects probably don't have "bits" in the radix sort way.

Antti Rasinen 2009-05-27 06:19:32

my objects are typically non-numerical

James Tauber 2009-05-27 06:28:27

chances are you at least have some key that you are sorting on that could be done in a bitwise way? if not an int, go off the first b bits of the ascii representation? unicode and other encodings would degrade pretty quickly.

nategood 2009-05-27 06:47:47

no, the items are being sorted by on subjective pairwise comparison by humans, there's no key

James Tauber 2009-05-27 13:49:04

ah okay. missed that. but for future reference, when you're willing to trade off "sortedness" for performance, it's an idea.

nategood 2009-05-27 16:19:25

My completely un-scientific and visual survey of the sorts on this page indicates that "Comb Sort" looks good. It seems to be getting to a better approximation with every pass.

JP Alioto 2009-05-27 06:10:21

ansaurus

tags:

views:

answers:

which sorting algorithms give near / approximate sort sooner?

related questions