Ordenación Avanzada

Ordenación por intercalación (Merge Sort)

Este algoritmo consiste en dividir el arreglo en dos mitades (hasta llegar a arreglos de un elemento), ordenar cada mitad y luego intercalarlas.

En pseudocódigo:

\begin{aligned} &\proc \; merge\_sort(\inout \; a : \array [1..n] \; \of \; T) \\ &\quad merge\_sort\_rec(a, 1, n) \\ &\bfend \; \proc \\ &\\ &\{ \; n \geq rgt \geq lft > 0 \land a = A \; \} \\ &\proc \; merge\_sort\_rec(\inout \; a : \array [1..n] \; \of \; T, \; \bfin \; lft, rgt: \nat) \\ &\quad \var \; mid : \nat \\ &\quad \if \; rgt > lft \; \then \\ &\quad \quad mid := (lft+rgt) \; \textnormal{div} \; 2 \\ &\quad \quad merge\_sort\_rec(a, lft, mid) \\ &\quad \quad \{- \;\; a[lft,mid] \; \textnormal{permutación ordenada de } A[lft,mid] \;\; -\} \\ &\quad \\ &\quad \quad merge\_sort\_rec(a, mid+1, rgt) \\ &\quad \quad \{- \;\; a[mid+1,rgt] \; \textnormal{permutación ordenada de } A[mid+1,rgt] \;\; -\} \\ &\quad \\ &\quad \quad merge(a, lft, mid, rgt) \\ &\quad \quad \{- \;\; a[lft,rgt] \; \textnormal{permutación ordenada de } A[lft,rgt] \;\; -\} \\ &\quad \fi \\ &\bfend \; \proc \\ &\{ \; a \; \textnormal{es permutación de} \; A \; \land \; a[lft,rgt] \; \textnormal{permutación ordenada de} \; A[lft, rgt] \; \} \\ \end{aligned}

El arreglo dejará de dividirse cuando este tenga un solo elemento, en ese caso, ya estará ordenado.

El procedimiento $merge$ se encarga de intercalar dos arreglos ordenados, en la siguiente imagen se puede ver su invariante, donde cada sublista está siempre ordenada antes de intercalarlas.

Su pseudocódigo es:

\begin{aligned} &\proc \; merge(\inout \; a : \array [1..n] \; \of \; T, \; \bfin \; lft, mid, rgt : \nat) \\ &\quad \var \; tmp: \array [1..n] \; \of \; T; \; j, k : \nat \\ &\quad \for \; i := lft \; \too \; mid \; \do \\ &\quad \quad tmp[i] := a[i] \\ &\quad \quad \{- \;\; \textnormal{copia con la primera mitad} \; a[lft,mid] \;\; -\} \\ &\quad \od \\ &\quad j := lft \\ &\quad k := mid+1 \\ &\quad \for \; j := lft \; \too \; rgt \; \do \\ &\quad \quad \if \; j \leq mid \; \land \; (k > rgt \; \lor \; tmp[j] \leq a[k]) \; \then \\ &\quad \quad \quad a[i] := tmp[j] \\ &\quad \quad \quad j := j+1 \\ &\quad \quad \else \\ &\quad \quad \quad a[i] := a[k] \\ &\quad \quad \quad k := k+1 \\ &\quad \quad \fi \\ &\quad \od \\ &\bfend \; \proc \\ \end{aligned}

Se considera el caso en el que todos los elementos de la segunda mitad se comparan, lo cual sucede si $k > rgt$ , por lo que completamos con los elementos restantes de la primera mitad.

Este algoritmo posee una complejidad de $O(n \log n)$ en el peor caso.

Ordenación rápida (Quick Sort)

Se toma el primer elemento del arreglo como pivote, se colocan los elementos menores a la izquierda y los mayores a la derecha. Luego se repite el proceso con las dos mitades.

En pseudocódigo:

\begin{aligned} &\proc \; quick\_sort(\inout \; a : \array [1..n] \; \of \; T) \\ &\quad quick\_sort\_rec(a, 1, n) \\ &\bfend \; \proc \\ &\\ &\{ \; 0 \leq rgt \leq n \; \land \; 1 \leq lft \leq n+1 \; \land \; lft-1 \leq rgt \; \land \; a = A \; \} \\ &\proc \; quick\_sort\_rec(\inout \; a : \array [1..n] \; \of \; T, \; \bfin \; lft, rgt: \nat) \\ &\quad \var \; pivot : \nat \\ &\quad \if \; rgt > lft \; \then \\ &\quad \quad partition(a, lft, rgt, pivot) \\ &\quad \quad quick\_sort\_rec(a, lft, pivot-1) \\ &\quad \quad quick\_sort\_rec(a, pivot+1, rgt) \\ &\quad \fi \\ &\bfend \; \proc \\ &\{ \; a \; \textnormal{es permutación de} \; A \; \land \; a[lft,rgt] \; \textnormal{permutación ordenada de} \; A[lft, rgt] \; \} \\ \end{aligned}

La invariante de $partition$ puede verse en la siguiente imagen, donde $lft = pivot$ y se cumple que todos los elementos a la izquierda son menores o iguales a $a[pivot]$ y los de la derecha son mayores a $a[piv]$ .

El pseudocódigo de $partition$ es:

\begin{aligned} &\proc \; partition(\inout \; a : \array [1..n] \; \of \; T, \; \bfin \; lft, rgt : \nat, \; \out \; pivot : \nat) \\ &\quad \var \; i, j : \nat \\ &\quad pivot := lft \\ &\quad i := lft+1 \\ &\quad j := rgt \\ &\quad \while \; i \leq j \; \do \\ &\quad \quad \if \; a[i] \leq a[pivot] \; \rightarrow \; i := i+1 \\ &\quad \quad \quad \; a[j] \geq a[pivot] \; \rightarrow \; j := j-1 \\ &\quad \quad \quad \; a[i] > a[pivot] \; \land \; a[j] < a[pivot] \; \rightarrow \; swap(a, i, j) \\ &\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \; i := i + 1 \\ &\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \; j := j - 1 \\ &\quad \quad \fi \\ &\quad \od \\ &\quad swap(a,pivot,j) \quad\; \{- \;\;\textnormal{dejando al} \; pivot \; \textnormal{en una posición más central} \;\; -\} \\ &\quad pivot := j \quad\quad\quad\quad \{- \;\; \textnormal{señalando la nueva posición del} \; pivot \;\; -\} \\ &\bfend \; \proc \\ \end{aligned}

Comparamos si $a[i]$ es menor o igual al pivote y si $a[j]$ es mayor o igual. De ser el caso aumentamos los índices, de lo contrario intercambiamos los elementos. Por último, ubicamos correctamente a $a[pivot]$ y asignamos su nuevo índice.

En el peor caso, la complejidad de este algoritmo en el peor caso es de $O(n^2)$ , pero en promedio es de $O(n \log n)$ . Por lo general es más rápido que Merge Sort, es una buena opción para conjuntos de datos que caben en memoria. De lo contrario, Merge Sort es más eficiente.