views:

391

answers:

6

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?

A: 

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

Jeffrey Kemp
Using bubble sort he would end with one side of the list perfectly ordered, and the other side not
MartinodF
Bubble sort starts sorting the top n values, but the rest is almost completely unordered. Plus: You need more comparisons in total.
Georg
Shell sort is a generalization of bubble sort that runs much faster. In its final step Shell sort is bubble sort.
Neil G
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
+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
A: 

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

paxdiablo
+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
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
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
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
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
Didn't thought of that.Then you are go for quicksort ;)
MartinodF
A: 

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
The OP is using humans to do pairwise comparison. His objects probably don't have "bits" in the radix sort way.
Antti Rasinen
my objects are typically non-numerical
James Tauber
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
no, the items are being sorted by on subjective pairwise comparison by humans, there's no key
James Tauber
ah okay. missed that. but for future reference, when you're willing to trade off "sortedness" for performance, it's an idea.
nategood
A: 

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