Lección 17 · 17 de 20
Quicksort y búsqueda binaria · Pascal
Programe quicksort y la búsqueda binaria en Pascal con arrays abiertos y recursión, y vea por qué buscar en una lista ordenada es tan rápido.
Quicksort ordena eligiendo un pivote y colocando a su izquierda los valores menores y a su derecha los mayores; después repite lo mismo con cada lado. Esta versión (la partición de Lomuto) toma como pivote el último elemento, a[hi].
La variable i marca la frontera de los menores: el bucle for recorre el tramo y, cada vez que encuentra un valor menor que el pivote, lo intercambia con a[i] y adelanta la frontera. Al terminar, el pivote se coloca en a[i], que ya es su sitio definitivo, y las dos llamadas recursivas ordenan cada lado si tiene más de un elemento.
El parámetro var a: array of Integer es un array abierto: acepta arrays de cualquier tamaño y, al ser var, los ordena en su sitio. El array codes se declara ya con sus valores, algo que Free Pascal 3.2 permite también con los arrays dinámicos. En promedio quicksort hace unas n·log n comparaciones; en el peor caso, con datos ya ordenados y este pivote, llega a n².
La búsqueda binaria solo funciona sobre datos ordenados: mira el elemento central y descarta la mitad donde no puede estar. Find lo hace de forma recursiva y devuelve -1 con Exit(-1) cuando el tramo se queda vacío. Con un millón de códigos bastan unas 20 comparaciones.
Código · main.pas
program main;procedure QuickSort(var a: array of Integer; lo, hi: Integer);var i, j, tmp: Integer;begin i := lo; for j := lo to hi - 1 do if a[j] < a[hi] then // a[hi] is the pivot begin tmp := a[i]; a[i] := a[j]; a[j] := tmp; Inc(i); end; tmp := a[i]; a[i] := a[hi]; a[hi] := tmp; // the pivot to its final place if lo < i - 1 then QuickSort(a, lo, i - 1); // smaller values, on the left if i + 1 < hi then QuickSort(a, i + 1, hi); // bigger ones, on the rightend;function Find(const a: array of Integer; target, lo, hi: Integer): Integer;var mid: Integer;begin if lo > hi then Exit(-1); // nothing left to look at mid := (lo + hi) div 2; if a[mid] = target then Result := mid else if a[mid] < target then Result := Find(a, target, mid + 1, hi) else Result := Find(a, target, lo, mid - 1);end;var codes: array of Integer = (4021, 1187, 9350, 2764, 5512, 3308, 7045); code: Integer;begin QuickSort(codes, 0, High(codes)); for code in codes do Write(code, ' '); WriteLn(LineEnding, '5512 is at index ', Find(codes, 5512, 0, High(codes))); WriteLn('6000 is at index ', Find(codes, 6000, 0, High(codes)));end.Salida · fpc main.pas && ./main
1187 2764 3308 4021 5512 7045 9350 5512 is at index 4 6000 is at index -1
Para recordar
- Quicksort: partir alrededor de un pivote y ordenar cada lado.
- Tras la partición, el pivote ya está en su sitio definitivo.
var a: array of Integeracepta arrays de cualquier tamaño.- La búsqueda binaria necesita datos ordenados.
- Cada paso de la búsqueda binaria descarta la mitad.
Ejercicio
Cambie la comparación de QuickSort para ordenar de mayor a menor y adapte Find para que siga funcionando con ese orden.