12

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?

James Tauber
  • 3,386
  • 6
  • 27
  • 37
  • I see you did not "accept" any answer. Have you got one yourself? Have you find an answer at all? I'm a bit curious myself about this subject. Thanks. – Shai Oct 31 '13 at 05:58
  • A related question I have that brought me to this page is how to assess the accuracy of an approximate sorting algorithm (i.e. metric for "how well sorted" something is), and eventually I found [Is there a way to measure how sorted a list is?](https://stackoverflow.com/q/16994668/13697228) – Sterling Sep 18 '21 at 22:27

6 Answers6

9

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
  • 8,157
  • 2
  • 32
  • 28
3

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
  • 3,166
  • 6
  • 35
  • 39
  • 1
    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 May 27 '09 at 06:13
  • 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 May 27 '09 at 06:17
  • 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 May 27 '09 at 06:24
  • 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 May 27 '09 at 06:27
  • 1
    Didn't thought of that. Then you are go for quicksort ;) – MartinodF May 27 '09 at 06:31
2

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
  • 11,807
  • 4
  • 36
  • 44
  • The OP is using humans to do pairwise comparison. His objects probably don't have "bits" in the radix sort way. – Antti Rasinen May 27 '09 at 06:19
  • my objects are typically non-numerical – James Tauber May 27 '09 at 06:28
  • 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 May 27 '09 at 06:47
  • no, the items are being sorted by on subjective pairwise comparison by humans, there's no key – James Tauber May 27 '09 at 13:49
  • ah okay. missed that. but for future reference, when you're willing to trade off "sortedness" for performance, it's an idea. – nategood May 27 '09 at 16:19
1

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
  • 44,864
  • 6
  • 88
  • 112
0

I devised an NlgN sorting algorithm I called "tournament sort" some time ago, which finds output items in order (i.e. it starts by finding the first item, then it finds the second item, etc.). I'm not sure it's entirely practical, since the book-keeping overhead exceeds that of quicksort, merge sort, etc. but in benchmarking with 1,000,000 random items the comparison count actually came in below a standard library quicksort implementation (though I'm not sure how it would do against newer ones).

For purposes of my algorithm, the "score" of each item is the number of items that it's known to be better than. Initially each item has a score of 0. When two items are compared, the better item adds to its score the score of the other item, plus one. To run the algorithm, declare all items to be "eligible", and as long as more than one eligible item remains, compare the two eligible items with the lowest score, and make the loser "ineligible". Once all but one item has been declared ineligible, output the one remaining item and then declare eligible all the items which that item had "beaten".

The priority queue required to compare the two lowest-scoring items poses a somewhat annoying level of bookkeeping overhead, but if one were sorting things that were expensive to compare, the algorithm may be interesting.

supercat
  • 77,689
  • 9
  • 166
  • 211
-2

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

Jeffrey Kemp
  • 59,135
  • 14
  • 106
  • 158
  • Using bubble sort he would end with one side of the list perfectly ordered, and the other side not – MartinodF May 27 '09 at 05:58
  • Bubble sort starts sorting the top n values, but the rest is almost completely unordered. Plus: You need more comparisons in total. – Georg Schölly May 27 '09 at 05:59
  • Shell sort is a generalization of bubble sort that runs much faster. In its final step Shell sort is bubble sort. – Neil G May 27 '09 at 06:04
  • 1
    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 May 27 '09 at 06:04