Menu
Design an efficient algorithm to sort 5 distinct - very large - keys less than 8 comparisons in the worst case. You can't use radix sort.
697
In any cases, (worse case, best case or average case) to sort the list in ascending order the number of comparisons between elements is the same. All lists with 5 elements need 10 comparisons to sort all the data.
The least number of comparisons needed to sort (order) five elements is 8.
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.
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.
Compare A to B and C to D. WLOG, suppose A>B and C>D. Compare A to C. WLOG, suppose A>C. Sort E into A-C-D. This can be done with two comparisons. Sort B into {E,C,D}. This can be done with two comparisons, for a total of seven.
119
This is pseudocode based on Beta's answer. Might have some mistakes as I did this in a hurry.
if (A > B)
swap A, B
if (C > D)
swap C, D
if (A > C)
swap A, C
swap B, D # Thanks Deqing!
if (E > C)
if (E > D) # A C D E
if (B > D)
if (B > E)
return (A, C, D, E, B)
else
return (A, C, D, B, E)
else
if (B < C)
return (A, B, C, D, E)
else
return (A, C, B, D, E)
else # A C E D
if (B > E)
if (B > D)
return (A, C, E, D, B)
else
return (A, C, E, B, D)
else
if (B < C)
return (A, B, C, E, D)
else
return (A, C, B, E, D)
else
if (E < A) # E A C D
if (B > C)
if (B > D)
return (E, A, C, D, B)
else
return (E, A, C, B, D)
else
return (E, A, B, C, D)
else # A E C D
if (B > C)
if (B > D)
return (A, E, C, D, B)
else
return (A, E, C, B, D)
else
if (B < E)
return (A, B, E, C, D)
else
return (A, E, B, C, D)
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
