Algoritmos De Ordenamiento

Algoritmos de Ordenamiento Lineal

Por ordenar se entiende el proceso de reorganizar un conjunto de objetos en una cierta secuencia de acuerdo a un criterio especificado. En general, el objetivo de este proceso es facilitar la posterior búsqueda de elementos en el conjunto ordenado.

Existen múltiples ejemplos reales de conjuntos que requieren ser ordenados: la guía telefónica, índices de libros, ficheros de bibliotecas, diccionarios, ficheros de diverso tipo en oficinas, actas de exámenes, etc.

A continuación se describen algunos de los algoritmos de ordenación lineal más conocidos.

3.1.1 BubleSort

La idea de este método es ir tomando los elementos de a dos e ir comparándolos e intercambiándolos de ser necesario, hasta que todos los elementos sean comparados.

for (i=0; i<n-1; i++)

{

for (j=i+1; j<n; j++)

{

if(V[i]>V[j])

{

aux = V[i];

V[i] = V[j];

V[j] = aux;

}

}

}

El bucle externo establece un desplazamiento secuencial dentrodel vector desde el primer elemento hasta el penúltimo , el bucle interno realiza un recorrido del vector desde el elemento i+1 hasta el último elemento del vector y va reduciendo en cada iteración del bucle externo el número de elementos a comparar, ya que los elementos anteriores ya debieron ordenarse en las iteraciones anteriores. Ahora bien, lo que se quiere es ordenar todos los valores, para lo cual se compara el elemento i con los subsiguientes elementos del vector e intercambiándolo cuando sea mayor que alguno de los elementos ubicado en alguna posición inferior del vector, en este intrecambio es que se genera la burbuja, donde los elementos más pequeños van subiendo y los más grandes se van ubicando en las posiciones inferiores del vector.

Ejemplo 3.1. Supongamos que un vector de 10 elementos tiene estos valores:

9 7 6 5 4 3 11 8 10 2

A continuación se describe paso por paso la evolución del método. Representando cada estado del vector de la siguiente manera:

i,j->V[0]V[1]V[2]V[3]V[4]V[5]V[6]V[7]V[8]V[9]

0,1->7 9 6 5 4 3 11 8 10 2

0,2->6 9 7 5 4 3 11 8 10 2

0,3->5 9 7 6 4 3 11 8 10 2

0,4->4 9 7 6 5 3 11 8 10 2

0,5->3 9 7 6 5 4 11 8 10 2

0,6->3 9 7 6 5 4 11 8 10 2

0,7->3 9 7 6 5 4 11 8 10 2

0,8->3 9 7 6 5 4 11 8 10 2

0,9->2 9 7 6 5 4 11 8 10 3

1,2->2 7 9 6 5 4 11 8 10 3

1,3->2 6 9 7 5 4 11 8 10 3

1,4->2 5 9 7 6 4 11 8 10 3

1,5->2 4 9 7 6 5 11 8 10 3

1,6->2 4 9 7 6 5 11 8 10 3

1,7->2 4 9 7 6 5 11 8 10 3

1,8->2 4 9 7 6 5 11 8 10 3

1,9->2

...