Algoritmos de ordenacion y busqueda

Capítulo
Algoritmos de ordenación y búsqueda
Contenido

9

• Ordenación • Ordenación por burbuja • Ordenación por selección • Ordenación por inserción • Ordenación Shell • Ordenación rápida (quicksort) • Búsqueda en listas: búsqueda secuencial y binaria • Resumen • Ejercicios • Problemas

Introducción
Muchas actividades humanas requieren que diferentes colecciones de elementosutilizados se pongan en un orden específico. Las oficinas de correo y las empresas de mensajería ordenan el correo y los paquetes por códigos postales con el objeto de conseguir una entrega eficiente; los anuarios o directorios telefónicos se ordenan por orden alfabético de apellidos con el fin último de encontrar fácilmente el número de teléfono deseado. Los estudiantes de una clase en launiversidad se ordenan por sus apellidos o por los números de expediente. Por esta circunstancia una de las tareas que realizan más frecuentemente las computadoras en el procesamiento de datos es la ordenación. El estudio de diferentes métodos de ordenación es una tarea intrínsecamente interesante desde un punto de vista teórico y, naturalmente, práctico. El capítulo estudia los algoritmos y técnicas deordenación más usuales y su implementación en C. De igual modo se estudiará el análisis de los diferentes métodos de ordenación con el objeto de conseguir la máxima eficiencia en su uso real. En el capítulo se analizarán los métodos básicos y los más avanzados empleados en programas profesionales.

Ordenación

265

Conceptos clave
• • • • Búsqueda Complejidad del algoritmo IntercambioOrdenación por inserción • Ordenación por selección • Ordenación por burbuja • Ordenación rápida

Ordenación
La ordenación o clasificación de datos (sort en inglés) es una operación que consiste en disponer un conjunto (estructura) de datos en algún determinado orden con respecto a uno de los campos de los elementos del conjunto. Por ejemplo, cada elemento del conjunto de datos de una guíatelefó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 forma creciente o decreciente de acuerdo con el 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. Unacolección de datos (estructura) puede ser almacenada en un archivo, un arreglo (vector o tabla), un arreglo de registros, una lista enlazada o un árbol. Cuando los datos están almacenados en un arreglo, 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. Se dice que una lista está ordenadapor la clave k si la lista está en orden ascendente o descendente con respecto a esta clave. Se dice que la lista está en orden ascendente si:
i < j

implica que k[i] a[j+1]) { /* elementos desordenados, es necesario intercambio */ long aux; a[j] = a[j+1]; a[j+1] = aux; } } }

Una modificación del algoritmo anterior puede ser utilizar, en lugar de una variable bandera interruptor, unavariable indiceIntercambio que se inicie a 0 (cero) al principio de cada pasada y se establezca al índice del último intercambio, de modo que cuando al terminar la pasada el valor de
indiceIntercambio siga siendo 0 implicará que no se ha producido ningún intercambio (o bien

que el intercambio ha sido con el primer elemento) y, por consiguiente, la lista estará ordenada. En caso de no ser 0, el valorde indiceIntercambio representa el índice del vector a partir del cual los elementos están ordenados. La codificación en C de esta alternativa sería:
/* Ordenación por burbuja: array de n elementos Se realizan una serie de pasadas mientras indiceIntercambio > 0 */ void ordBurbuja2 (long a[], int n) { int i, j; int indiceIntercambio; /* i es el índice del último elemento de la sublista */ i =...