Clasificación

Eficiencia de algoritmos:

   

Algoritmo	Caso promedio	Caso peor
Simples	O(n^2)
QuickSort	O(n · log n)	O(n^2)
HeapSort		O(n · log n)
MergeSort		O(n · log n)
Por Urnas o Por Cubetas		O(n)

ALGORITMOS SIMPLES DE CLASIFICACIÓN

Problemas con n < 100
   

❶  CLASIFICACIÓN POR INTERCAMBIO. BURBUJA O BUBBLESORT

   
Se recorre varias veces el vector de abajo hacia arriba y, al hacer esto, si hay dos elementos adyacentes que no están en orden, se invierten. El efecto producido por esta operación es que en el primer recorrido el registro con valor clave menor sube al primer valor del vector.
   

❷  CLASIFICACIÓN POR INSERCIÓN

   
En el i-ésimo recorrido se inserta el i-ésimo elemento A[i] en el lugar correcto que corresponda de la lista {A[0] … A[i-1]}, los cuales fueron ordenados previamente. Después de hacer esta inserción, se encuentran clasificados los registros colocados en {A[0] … A[i]}.
   

❸  CLASIFICACIÓN POR SELECCIÓN

   
La idea es que en el i-ésimo recorrido se seleccione el registro con la clave más pequeña de la lista {A[i] … A[n-1]} y se intercambie con A[i]. Como resultado, después de i pasadas, los i registros menores ocupan {A[0] … A[i]} en el orden clasificado.
   

è Método de selección es el más eficiente de los 3: debido a que hace un menor nº de movimientos.

ALGORITMOS RÁPIDOS DE CLASIFICACIÓN

①  QUICKSORT

   
La esencia del método consiste en clasificar un vector {A[0] … A[n-1 ]} tomando en el vector un valor clave “v” como elemento pivote, alrededor del cual reorganizar los elementos del vector. Se permutan los elementos del vector con el fin de que para alguna “j”, todos los registros con claves menores que “v” aparezcan en {A[0] … A[j]} y todos aquellos con claves mayores aparezcan en {A[j+1] … A[n-1]}.