CODEWITHSUNDEEP
arraysalgorithmsorting
user2038833
user2038833

Reputation: 87

How to find a lower bound for a sorting algorithm which involves super-comparisons?

Suppose there is a sorting algorithm that in addition to regular comparisons, is also allowed super-comparisons: a super-comparison takes in three elements and outputs those elements in order from smallest to largest.

I want to find a lower bound.

Since unlike a regular comparison that only has two possible outcomes, a super-comparison will have 3! possible outcomes, I believe it should be log3(n!).

I am not sure though, any ideas?

Upvotes: 1

Views: 602

Answers (2)

amit
amit

Reputation: 178521

Actually, the number of super-comparisons is log_6(n!), this is because you have 6 possible outcomes per super-compare op, and not 3 (3! = 6). Thus, by repeatedly invoking these super-comparisons on the tree representing the random permutation, you get to a sorted array within log_6(n!) compare ops.

Note that when it comes to asymptotic time complexity - it remains O(nlogn) the base of the logarithm does not matter because you can switch bases easily:

log_6(n!) = log_2(n!)/log_2(6) = log_2(n!) / CONST 
=> log_6(n!) is in O(log_2(n!))
=> log_6(n!) is in O(nlogn)

P.S A good intuition will be to see what happens at "infinity" i.e. what you have a super-comparison that sorts n elements. Obviously, you will need a single such op to sort an array, and indeed log_n!(n!) = 1, while log_n(n!) > 1.

Upvotes: 3

jinsoo yoon
jinsoo yoon

Reputation: 106

in ocaml,

let rec quicksort = function
    | [] -> []
    | x::xs -> let smaller, larger = List.partition (fun y -> y < x) xs
               in quicksort smaller @ (x::quicksort larger)

Upvotes: -1

Related Questions