**T**he last Le Monde puzzle made me wonder about the ternary version of the sorting algorithms, which all seem to be binary (*compare x and y, then*…). The problem is, *given (only) a blackbox procedure that returns the relative order of three arbitrary numbers, how many steps are necessary to sort a series of n nnumbers?* The heapsort entry in Wikipedia mentions a ternary sorting version, but does not get into details. Robert Sedgewick (author of a fabulous book on algorithmic I enjoyed very much when I started programming) has a talk about the optimality of *quicksort* where he mentions ternary sorting, but this seems to be more related with ties than with my problem… It is of course highly formal in that I do not know of a physical device that would justify moving from binary to ternary comparisons.

## Archive for rank

## Ternary sorting

Posted in R with tags heapsort, Le Monde, quicksort, rank, sorting, wikipedia on July 25, 2011 by xi'an## Le Monde puzzle [#28]

Posted in R with tags bubblesort, mathematical puzzle, quicksort, R, rank on July 22, 2011 by xi'an**T**he puzzle of last weekend in ** Le Monde** was about finding the absolute rank of x

_{9}when given the relative ranks of x

_{1},….,x

_{8}and the possibility to ask for relative ranks of three numbers at a time. In R terms, this means being able to use

> rank(x[-9]) [1] 1 7 4 6 8 3 2 5 > rank(x[1:3]) [1] 1 3 2

or yet being able to sort the first 8 components of x

> x[-9]=sort(x[-9]) > rank(x[c(1,8,9)]) [1] 1 3 2

and then use rank() over triplets to position x_{9} in the list. If x_{9} is an extreme value, calling for its rank relative to x_{1} and x_{8} is sufficient to find its position. Else repeating with the rank relative to x_{2} and x_{7}, then relative to x_{3} and x_{6} , etc., produces the absolute rank of x_{9} in at most 4 steps. However, if we first get the rank relative to x_{1} and x_{8}, then the rank relative to x_{4} and x_{5}, we only need at most an extra step to find the absolute rank of x_{9} in thus at most 3 steps. Yet however, if we start with the rank relative to x_{3} and x_{6}, we are left with a single rank call to determine the absolute rank of x_{9} since, whatever the position of x_{9} relative to x_{3} and x_{6}, there are only two remaining numbers to compare x_{9 }with. So we can find the absolute rank of x_{9} in exactly two calls to rank.

**T**he second part of the puzzle is to determine for an unknown series x of 80 numbers the maximum number of calls to rank(c(x_{1},x_{2},x_{3})) to obtain rank(x). Of course, the dumb solution is to check all 82160 triplets, but I presume a sort of bubblesort would do better, even though Wikipedia tells me that bubble sort has worst-case and average complexity both *О*(*n*^{2}), while quicksort has an average (if not worse-case) *O*(*n* log(*n)*) complexity…. If we follow the one-step procedure obtained in the first part to insert a new number, starting with three numbers whose relative rank is obtained with one single call, we need *in toto*

1 + (9-3)*2 + ((1+3*8+2)-9)*3+(80-27)*4 =279

calls to rank since 80<1+3*(3*8+2)+2=81. *(This is also the solution proposed in Le Monde, however there is no proof inserting one number at a time is the optimal solution.)*