Menu
How can I sort 4 numbers in 5 comparisons?
793
Solution: The merging step always takes O(N) time, so the sorting process takes O(N log N) time on all inputs. Exercise 4 [10]: Prove that any comparison based algorithm to sort 4 elements requires 5 comparisons.
Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for n items whenever n ≤ 15 or 20 ≤ n ≤ 22, and it has the fewest comparisons known for n ≤ 46. Glenn K.
(4 factorial) If you do only 4 comparisons, then you can get only 4 bits of information, which is enough to distinguish between 16 different cases, which isn't enough to cover all the possible output cases. Therefore, 5 comparisons is the optimal worst case.
In general, the average number of comparisons per pass in selection sort will always be one half of the number of items to be sorted. For eight items, we have 1/2(82 + 8) = 1/2(64 + 8) = 1/2(72) = 36 comparisons.
Takes numbers {a,b,c,d}, split into 2 sets {a,b} {c,d}. Order each of those 2 sets, so you get (e,f) (g,h). That's one comparison per set.
Now pick lowest from the front (compare e,g). That's now three comparisons. Pick next lowest from either (e, h) or (f, g). That's four. Compare the last two elements (you might not even need this step if the two elements are from the same set, and thus already sorted). So that's five.
158
Pseudocode:
function sortFour(a,b,c,d)
if a < b
low1 = a
high1 = b
else
low1 = b
high1 = a
if c < d
low2 = c
high2 = d
else
low2 = d
high2 = c
if low1 < low2
lowest = low1
middle1 = low2
else
lowest = low2
middle1 = low1
if high1 > high2
highest = high1
middle2 = high2
else
highest = high2
middle2 = high1
if middle1 < middle2
return (lowest,middle1,middle2,highest)
else
return (lowest,middle2,middle1,highest)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
