Algoritmos de ordenación y búsqueda

6
ALGORITMOS DE ORDENACIÓN Y BÚSQUEDA

OBJETIVOS
Después del estudio de este capítulo usted podrá: • Conocer los algoritmos basados en el intercambio de elementos. • Conocer el algoritmo de ordenación por inserción. • Conocer el algoritmo de selección. • Distinguir entre los algoritmos de ordenación basados en el intercambio y en la inserción. • Deducir la eficiencia de los métodos básicosde ordenación. • Conocer los métodos más eficientes de ordenación. • Aplicar métodos mas eficientes de ordenación de arrays (arreglos). • Diferenciar entre búsqueda secuencial y búsqueda binaria.

6.6. Ordenación por burbuja. 6.7. Ordenación Shell. 6.8. Ordenación rápida (quicksort). 6.9. Ordenación Binsort y Radixsort. 6.10. Búsqueda en listas: búsqueda secuencial y binaria. RESUMEN EJERCICIOSPROBLEMAS

CONCEPTOS CLAVE
• • • • • • • • • Ordenación numérica. Ordenación alfabética. Complejidad cuadrática. Ordenación por burbuja. Ordenación rápida. Residuos. Ordenación por intercambio. Ordenación por inserción. Búsqueda en listas: búsqueda secuencial y búsqueda binaria. • Complejidad logarítmica. • Ordenación por selección.

CONTENIDO
6.1. 6.2. 6.3. 6.4. 6.5. Ordenación. Algoritmosde ordenación básicos. Ordenación por intercambio. Ordenación por selección. Ordenación por inserción.

INTRODUCCIÓN
Muchas actividades humanas requieren que en ellas las diferentes colecciones de elementos utilizados se coloquen 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 unaentrega eficiente; los anuarios o listines telefónicos ordenan sus clientes por orden alfabético de apellidos con el fin último de encontrar fácilmente el número de teléfono deseado; los estudiantes de

165

166

Algoritmos y estructuras de datos

una clase en la universidad se ordenan por sus apellidos o por los números de expediente, etc. Por esta circunstancia una de las tareas querealizan 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 de ordenación más usuales y su implementación en C. De igual modo se estudiará el análisis de los algoritmos utilizadosen diferentes métodos de ordenación con el objetivo de conseguir la máxima eficiencia en su uso real. En el capítulo se analizarán los métodos básicos y avanzados más empleados en programas profesionales.

6.1. 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 auno 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 deordenació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 almacenadosen 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 a[j+1]) { /* elementos desordenados, es necesario intercambio */ long aux; interruptor = 1; aux = a[j]; a[j] = a[j+1]; a[j+1] = aux; } } }

Una...