como ordenar un vector

Algoritmos elementales para ordenar un vector
Pablo Santamaría
v0.1 (Junio 2007)

1.

Introducción

Una de las operaciones más importantes (y demandantes) en computación es ordenar un ciertoconjunto de datos. Para nuestros propósitos de cálculo científico, tal colección de datos es simplemente un conjunto de N valores numéricos almacenados en un arreglo unidimensional (vector ) A.
Dichovector estará en orden ascendente si
i 50).
Para aclarar ésto tenemos que hablar de la eficiencia de los métodos de ordenación. La mejor
manera de medir el rendimiento de un algoritmo de ordenaciónconsiste en contar el número de
comparaciones entre elementos utilizados para ordenar un vector de N elementos. Un algoritmo
de ordenación será más eficiente cuanto menor sea tal número decomparaciones. En el caso de
los algoritmos mencionados puede demostrarse que tal número de comparaciones es proporcional
a N 2 . Así, si se duplica el tamaño del vector, el número de comparaciones secuadriplica. Por otra
parte, los mejores algoritmos de ordenación tienen un número de comparaciones proporcional a
N log N . Claramente estos algoritmos son computacionalmente más eficientes que losalgoritmos
elementales presentados aquí 1 .

2.

Método de burbuja

El algoritmo de ordenación de burbuja (“bubble sort ”) se basa en comparar los elementos
adyacentes del vector e intercambiar losmismos si están desordenados. Se comienza comparando
el primer elemento con el segundo, si están desordenados se intercambian. Luego se compara el
segundo con el tercero, intercambiándolos si estándesordenados. Este proceso que se realiza sobre
todos los elementos constituye una pasada sobre el vector. Al terminar esta pasada el mayor
elemento se encuentra al final del vector y algunos de loselementos más pequeños se han movido
hacia las primeras posiciones (es decir, los elementos más pequeños han “burbujeado” hacia arriba,
mientras que los más grandes se han “hundido”, de aquí el...