Algoritmo

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étodosbásicos de 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.

CONTENIDO
6.1.
6.2.
6.3.
6.4.
6.5.

Ordenación.
Algoritmos de ordenación básicos.
Ordenación por intercambio.
Ordenación por selección.
Ordenación por inserción.

6.6. Ordenaciónpor 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
EJERCICIOS
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 porintercambio.
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 utilizados se coloquen en un orden específico. Las oficinas de correo y las empresas de mensajería
ordenan el correo y los paquetes porcódigos postales con el objeto de conseguir una entrega
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. Poresta 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 seestudiará el análisis de los algoritmos utilizados en 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 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 alvalor 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, sedenomina 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 a[j+1])
{
/* elementos desordenados, es necesario intercambio */
long aux;...