How to find the best way to sort 8 elements and prove that there is no better way (no more efficient way)?

Question

Possible Duplicate:
Fastest sort of fixed length 6 int array

The task is to find a way to sort 8 random numbers with the least number of comparisons (not operations). I expect that I have to use qSort (divide an array by half, sort and then merge and so on.. it must be quicksort i think). For 8 elements number of comparisons is 17, and i have to prove that there is no way to sort random array with 16 (n minus 1) comparisons.

Thanks

Any case, so must be worst also. I'm in first year of studies, so I don't think we have to do something extraordinary (I study math not IT). And kind of sort I use is mergesort! Thanks in advance.

Best case? Average case? Worst case? Are stochastical algorithms allowed? I can give a best-case implementation with 7 comparisons. — thiton, Dec 29 '11 at 22:05
using the link found in the chosen answer at the question linked to by @atalyor , the network sort would use 19 comparisons. — hatchet - done with SOverflow, Dec 29 '11 at 22:07
@SaeedAmiri, the other question was about 6, but it you go to this site it referenced (http://pages.ripco.net/~jgamble/nw.html) you can see that 8 elements takes 19 comparisons with network sort — hatchet - done with SOverflow, Dec 30 '11 at 13:42
This question is not really a duplicate of the 6 element question. That was about fastest runtime. This is about number of comparisons. Because of that, the answers to these questions should be different regardless of whether it's 6 or 8 elements. — hatchet - done with SOverflow, Dec 30 '11 at 15:54

score 3 · Answer 1 · edited May 23 '17 at 12:17

Mergesort/merge-insertion sort will require 16 comparisons for n=8, which is the minimum worst case number of comparisons.

http://oeis.org/A001768 (number of comparisons for mergesort)

http://oeis.org/A036604 (minimum number of comparisons in general)

see also Sorting an array with minimal number of comparisons

EDIT: without assuming "random numbers" are range restricted integers. If you can make assumptions about the range of values, then there are alternatives.

score 2 · Answer 2 · answered Dec 29 '11 at 23:20

2

Radix sort requires no comparisons at all :)

answered Dec 29 '11 at 23:20

500 - Internal Server Error

28,327
8
59
66

1

Just because it's not comparative, doesn't mean it requires no comparisons. Even a simple x == x is a comparison, comparisons between digits are comparisons... – Luchian Grigore Dec 30 '11 at 06:29
@Luchian Grigore: Radix sort, like Counting Sort and Bucket sort , is not a general purpose sort algorithm. It requires additional conditions on the input: you can not sort an arbitrary input like you do with Quick sort, Merge Sort, and other true general purpose sort algorithms. – Massimo Cafaro Dec 30 '11 at 09:17

How to find the best way to sort 8 elements and prove that there is no better way (no more efficient way)?

2 Answers2

Linked

Related