Contenido principal
Curso: Ciencias de la computación > Unidad 1
Lección 9: Ordenamiento rápidoHacer particiones en tiempo lineal
El verdadero trabajo del ordenamiento rápido ocurre durante el paso de dividir, que hace la partición del subarreglo
array[p..r] alrededor de un pivote del subarreglo. Aunque podemos elegir cualquier elemento en el subarreglo como el pivote, es fácil de implementar hacer la partición si elegimos el elemento que está hasta la derecha del subarreglo, A[r], como el pivote.Una vez elegido un pivote, hacemos la partición del subarreglo al pasar por él, de izquierda a derecha, al comparar cada elemento con el pivote. Mantenemos dos índices
q y j en el subarreglo que lo divide en cuatro grupos. Usamos el nombre de variable q porque ese índice eventualmente apuntará a nuestro pivote. Usamos j porque es un nombre común de una variable de contador, y la variable será descartada una vez que terminemos.- Los elementos en
array[p..q-1]son el "grupo C", que consiste de elementos que se sabe que son más chicos o iguales que el pivote. - Los elementos en
array[q..j-1]son el "grupo G," que consiste de elementos que se sabe que son más grandes que el pivote. - Los elementos en
array[j..r-1]son el "grupo D", que consiste de elementos cuya relación con el pivote es desconocida porque todavía no han sido comparados. - Por último,
array[r]es el "grupo P", el pivote.
Inicialmente, tanto
q como j son iguales a p. En cada paso, comparamos A[j], el elemento hasta la izquierda en el grupo D, con el pivote. Si A[j] es mayor que el pivote, entonces simplemente incrementamos j, de modo que la línea que divide los grupos C y D se corra una posición hacia al derecha:Si en cambio
A[j] es menor o igual que el pivote, intercambiamos A[j] con A[q] (el elemento hasta la izquierda en el grupo G), incrementamos j, e incrementamos q, corriendo así la línea que divide a los grupos C y G, y la línea que divide a los grupos G y D una posición hacia la derecha:Una vez que llegamos al pivote, el grupo U está vacío. Intercambiamos el pivote con el elemento más a la izquierda en el grupo G: se intercambia
A[r] con A[q]. Este intercambio pone al pivote entre los grupos L y G, y hace lo correcto incluso si el grupo L o el grupo G está vacío. La función
partition que implementa esta idea también devuelve el índice q donde terminó poniendo el pivote, de modo que la función quicksort, la cual la llama, sepa dónde están las particiones. Aquí están los pasos de hacer la partición del subarreglo [12, 7, 14, 9, 10, 11] en
array[4..9]:Hacer la partición de un subarreglo con
A[j] se compara una vez con el pivote. A[j] puede o no intercambiarse con A[q], q puede o no incrementarse, y j siempre se incrementa. El número total de líneas ejecutadas por elemento en el subarreglo es una constante. Como el subarreglo tiene Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
porque se le argumenta la funcion partition en esta regla(1 voto)
i couldnt solve the activity before, can someone help me ?
// This function partitions given array and returns
// the index of the pivot.
var partition=function(array, p, r){
// This code has been purposefully obfuscated,
// as you will implement it yourself in next challenge
var e=array,t=p,n=r;var r=function(e,t,n){var r=e[t];e[t]=e[n];e[n]=r;};var i=t;for(var s=t;s<n;s++){if(e[s]<=e[n]){r(e,s,i);i++;}}r(e,n,i);return i;
};
var quickSort = function(array, p, r) {
if ( 1< r-p) {
var q = partition(array,p ,r );
quickSort(array,q+1,array.length-1);
quickSort(array,p ,q-1 );
}
};
var array = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];
quickSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [2,3,5,6,7,9,10,11,12,14]);(1 voto)
Vence al ordenar de manera recursiva los subarreglos array[p..q-1] (todos los elementos a la izquierda del pivote, los cuales deben ser menores o iguales que el pivote) y array[q+1..r] (todos los elementos a la derecha del pivote, los cuales deben ser mayores que el pivote).(1 voto)