jueves, 19 de julio de 2007

ORDENACIÓN, BÚSQUEDA E INTERCALACIÓN

ORDENACIÓN, BÚSQUEDA E INTERCALACIÓN
Los procesos que consumen más tiempo durante la operación de un ordenador, son ordenación, búsqueda e intercalación. La ordenación se clasifica en interna (matrices), y externa (archivos). Las técnicas ordenación, mezcla e intercalación deben ser dominados por el alumno.
ORDENACIÓN
Es un proceso para clasificar los elementos de un array en un orden particular. Por ejemplo, clasifi-car un conjunto de números en orden creciente o una lista de nombres por orden alfabético. La clasifica-ción es una operación tan frecuente en programas de computadora que una gran cantidad de algoritmos han sido diseñados para clasificar listas de elementos con eficacia y rapidez. La elección de un determi-nado algoritmo depende del tamaño del vector o array a clasificar, el tipo de datos y la cantidad de memoria disponible. La ordenación o clasificación es el proceso de organizar datos en algún orden o secuencia específica tal como creciente o decreciente para datos numéricos o alfabéticamente para datos de caracteres.
Los métodos de ordenación se dividen en dos categorías:
 ordenación interna (vectores, tablas, matrices)
 ordenación externa (archivos)
La ordenación de arrays se maneja en la memoria RAM, por lo tanto se hace a gran velocidad y ac-ceso aleatorio. La ordenación de archivos se suele hacer sobre soportes de almacenamiento externo, discos, cintas, etc.. Estos dispositivos son más lentos en las operaciones de entrada- salida, pero pueden contener mayor cantidad de información.
Los métodos de ordenación que desarrollaremos podrán ser explicados a vectores, pueden ser ex-tendidos a matrices o tablas, ya que toda ordenación de tabla o matriz se basa en la ordenación de una fila o columna, que no es otra cosa que un vector.
Los más populares son:
 Intercambio
 Selección
 Inserción
MÉTODO DE INTERCAMBIO O DE BURBUJEO
El algoritmo de clasificación de intercambio o de la burbuja, debería ser denominado de decantación y se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.
Partamos que poseemos el siguiente vector y se desea ordenar en forma ascendente(el menor en la posición V(1) y el último en V(9)):
V(1) 64
V(2) 28
V(3) 13
V(4) 23
V(5) 79
V(6) 54
V(7) 25
V(8) 18
V(9) 41
Los pasos a dar son:
1. Comparar V(1) y V(2). Si están en orden, se mantienen como están; caso contrario se intercam-bian entre sí.
2. A continuación se comparan los elementos 2 y 3; de nuevo si no están en orden, se intercam-bian sino no.
3. Y así sucesivamente, hasta que cada elemento del vector ha sido comparado con sus elementos adyacentes y se han realizado los intercambios necesarios.
El método se expresa así:
Pseudicódigo N-S
desde I = 1 hasta 8 hacer I = 1 hasta 8
si elemento (I) > elemento (I + 1) entonces elemento (I) > elemento (I + 1)
intercambiar elementos (I, I+ 1) intercambiar elementos (I, I+ 1)
fin si
fin desde
Intercambiar es un procedimiento para trocar los valores de dos elementos A(I), A(I + l), es una ac-ción compuesta que contiene las siguientes acciones:
AUX  A(I)
A(I)  A(I + 1)
A(I + 1)  AUX
El valor más grande rápidamente baja al último lugar, mientras el más pequeño sube posición a po-sición hacia el comienzo de la lista al igual que las burbujas de aire en una botella de gaseosa. Tras reali-zar un recorrido completo por todo el vector, el elemento más grande habrá llegado a ocupar la última posición.
En el segundo recorrido, el segundo elemento llegará a la penúltima, y así sucesivamente.
Ahora veremos como funciona esta idea en el ejemplo anterior.
Número de paso
Inic 1 2 3 4 5 6 7 8
V(1) 64 28 13 13 13 13 13 13 11
V(2) 28 13 23 23 23 23 18 11 13
V(3) 13 23 28 28 25 18 11 18 18
V(4) 23 64 54 25 18 11 23 23 23
V(5) 79 54 25 18 11 25 25 25 25
V(6) 54 25 18 11 28 28 28 28 28
V(7) 25 18 11 54 54 54 54 54 54
V(8) 18 11 64 64 64 64 64 64 64
V(9) 11 79 79 79 79 79 79 79 79
El pseudo código de este algoritmo de ordenación, es el que desarrollamos en los siguientes pasos
Pseudocódigo algoritmo burbuja1
lNlClO
para I  1 hasta N – 1 hacer
para J  1 hasta N – 1 hacer
si X(J) > X(J + 1) entonces {intercambiar}
AUX  X(J)
X(J)  X(J + 1)
X(J+ 1)  AUX
fin si
fin para
fin para
El diagrama N-S del algoritmo de burbuja1:
I  1 hasta N – 1
J  1 hasta N – 1
X(J) > X(J + 1) {intercambiar}
AUX  X(J)
X(J)  X(J + 1)
X(J+ 1)  AUX




Si se efectúa n-1 veces la operación sobre un vector de n valores se tiene ordenada el vector. Cada operación requiere n-1 comprobaciones o test y como máximo n-1 intercambios. La ordenación total exigi-rá un máximo de
(n – 1) *(n – l) = (n – 1)2 intercambios de elementos.
Las sucesivos situaciones de los elementos del vector se ve en el listado anterior.
Si observamos en detalle notamos, que en le segundo paso no es necesario llegar a la última posi-ción del vector ya que en el se encuentra el mayor valor, en el tercer paso los dos últimos valores ya están ordenados. Y así sucesivamente. Por lo cual en esta ordenación hay un máximo de cambios igual:
(n – 1) + (n – 2) + (n – 3) + ... + 3 + 2 + 1 = n * (n – 1) / 2 intercambios de elementos.
Para optimizar este algoritmo su pseudocódigo deberá ser el siguiente.
Pseudocódigo algoritmo burbuja2
INICIO
para I  1 hasta N – 1 hacer
para J  1 hasta N – I hacer
si X(J) > X(J + 1) entonces {intercambiar}
AUX  X(J)
X(J)  X(J + 1)
X(J+ 1)  AUX
fin si
fin para
fin para
Como se puede notar el único cambio que sufrió el pseudocódigo es N-I en lugar de N-1 en el se-gundo para, este cambio no alterará el diseño del diagrama N-S por lo cual no lo repetiremos.
Segunda mejora
Esta segunda mejora toma el caso cuando aun no cumplidos todos los ciclos el vector ya se encuen-tra ordenado. En este caso es posible que estemos realizando ciclos innecesarios, los que consumen tiempo de procesador sin beneficio. Para evitar este problema lo que se hará es colocar una bandea. Su función es que cuando en un ciclo no se haga ningún cambio (lo que implica que el vector ya esta orde-nado), la bandera indique esto y se detenga el proceso.
Pseudocódigo algoritmo burbuja3
lNlClO
Bandera  F (falso)
I  1
mientra Bandera = F y I < N hacer
Bandera  V (verdadero)
para J  1 hasta N – I hacer
si X(J) > X(J + 1) entonces {intercambiar}
AUX  X(J)
X(J)  X(J + 1)
X(J+ 1)  AUX
Bandera  F
fin si
Incrementa I
fin para
fin para
El diagrama N-S del algoritmo de burbuja3:
Bandera  F (falso) I  1
Bandera = F y I < N
Bandera  V (verdadero)
J  1 hasta N – I
X(J) > X(J + 1) {intercambiar}
AUX  X(J)
X(J)  X(J + 1)
X(J+ 1)  AUX
Bandera  F



Incremente I
Código en Pascal del procedimiento para el algoritmo de burbuja3:
program Ordenamiento_Burbuja;
{* Ejemplo del ordenamiento por el método de burbujeo *}
{* Burbujeo mejorado con bandera *}
{* Archivo BurbujaB.Pas *}
{* Desarrollo del Ing. Fernando J. LAGE *}
{* Octubre 1998*}
uses
wincrt,windos; {* declaraciones de librerias, para correr bajo Windows *}
{* crt,dos;*} {* declaraciones de librerias, para correr bajo DOS *}
const
Enter = #13;
Ln = #13#10;
type {* Definición de tipos *}
Numeros = 1..3200;
Vector = array[1..256]of Numeros;
Var
Dato : Vector;
Filas : Byte;
procedure IntercambioE (var Capa, Omega : Numeros);
{* IntercambioE produce el intercambio de dos valores del vector *}
var
Aux : Numeros; {* elemento auxiliar *}
begin {* Comienzo del procedimiento IntercambioE *}
Aux := Capa;
Capa := Omega;
Omega := Aux
End; {* Fin del procedimiento IntercambioE*}
procedure BurbujaB (var Alfa: Vector; Elementos: integer);
{* BurbujaB produce el ordenamiento usando el método de la burbuja *}
{* Optimizado por el uso de una Bandera *}
var
Bandera : Boolean;
Iteracion, Contador : Integer; {* Iteracion reemplaza I del pseudocódigo *}
{* Contador a J del pseudocódigo *}
begin {* Comienzo del procedimiento BurbujaB *}
Bandera := False;
Iteracion := 1;
While (Bandera = False) and (Iteracion < Elementos) do
begin
Bandera := True;
For Contador := 1 to Elementos - Iteracion do
If Alfa[Contador] > Alfa[Contador + 1] then
Begin
Intercanbio (Alfa[Contador],Alfa[Contador + 1]);
Bandera := False
End; {* Fin del If*}
Inc(Iteración)
End {* Fin del While*}
End; {* Fin del procedimiento BurbujaB*}
begin {* Comienzo del programa *}
{* Se limpia la pantalla *}
ClrScr;
........................
{* Llamado al procedimientos BurbujaB *}
BurbujaB(Dato,Filas);
........................
end. {* Fin del programa *}
MÉTODO POR INSERCIÓN
I
Este método consiste en insertar un elemento en el vector en una parte ya ordenada de este vector y comenzar de nuevo con los elementos restantes. Por ser utilizado generalmente por los jugadores de cartas se le conoce también por el nombre de método de la baraja. Este método, para usarlo en forma optima, debe aplicarse a medida que se carga el vector. Así, por ejemplo, supongamos el caso del ejem-plo anterior.
Inserción mientras se carga el vector
Número de paso
Ing. 64 28 13 23 79 54 25 18 11
V(1) 64 28 13 13 13 13 13 13 11
V(2) 64 28 23 23 23 23 18 13
V(3) 64 28 28 28 25 23 18
V(4) 64 64 54 28 25 23
V(5) 79 64 54 28 25
V(6) 79 64 54 28
V(7) 79 64 54
V(8) 79 64
V(9) 79
Cuando ingresa el primer valor (64) se lo debe colocar en la primera posición. Cuando ingrese el se-gundo (28), se lo comparará con el primero y si es menor se desplaza el primero a la segunda posición y se coloca el segundo en dicho lugar. Caso contrario se agrega detrás del último.
Cuando ingrese el tercero se chequera con el segundo si es menor el segundo se chequea contra el primero y si es menor que este se desplaza una posición hacia abajo el segundo y el tercero, y se coloca en primer lugar el dato. Si hubiera sido mayor que el primero solo se desplaza el segundo y se hubiera colocado ahí, sino simplemente se hubiera colocado en la tercera posición. Este proceso se repite con cada elemento del vector.
Otra forma de implementar lo mismo, es compara el valor con cada elemento del vector desde el úl-timo hasta encontrar uno menor y en cada caso que es mayor (el elemento del vector) desplazar una posición hacia abajo.
Aquí vamos a desarrollar, pseudocódigo, diagrama N-S y código Pascal para este último caso.
Pseudocódigo algoritmo inserción1
para I  1 hasta N hacer
Leo Dato
J  I - 1
Mientras Auxiliar < X(J) o J >0 hacer
X(J+1)  X(J)
J  J - 1
fin mientras
X(J+1)  Auxiliar
fin para
fin
El diagrama N-S del algoritmo de inserción1:
I  1 hasta N
Auxiliar  Dato
J  I - 1
Auxiliar < X(J) o J > 0
X(J+ 1)  Auxiliar
J  J - 1
X(J+1)  Auxiliar

El código Pascal que pasmos a desarrollar para este caso se divide en un programa principal donde se lee y escribe el vector, y procedimiento donde se ordena el vector a medida que ingresan los datos.

Código Pascal del algoritmo de Imserción1:
program Ordenamiento_Insercion;
{* Ejemplo del ordenamiento por el método de Inserción *}
{* Inserción mejorado con bandera y trabaja mientras carga el vector*}
{* Archivo Insercio.Pas *}
{* Desarrollo del Ing. Fernando J. LAGE *}
{* Octubre 1998*}
uses
wincrt,windos; {* declaraciones de librerias, para correr bajo Windows *}
{* crt,dos;*} {* declaraciones de librerias, para correr bajo DOS *}
const
Enter = #13;
Ln = #13#10;
type {* Tipo conjunto *}
Numeros = 1..3200;
Vector = array[1..5]of Numeros;
Var
Dato : Vector;
I, J : Byte;
Valor : Numeros;
procedure Insercion (var Alfa:Vector; Val:Numeros; Elemento: Byte);
{* Inserción produce el ordenamiento usando el método de inserción *}
{* El cual utiliza una Bandera *}
{* Alfa es el vector que contienen los datos *}
{* Val es el dato y Elemento la cantidad de valores cargados *}
var
Iteracion : Integer; {* Iteracion reemplaza al J del pseudocódigo *}
begin {* Comienzo del procedimiento Insercion *}
Iteracion := Elemento - 1;
While (Val < Alfa[Iteracion]) and (Iteracion > 0) do
Begin
Alfa [Iteracion+1]:= Alfa [Iteracion];
Dec(Iteracion);
End; {* Fin del While *}
Alfa[Iteracion + 1] := Val;
End; {* Fin del procedimiento Insercion *}
begin {* Comienzo del programa *}
{* El programa solo juega con 5 valores porque es demostrativo *}
{* Se limpia la pantalla *}
ClrScr;
For I := 1 to 5 do
begin
{* Carga del dato *}
Write ('Dato(',I:1,')= ');
ReadLn (Valor);
{* Llamado al procedimientos Insercion *}
Insercion( Dato, Valor, I);
end;
{* Listado del dato *}
For J := 1 to 5 do
WriteLn ('Dato(',J:2,')= ',Dato[J]);
end. {* Fin del programa *}
Inserción en un vector ya almacenado
Supongamos que el vector se encuentra ya almacenado y lo queremos ordenas. En este caso co-menzamos enviando a una variable auxiliar el segundo elemento del vector (28), Luego se compara esta variable con el primer valor, si es menor se desplaza el primer valor una posición hacia abajo y se coloca en el primer lugar el contenido de la variable auxiliar, caso contrario el contenido de la variable auxiliar se coloca en la segunda posición.
Luego se toma el tercer valor del vector (13) y se lo pasa a la variable y se lo compara con el se-gundo valor del vector si es menor el segundo valor se copia en la tercera posición y se compara la varia-ble con primer valor (aquí nos encontramos en el caso anterior), caso contrario copiamos el valor auxiliar en la tercera posición.
Así sucesivamente hasta que llegamos a la última posición del vector. Debe tenerse en cuenta que cuando estamos trabajando con el elemento n del vector, los n-1 elementos anteriores ya han sido orde-nados, lo que implica que hasta la posición n-1 el vector está ordenado, y es en dicho rango donde reali-zaremos la búsqueda de la nueva posición del dato por lo cual para optimizar dicha búsqueda se podrá realizar por el método de Búsqueda Binaria, lo que aumentará la eficiencia. El desarrollo con Búsqueda Binaria se verá más adelante.
Número de paso
Ing. 1 2 3 4 5 6 7 8
V(1) 64 28 13 13 13 13 13 13 11
V(2) 28 64 28 23 23 23 23 18 13
V(3) 13 13 64 28 28 28 25 23 18
V(4) 23 23 23 64 64 54 28 25 23
V(5) 79 79 79 79 79 64 54 28 25
V(6) 54 54 54 54 54 79 64 54 28
V(7) 25 25 25 25 25 25 79 64 54
V(8) 18 18 18 18 18 18 18 79 64
V(9) 11 11 11 11 11 11 11 11 79
El algoritmo de inserción propiamente dicho no sufre modificaciones lo único que se debe modificar es el programa principal donde se lee y escribe el vector, y procedimiento donde se ordena el vector a medida que ingresan los datos.
Código Pascal del algoritmo de llamado inserción1:
begin {* Comienzo del programa *}
{* El programa solo juega con 5 valores porque es demostrativo *}
{* Se limpia la pantalla *}
ClrScr;
For I := 1 to 5 do
begin
{* Carga del dato *}
Write ('Dato(',I:1,')= ');
ReadLn (Valor);
end;
For I := 2 to 5 do
begin
{* Carga del dato *}
Valor := Dato [I];
{* Llamado al procedimientos Insercion *}
Insercion( Dato, Valor, I);
end;
{* Listado del dato *}
For J := 1 to 5 do
WriteLn ('Dato(',J:2,')= ',Dato[J]);
end. {* Fin del programa *}
El algoritmo de inserción se mejora notablemente aplicando el método de búsqueda binaria para en-contrar el lugar de inserción.
Este método tiene un número de comparaciones igual a:



ORDENACIÓN POR SELECCIÓN
Este método se basa en buscar el elemento menor del vector y colocarlo en primera posición. Luego se busca el mayor que se encuentra entre el segundo elemento y el último, y se coloca en la segunda posición, y así sucesivamente. Los pasos sucesivos a dar son:
1. Seleccionar el elemento menor del vector de n elementos.
2. Intercambiar dicho elemento con el primero.
3. Repetir estas operaciones con los n – l elementos restantes, seleccionando el segundo ele-mento; luego continuamos con los n – 2 elementos restantes hasta que sólo quede el mayor.
Aplicaremos en el ejemplo anterior el método para poder aclararlo.

Número de paso
Ing. 1 2 3 4 5 6 7 8
V(1) 64 11 11 11 11 11 11 11 11
V(2) 28 28 13 13 13 13 13 13 13
V(3) 13 13 28 18 18 18 18 18 18
V(4) 23 23 23 23 23 23 23 23 23
V(5) 79 79 79 79 79 25 25 25 25
V(6) 54 54 54 54 54 54 28 28 28
V(7) 25 25 25 25 25 79 79 54 54
V(8) 18 18 18 28 28 28 54 79 64
V(9) 11 64 64 64 64 64 64 64 79
1. Entre las posiciones V(1) y V(9) el menor valor se halla en V(9) y es el número 11 este valor lo intercambio con V(1)
2. Entre las posiciones V(2) y V(9) el menor valor se halla en V(3) y es el número 13 este valor lo intercambio con V(2)
3. Entre las posiciones V(3) y V(9) el menor valor se halla en V(8) y es el número 18 este valor lo intercambio con V(3)
4. Y así sucesivamente hasta llegar a buscar entre V(8) y V(9) (entre V(n-1) y V(n). Que será el último caso.
Ahora vamos a desarrollar, pseudocódigo, diagrama N-S y código Pascal para este algoritmo.
Pseudocódigo algoritmo selección
para I  1 hasta N - 1 hacer
Aux  V(I)
K  I
para J  J+1 hasta N hacer
si V(J) < Aux entonces
Aux  V(J)
K  J
fin_si
fin_para
V(K)  V(I)
V(I)  Aux
fin_para
El diagrama N-S del algoritmo de selección:
I  1 hasta N - 1
Aux  V(I)
K  I
J  J+1 hasta N
V(J) < Aux
Aux  V(J)
K  J



V(K)  V(I)
V(I)  Aux

Código Pascal del algoritmo del procedimiento de selección
procedure Seleccion (var Alfa: Vector; Elemento: Byte);
{* Selección produce el ordenamiento usando el método del mismo nombre *}
{* Alfa es el vector que contienen los datos *}
{* Elemento la cantidad de valores cargados *}
var
I, J, K : Integer;
Aux: Numeros;
begin {* Comienzo del procedimiento Selección *}
For I := 1 To Elemento – 1 do
Begin
Aux := Alfa[I];
K := I;
For J := I + 1 To Elemento do
If Alfa [J] < Aux then
Begin
Aux := Alfa [J];
K := J;
End; {* Fin del If y del For J *}
Alfa[K] := Alfa[I];
Alfa[I] := Aux;
End; {* Fin del For I *}
End; {* Fin del procedimiento Selección *}
Método de Shell
Es una mejora del método de inserción directa que se utiliza cuando el número de elementos a or-denar es grande. El método se denomina "Shell" en honor de su creador Donald Shell.
El método Shell se basa en fijar el tamaño de los saltos constantes, pero de más de una posición.
Supongamos un vector de elementos de n posiciones, en lugar de compara la primera con la se-gunda. la segunda con la tercera y así sucesivamente hasta comparar la n-1 posición con la posición n. Define una apertura igual a la mitad de n (entera), y compara la primera posición con la (N/2)+1, la se-gunda con la (N/”2)+2 y así sucesivamente hasta llegar (N/2)-1 con N. Con la misma apertura se repite el proceso hasta que en una vuelta no existan más cambios. Aquí es cuando se reduce la apertura a la mitad (entero) y se repite el proceso de las comparaciones, hasta que no se produzcan cambios. En esta situación se reduce el salto a la mitad. Y esto se hace así sucesivamente hasta que con salto uno en una vuelta no haya más cambios.
Aplicaremos en el ejemplo anterior el método de Shell

Número de paso
Ape 4 4 4 2 2 2 1 1
V(1) 64 64 11 11 11 11 11 11 11
V(2) 28 28 28 28 18 18 18 13 13
V(3) 13 13 13 13 13 13 13 18 18
V(4) 23 18 18 18 28 23 23 23 23
V(5) 79 11 64 64 25 25 25 25 25
V(6) 54 54 54 54 23 28 28 28 28
V(7) 25 25 25 25 64 64 64 54 54
V(8) 18 23 23 23 54 54 54 64 64
V(9) 11 79 79 79 79 79 79 79 79
El algoritmo resultante expresado con la estructura iterar será:
Pseudocódigo algoritmo Shell
inicio
E  N+1
repetir
E  ent(E/2)
repetir
Salida  Verdadero
Para I  1 hasta N – E hacer
si X(I)> X(I+ E)
entonces
AUX  X(I)
X(I)  X(I+ E)
X(I + E)  AUX
SW  Falso
fin_si (fin para)
hasta Salida = Verdadero
hasta E= 1
fin
El diagrama N-S del algoritmo de Shell:
E  N + 1
E  entero (E/2)
Salida  Verdadero
I  1 hasta N - E
X(I) < X(I+E)
Aux  X(I)
X(I)  X(I+E)
X(I+E)  Aux



Salida = Verdadero
E = 1
Código Pascal del algoritmo del procedimiento Shell
procedure Shell (var Alfa: Vector; N: Byte);
{* Inserción produce el ordenamiento usando el método de inserción *}
{* Alfa es el vector que contienen los datos *}
{* N es la cantidad de valores cargados *}

var
Salida : Boolean;
Aux : Numeros;
E, I : Byte;

begin {* Comienzo del procedimiento Shell *}
E := N + 1;
Repeat
E := E div 2;
Repeat
Salida := True;
For I := 1 To (N-E) Do
If Alfa[I] > Alfa[I+E] Then
Begin
Aux := Alfa [I];
Alfa[I] := Alfa[I+E];
Alfa[I+E]:= Aux;
Salida := False
End
Until Salida
Until E= 1
End; {* Fin del procedimiento Shell*}
Método de ordenación rápida ("quicksort")
El método de ordenación rápida (quicksort) para ordenar o clasificar un vector o lista de elementos (array), se basa en el hecho de que es más rápido y fácil de ordenar dos listas pequeñas que una lista grande. Se denomina método de ordenación rápida y es debido Hoare.
El método se basa en la estrategia típica de "divide y vencerás. La lista a clasificar almacenada en un vector o array se divide en dos: una que contiene los valores menores o iguales a un cierto valor espe-cífico y otra con todos los valores mayores que ese valor. El valor elegido puede ser cualquier valor arbi-trario del vector y se denomina valor pivote.
El primer paso es dividir la lista original en dos sublistas o subvectores y un valor de separación.
Así, el vector V se divide en tres partes:
- Subvector VI que contiene los valores inferiores o iguales.
- El elemento de separación.
- Subvector VD que contiene los valores superior o iguales.
Los subvectores VI y VD no están ordenados, excepto en el caso de reducirse a un elemento.
Consideremos la lista de valores.
18 11 27 13 9 4 16
Se elige un pivote, 13. Se recoge la lista desde el extreme izquierdo y se busca un elemento mayor que 13 (se encuentra el 18). A continuación, se busca desde el extremo derecho un valor menor que 13 (se encuentra el 4).
18 11 27 13 9 4 16
Se intercambian estos dos valores y se produce la lista
4 11 27 13 9 18 16
Se sigue recorriendo el vector por la izquierda y se localiza el 27, y a continuación otro valor bajo se encuentra a la derecha (el 9). Intercambiar estos dos valores y se obtiene
4 11 9 13 27 18 16
Al intentar este proceso una vez más, se encuentra que las exploraciones de los dos extremes vie-nen juntos sin encontrar ningún futuro valor que esté "fuera de lugar".
En este punto se conoce que todos los valores a la derecha son mayores que todos los valores a la izquierda del pivote. Se ha realizado una partición en la lista original que se ha quedado dividida en dos listas más pequeñas:
4 11 9 [13] 27 18 16
Ninguna de ambas listas se encuentran ordenadas; sin embargo, basados en los resultados de esta primera partición, se pueden ordenar ahora las dos particiones independientemente. Esto es, si ordena-mos la lista
4 11 9 y 27 18 16 la lista quedará ordenada.
En el ejemplo siguiente, se parte de otra lista.
50, 30, 20, 80, 90, 70, 95, 85, 10, 15, 75, 25
el autor dice que se debe tomar como pivote el número 50, dividir la lista en dos y repetir los pasos anteriores.
Es sin duda quicksort el método más rápido de ordenación que existe. Pero el mismo se basa en que el pivote será el elemento que quedará en el medio de la lista. Crear un algoritmo que sirva para quicksort es relativamente sencillo. Lograr un algoritmo que determine en una lista dada cual será el ele-mento pivote es lo complejo. Por eso cada empresa de software tiene su propio algoritmo de quicksort.