Algoritmos De Busqueda Y Ordenacion

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 inter- cambio de elementos.
• Conocer el algoritmo de ordenación por in-
serción.
• Conocer el algoritmo de selección.
• Distinguir entre los algoritmos deordena- ción basados en el intercambio y en la in-
serción.
• Deducir la eficiencia de los métodos bási- cos de ordenación.
• Conocer los métodos más eficientes de or- denación.
• Aplicar métodos mas eficientes de ordena-
ción de arrays (arreglos).
• Diferenciar entre búsqueda secuencial y búsqueda binaria.

CONTENIDO

6.1. Ordenación.6.2. Algoritmos de ordenación básicos.
6.3. Ordenación por intercambio.
6.4. Ordenación por selección.
6.5. Ordenación por inserción.
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 secuen- cial y binaria.

RESUMENEJERCICIOS PROBLEMAS
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.INTRODUCCIÓN

Muchas actividades humanas requieren que en ellas las diferentes colecciones de elementos utili- zados 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 una entrega eficiente; los anuarios o listines telefónicos ordenan sus clientes por orden alfabéticode apelli- dos 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 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 de ordenación más usuales y su implementación en C. De igual modo se estudiará el análi-
sis de los algoritmos utilizados en diferentes métodos de ordenación con el objetivo de conseguirla 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 a uno de los campos de elementos delconjunto. 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 almace- nados en un archivo, el proceso de...