**A** low-key sorting problem as Le Monde current mathematical puzzle:

*If the numbers from 1 to 67 are randomly permuted and if the sorting algorithm consists in picking a number i with a position higher than its rank i and moving it at the correct i-th position, what is the maximal number of steps to sort this set of integers when the selected integer is chosen optimaly?*

As the question does not clearly state what happens to the number j that stood in the i-th position, I made the assumption that the entire sequence from position i to position n is moved one position upwards (rather than having i and j exchanged). In which case my intuition was that moving the smallest moveable number was optimal, resulting in the following R code

sorite<-function(permu){ n=length(permu) p=0 while(max(abs(permu-(1:n)))>0){
j=min(permu[permu<(1:n)])
p=p+1
permu=unique(c(permu[(1:n)<j],j,permu[j:n]))}
return(p)}

which takes at most n-1 steps to reorder the sequence. I however checked this insertion sort was indeed the case through a recursive function

resorite<-function(permu){ n=length(permu);p=0 while(max(abs(permu-(1:n)))>0){
j=cand=permu[permu<(1:n)]
if (length(cand)==1){
p=p+1
permu=unique(c(permu[(1:n)<j],j,permu[j:n]))
}else{
sol=n^3
for (i in cand){
qermu=unique(c(permu[(1:n)<i],i,permu[i:n]))
rol=resorite(qermu)
if (rol<sol)sol=rol}
p=p+1+sol;break()}}
return(p)}

which did confirm my intuition.

### Like this:

Like Loading...