HEAPSORT

Otro de los algoritmos rápidos es el de Heapsort. Es un algoritmo de ordenación no recursivo apoyado en otra estructura de datos como son los montículos (Heap).
Consiste en almacenar todos los elementos del conjunto a ordenar en un heap, y luego extraer el nodo raiz del montículo en sucesivas iteraciones obteniendo el conjunto ordenado.
La clave fundamental de este algoritmo esta en una propiedad de los heap, por lo cual, el nodo raiz contiene siempre el menor elemento (o mayor, según el ordenamiento que queramos realizar) de todos los almacenados en el.
Aquí tenemos una animación gráfica del funcionamiento de este algoritmo:

QUICKSORT CENTRAL

El siguiente algoritmo define el método de ordenación Quicksort utilizando como elemento pivote el elemento que esta en el medio de la lista de elementos:


función QUICKSORT (variables v: vector; pi, pf: enteros)
   variables 
      i, j: índice; 
      x: elemento 
   fvar
   comienzo
   si pi < pf entonces
      x = a[(pi + pf)/2];
      i = pi; 
      j = pf;
      repetir
         mientras a[i] < x hacer 
            i=i+1 fmientras
         mientras a[j] > x hacer 
            j=j-1 fmientras
         si i <= j entonces
            SWAP (a[i], a[j]); 
            i = i + 1; 
            j = j - 1;
         fsi
      mientras i <= j;
      QUICKSORT (a, pi, j);
      QUICKSORT (a, i, pf);
   fsi
fin

• Los elementos pi y pf serán los índices inferior y posterior respectivamente del vector.
• Como podemos observar utilizamos como pivote el elemento que esta en la mitad del vector:  

             x = a[(pi + pf)/2];

• Y una vez colocado en su posición hacemos una llamada recursiva con los dos subvectores, el de la parte derecha (desde i hasta pf),  y el de la parte izquierda (desde pi hasta j).
• Este algoritmo define ordenación ascendente. Si lo que quisiésemos fuese lo contrario solo habría que modificar estas líneas:

             mientras a[i] > x hacer 

                i=i+1 fmientras

            mientras a[j] < x hacer 

                j=j-1 fmientras

QUICKSORT

Quizá uno de los mejores y mas rápidos algoritmos sea el Quicksort.

El algoritmo implementado bajo el esquema de Divide y Vencerás, que como su propio nombre indica resuelve un problema difícil, dividiéndolo en partes mas simples tantas veces como sea necesario; esta basado en los siguientes fundamentos:

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Éste según la modalidad que hallamos elegido podrá ser el primero, último, central,...
• Ubicar los demás elementos del conjunto a ordenar como queramos hacerlo. O los mas pequeños a su izquierda y los mayores a la derecha (orden creciente), o los mas pequeños a su derecha y los mas grandes a su izquierda (orden creciente).
• Dividimos así la lista en dos sublistas, porque el elemento pivote ya queda ordenado. La sublista izquierda y la derecha.
• Así repetimos el proceso de forma recursiva para cada sublista.

Ejemplo Gráfico Quicksort

CLASIFICACIÓN GENERAL

Debido a la gran diversidad de algoritmos de ordenación y "sucedáneos", podemos hacer una clasificación general:
- Directos: algoritmos cortos y fáciles de entender, son especialmente adecuados para problemas relativamente pequeños. Clasificados a su vez en tres categorías de acuerdo al método base empleado: ordenamiento por selección, por intercambio y por inserción.
- Indirectos: métodos mas complicados de entender, producidos por un refinamiento de los anteriores; sobre todo para problemas de gran tamaño, donde los anteriores producen un "gran coste temporal". En esta clasificación podemos nombrar algoritmos como Quicksort, Mergesort o algoritmos basados en otras estructuras (árboles) como el Heapsort.

ALGORITMOS DE ORDENACIÓN

A menudo se nos presentan un sinfín de problemas donde aparecen estructuras que almacenan datos de todo tipo. Quizá una de las estructuras mas utilizadas son los vectores o arrays.
Un vector es un conjunto finito de elementos del mismo tipo. Uno de los aspectos importantes es la necesidad de la ordenación de cualquier tipo de estos elementos. Esto permitirá acceder de forma directa a cualquiera de los elementos que forman ese conjunto de datos, para ello simplemente basta con indicar la posición que ocupa el elemento en el vector.
Es ahí donde aparece uno de los grandes problemas de la Programación: la ordenación de estos elementos.
Existe una gran cantidad de formas de realizarlo en base a una serie de factores, donde fundamentalmente influye la complejidad temporal de estos algoritmos.
¡Si!, el "tiempo" que tarda en realizarse. Cuando hablamos de tamaños pequeños de problema ese factor no es verdaderamente importante. Sin embargo aumenta gradualmente a medida que esos tamaños se van haciendo grandes.
El motivo de este blog, no es nada mas que eso. Intentar realizar una clasificación lo mas acertada posible, y un análisis de cada uno de los algoritmos.