PRACTICA #1: Algoritmos de ordenamiento secuencial

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice ordenar. En este caso nos servira para ordenar vectores o matrices con valores asignados. Los siguientes algoritmos ilustran un esquema de implementación del algoritmo de ordenamiento secuencial.

1) Algoritmo de ordenamiento por selección (Selectio Sort)

Consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenarlo todo. Su implementación requiere N^2 comparaciones e intercambios para ordenar una secuencia de elementos.

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación de intercambiar los elementos sería más costosa en este caso. Su funcionamiento se puede definir de forma general como:

• Busca el mínimo elemento entre la posición i y el final de la lista

• Intercambiar el mínimo con el elemento de la posición i

De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1

Implementación

A continuación se muestra el Ordenamiento por Selección en Python

Ordenamiento por Selección en Python

Resultado de Ordenar la Cadena

Video: Ordenamento por Selección

REFERENCIAS: http://www.ecured.cu/index.php/Algoritmo_de_ordenamiento_por_selecci%C3%B3n#Ejemplo

2) Ordenamiento por Burbuja (Bubble Sort)

Es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas burbujas. También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

El procedimiento de la burbuja es el siguiente:

• Ir comparando desde la casilla 0 número tras número hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevará hasta la última casilla, si no es así, será reemplazado por uno mayor que él.

• Este procedimiento seguirá así hasta que haya ordenado todas las casillas del vector.

• Una de las deficiencias del algoritmo es que ya cuando ha ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

Implementación

A continuación se muestra el Ordenamiento por Burbuja en Python

Ordenamiento por Burbuja en Python

Resultado de Ordenar la Cadena

VIDEO: Ordenamiento por Burbuja en Python

REFERENCIA: http://www.ecured.cu/index.php/Ordenamiento_de_burbuja

3) Ordenamiento por inserción (Insertion Sort)

Supóngase que se desea ordenar los siguientes claves del arreglo (A) utilizando el método de inserción directa el cual consiste en insertar un elemento del arreglo en la parte izquierda del mismo que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento.

El algoritmo ordena los elementos del arreglo utlizando el método de inserción directa A es un arreglo de N elementos donde I, aux y k son variables de tipo entero.

1.- Repetir con I desde 2 hasta N Hacer aux<- A[I] y k<- I-1

a. Repetir mientras(aux < [k]) y (k > 1) , Hacer A[k+1]<- A[k] y k<-- k-1

b. {fin del ciclo del paso 1.1}

c. Si a[k]<=aux Entonces: Hacer A[k+1]<-aux

Si no Hacer A[k+1]<- A[k], A[k]<-A[k]

d. { fin del condicional del paso 1.3}

2. {fin del condicional del paso1

Ordenamiento por inserción

Implementación

A continuación se muestra el Ordenamiento por Inserción en Python

Ordenamiento por Inserción en Python

Resultado de Ordenar la Cadena

VIDEO: Ordenamiento por Burbuja en Python

REFERENCIAS: http://www.ecured.cu/index.php/Ordenamiento_por_Inserci%C3%B3n

4) Ordenamiento por mezcla (Merge Sort)

El algoritmo de ordenamiento por mezcla es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás.

Fue desarrollado en 1945 por John Von Neumann.

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

• Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:

• Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.

• Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.

• Mezclar las dos sublistas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

• Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.

• Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

Implementación

A continuación se muestra el Ordenamiento por Mezcla en Python

Ordenamiento por mezcla

Resultado de Ordenar la Cadena

VIDEO: Ordenamiento por mezcla

REFERENCIA: http://www.c.conclase.net/orden/?cap=mergesort

5) Ordenamiento Rápido (Quick Sort)

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana. Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.

La idea central de este algoritmo consiste en el siguiente:

• Se toma un elemento x de una posición cualquiera del arreglo.

• Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.

• Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo

Ordenamiento Quick Sort

Implementación

A continuación se muestra el Ordenamiento Rápido en Python

Ordenamiento Rapido en Python

Resultado de Ordenar la Cadena

VIDEO: Ordenamiento Rapido

REFERENCIA: http://www.angelfire.com/wy2/est_info/quicksort.html