gegegege

UAA – Sistemas Electrónicos

3

Estructura de Datos

Serna

Métodos de Ordenamiento

3.1

Tipos de Ordenamiento

La ordenación o clasificación de datos consiste en la disposición de los mismos de acuerdo con
algún valor o característica. Por ejemplo, cada elemento de una agenda telefónica tiene un campo
nombre, un campo dirección y un campo número telefónico. Por lo regular losdatos en la agenda
se encuentran organizados en un orden de la A la Z. De la misma forma un lista ó vector de datos
se dice que esta ordenado de manera ascendente, si X [ i ] = X [ i +1].
El proceso de ordenación es uno de los mecanismos más interesantes cuando llega el momento
de mostrar que existen múltiples soluciones para un mismo problema, y que cada solución
algorítmica tiene sus propiasventajas y desventajas.
Una forma de medir la eficiencia de un algoritmo de esta clase, es verificar el número de
comparaciones entre valores clave, además del número de movimientos que se tengan que
realizar entre elementos (intercambios) de la lista.
Los métodos de ordenamiento que trabajan con estructuras de datos residentes en memoria
principal se denominan Ordenamientos Internos,mientras que las implementaciones que utilizan
estructuras de datos residentes en archivos se conocen como Ordenamientos externos.

3.2

Ordenamiento Interno

Los métodos de ordenamiento interno trabajan en memoria principal y sus implementaciones son
muy variadas, de manera que la elección del algoritmo adecuado debe realizarse con criterios de
eficiencia (tiempo y ejecución) y en función de lamemoria disponible. Dividiremos los métodos en
dos grandes grupos:
•
•

Directos (burbuja, selección e inserción).
Logarítmicos (Shell sort, Merge sort, Heap sort, Quick sort, Radix).

En el caso de listas pequeñas, los métodos directos se desempeñan de manera relativamente
eficientes, ya que la codificación del algoritmo correspondiente no es compleja. Su uso es muy
frecuente. Sinembargo, en arreglos grandes las ordenaciones directas resultan ineficientes y se
necesitara un método logarítmico para su solución.

3.2.1 Ordenación por intercambio (burbuja)
Es uno de los métodos relativamente más sencillo e intuitivo, pero también resulta ser muy
ineficiente. Se basa en la ordenación por cambio, y recibe su nombre de la semejanza con las
burbujas de un depósito de agua dondecada burbuja busca su propio nivel.
Los pasos a efectuar en el caso de una ordenación ascendente (en el caso de la ordenación
descenderte solo habría que cambiar el signo de comparación) son:
1. Comparar el primer y segundo elemento, intercambiarlos si el primero es mayor que el
segundo; luego se compara el primero con el tercero, intercambiándose en caso necesario, y el
proceso se repitehasta llegar al último elemento. De este modo, tras la primera iteración la
casilla primera conservara el elemento más pequeño de esa iteración.

1

UAA – Sistemas Electrónicos

Estructura de Datos

Serna

2. Se repite el paso anterior, pero ahora con el segundo y tercero, en caso de ser necesario se
intercambian, y así hasta llegar a comparar el segundo con el ultimo.
Consideremos elsiguiente ejemplo. Se cuenta con un vector de 6 posiciones donde se inicia una
lista de números { 7, 2, 8, 3, 5, 1 }, la cual será ordenada en forma ascendente { 1, 2, 3, 5, 7, 8 },
observe como se declara una variable constante entera llamada n la cual tiene un valor de 6,
enseguida se declara un vector de tipo entero que contendrá una cantidad n de casillas, en este
caso 6, declaramostambién las variables i y j que nos ayudaran a desplazarnos entre casilla y
casilla para hacer las comparaciones. Y finalmente la variable tem, almacenara temporalmente el
valor a intercambiar entre las casillas que lo necesiten.
El proceso sería de la siguiente manera:
1ra iteración, i permanece fijo en la casilla 0 y j se incrementa hasta llegar al último elemento:
{ 7, 2, 8, 3, 5, 1 } j = 1,...