técnicas de ordenación en c++

Métodos
De
Ordenación
Leyva Larragoiti Ivan

septiembre 5

2013
Reporte de
prácticas
(Practica 1)

Objetivo.
Conocer y aplicar los métodos de ordenación básicos los cuales son: método de
intercambio, ordenación por selección, ordenación por inserción, ordenación por burbuja
y ordenación por burbuja mejorado.

Marco Teórico.
La ordenación o clasificación de datos consiste en ladisposició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 los datos en la agenda se encuentran organizados en un orden de la A la Z. De la
misma forma un lista o 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 propias ventajas 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 movimientosque se tengan
que realizar entre elementos (intercambios) de la lista.
Ordenación por 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 donde cada burbuja busca su propio nivel. Los
pasos a efectuar en el caso de unaordenació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 repite hasta llegar al último elemento. De este modo, tras la
primera iteración lacasilla primera conservara el elemento más pequeño de esa iteración.
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 el
siguiente 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 formaascendente { 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, declaramos tambié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.
Algoritmo de Burbuja mejorado
Existe una versión mejorada de dicho algoritmo en donde se integra una variable que
funge como switch (bandera) que permite detectar el momento en que ya no se
presenten mas intercambios aunque su mejora no suele ser tan importante pues el
algoritmo sigue comportándose como unaordenación cuadrática O(n2).
Método de Inserción
Este método también se denomina “método del jugador de cartas”, por la semejanza con
la forma de clasificar las cartas de una baraja, insertando cada carta en el lugar adecuado.
El algoritmo ordena los dos primeros elementos de la lista, a continuación el tercer
elemento se inserta en la posición que corresponda, el cuarto se inserta en la lista de treselementos, y así sucesivamente. Este proceso continua hasta que la lista este totalmente
ordenada. Sea una lista A [1], A [2],... A[n]. Los pasos a dar para una ordenación
ascendente son:
1. Ordenar A [1] y A [2].
2. Comparar A[3] con A[2], si A[3] es mayor o igual a que A[2], sigue con el siguiente
elemento si no se compara A[3] con A[1]; si A[3] es mayor o igual que A[1], insertar A[3]...