Scribd
Cargar
2 vistas3 páginas

Algoritmo Quicksort: Ordenación Eficiente

El algoritmo descrito es el método de ordenamiento Quicksort, que selecciona un pivote y reorganiza los elementos en torno a él, separando la lista en sublistas de menores y mayores. Este proceso se repite recursivamente hasta que todos los elementos están ordenados. Un ejemplo ilustrativo muestra cómo se realiza el intercambio de elementos y la aplicación recursiva del algoritmo.

Cargado por

Isc Cris Emm
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
2 vistas3 páginas

Algoritmo Quicksort: Ordenación Eficiente

El algoritmo descrito es el método de ordenamiento Quicksort, que selecciona un pivote y reorganiza los elementos en torno a él, separando la lista en sublistas de menores y mayores. Este proceso se repite recursivamente hasta que todos los elementos están ordenados. Un ejemplo ilustrativo muestra cómo se realiza el intercambio de elementos y la aplicación recursiva del algoritmo.

Cargado por

Isc Cris Emm
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

El algoritmo consta de los siguientes pasos:

 Elegir un elemento de la lista de elementos a ordenar, al que llamaremos


pivote.
 Resituar los demás elementos de la lista a cada lado del pivote, de manera que
a un lado queden todos los menores que él, y al otro los mayores. Los
elementos iguales al pivote pueden ser colocados tanto a su derecha como a su
izquierda, dependiendo de la implementación deseada. En este momento, el
pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
 La lista queda separada en dos sublistas, una formada por los elementos a la
izquierda del pivote, y otra por los elementos a su derecha.
 Repetir este proceso de forma recursiva para cada sublista mientras éstas
contengan más de un elemento. Una vez terminado este proceso todos los
elementos estarán ordenados.

Ejemplo
En el siguiente ejemplo se marcan el pivote y los índices i y j con las letras p, i y j
respectivamente.

Comenzamos con la lista completa. El elemento pivote será el 4:

5 - 3 - 7 - 6 - 2 - 1 - 4
p

Comparamos con el 5 por la izquierda y el 1 por la derecha.

5 - 3 - 7 - 6 - 2 - 1 - 4
i j p

5 es mayor que 4 y 1 es menor. Intercambiamos:

1 - 3 - 7 - 6 - 2 - 5 - 4
i j p

Avanzamos por la izquierda y la derecha:

1 - 3 - 7 - 6 - 2 - 5 - 4
i j p

3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí.

1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
7 es mayor que 4 y 2 es menor: intercambiamos.

1 - 3 - 2 - 6 - 7 - 5 - 4
i j p

Avanzamos por ambos lados:

1 - 3 - 2 - 6 - 7 - 5 - 4
iyj p

En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora
intercambiamos lista[i] con lista[sup] (pasos 16-18):

1 - 3 - 2 - 4 - 7 - 5 - 6
p

Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo


siguiente:

1 - 3 - 2

1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha.


Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con
lista[sup]:

1 - 2 - 3

El mismo procedimiento se aplicará a la otra sublista. Al finalizar y unir todas las


sublistas queda la lista inicial ordenada en forma ascendente.

1 - 2 - 3 - 4 - 5 - 6 - 7
//Recibe un vector de enteros y el índice del primer y último elemento
válido del mismo

void ordenarQuicksort(int[] vector, int primero, int ultimo){


int i=primero, j=ultimo;
int pivote=vector[(primero + ultimo) / 2];
int auxiliar;

do{
while(vector[i]<pivote) i++;
while(vector[j]>pivote) j--;

if (i<=j){
auxiliar=vector[j];
vector[j]=vector[i];
vector[i]=auxiliar;
i++;
j--;
}

} while (i<=j);

if(primero<j) ordenarQuicksort(vector,primero, j);


if(ultimo>i) ordenarQuicksort(vector,i, ultimo);
}

También podría gustarte