SQRTSORT del libro de Vazirani sobre algoritmos

Question

Yo estudio el Algoritmo libro y vi el siguiente ejercicio. Yo no podía resolver. Esta no es la tarea, ni examen. Sólo la lectura de algún material en algoritmos para la preparación del examen de ingreso. Cualquier buena idea o solución sería apreciada.

Describir un algoritmo que ordena un arreglo de entrada de $A[1..n]$ llamando a un subrutina SQRTSORT(k), que ordena el subarray $A[k+1..k+\sqrt{n}]$ en su lugar, dado un entero arbitrario $k$ $0$ $n-\sqrt{n}$ como entrada. (Para simplificar el problema, suponga que $\sqrt{n}$ es un entero). Su algoritmo es sólo permitido para revisar o modificar la matriz de entrada llamando SQRTSORT; en particular, el algoritmo debe no comparar directamente, mover o copiar elementos de la matriz. Cuántas veces ¿su algoritmo de llamada SQRTSORT en el peor de los casos?

Answer 1

Usted puede detectar $l$ mayores valores (y recopilar de ellos en posiciones de $n-l+1,\ldots,n$) de la matriz llamando SQRTSORT con $k=0$, $k=\sqrt{n}-l$, $k=2\sqrt{n}-2l$, y así sucesivamente. Por lo tanto, $2\sqrt{n}$ de las llamadas son suficientes para encontrar $\sqrt{n}/2$ mayores valores de la matriz. Hacer esto de forma recursiva, se ordena la matriz con en la mayoría de las $4n$ llamadas de SQRTSORT.

Un límite inferior mejor que $O(n)$ no se puede esperar, porque algunas matrices requieren $cn^2$ transposiciones de los vecinos de las entradas se ordenan. Tenga en cuenta que SQRTSORT actos en $\sqrt{n}$ consecutivo entradas, y así una permutación causada por SQRTSORT llamada puede ser escrito como una composición de más de $O(n)$ transposiciones de los vecinos de las entradas.