Métodos de ordenamiento y búsqueda.

ORDENACIÓN
La ordenación o clasificación de datos (sort, en inglés) es una operación consistente en disponer
un conjunto —estructura— de datos en algún determinado orden con respecto a uno de los campos
de elementos del conjunto. Por ejemplo, cada elemento del conjunto de datos de una guía telefónica
tiene un campo nombre, un campo dirección y un campo número de teléfono; la guía telefónica está
dispuesta en orden alfabético de nombres; los elementos numéricos se pueden ordenar en orden
creciente o decreciente de acuerdo al valor numérico del elemento. En terminología de ordenación,
el elemento por el cual está ordenado un conjunto de datos (o se está buscando) se denomina clave.
Una colección de datos (estructura) puede ser almacenada en un archivo, un array (vector o
tabla), un array de registros, una lista enlazada o un árbol. Cuando los datos están almacenados en
un array, una lista enlazada o un árbol, se denomina ordenación interna. Si los datos están almacenados
en un archivo, el proceso de ordenación se llama ordenación externa.
Una lista se dice que está ordenada por la clave k si la lista está en orden ascendente o descendente
con respecto a esta clave. La lista se dice que está en orden ascendente si:
i < j implica que k[i] <= k[j]
y se dice que está en orden descendente si:
i > j implica que k[i] <= k[j]
para todos los elementos de la lista. Por ejemplo, para una guía telefónica, la lista está clasificada en
orden ascendente por el campo clave k, donde k[i] es el nombre del abonado (apellidos, nombre).
4 5 14 21 32 45 orden ascendente
75 70 35 16 14 12 orden descendente
Zacarias Rodriguez Martinez Lopez Garcia orden descendente
Los métodos (algoritmos) de ordenación son numerosos, por ello se debe prestar especial atención
en su elección. ¿Cómo se sabe cuál es el mejor algoritmo? La eficiencia es el factor que mide
la calidad y rendimiento de un algoritmo. En el caso de la operación de ordenación, dos criterios se
suelen seguir a la hora de decidir qué algoritmo —de entre los que resuelven la ordenación— es el
más eficiente: 1) tiempo menor de ejecución en computadora; 2) menor número de instrucciones.
Sin embargo, no siempre es fácil efectuar estas medidas: puede no disponerse de instrucciones para
medida de tiempo —aunque no sea éste el caso del lenguaje C—, y las instrucciones pueden variar,
dependiendo del lenguaje y del propio estilo del programador. Por esta razón, el mejor criterio para
medir la eficiencia de un algoritmo es aislar una operación específica clave en la ordenación y
contar el número de veces que se realiza. Así, en el caso de los algoritmos de ordenación, se
utilizará como medida de su eficiencia el número de comparaciones entre elementos efectuados. El
algoritmo de ordenación A será más eficiente que el B, si requiere menor número de comparaciones.
166 Algoritmos y estructuras de datos
Así, en el caso de ordenar los elementos de un vector, el número de comparaciones será función del
número de elementos (n) del vector (array). Por consiguiente, se puede expresar el número de
comparaciones en términos de n (por ejemplo, n+4, o bien n2 en lugar de números enteros (por
ejemplo, 325).
En todos los métodos de este capítulo, normalmente —para comodidad del lector— se utiliza el
orden ascendente sobre vectores o listas (arrays unidimensionales).
Los métodos de ordenación se suelen dividir en dos grandes grupos:
• directos burbuja, selección, inserción
• indirectos (avanzados) Shell, ordenación rápida, ordenación por mezcla, Radixsort
En el caso de listas pequeñas, los métodos directos se muestran eficientes, sobre todo porque los
algoritmos son sencillos; su uso es muy frecuente. Sin embargo, en listas grandes estos métodos se
muestran ineficaces y es preciso recurrir a los métodos avanzados.