La Ordenación de burbuja (Bubble Sort en inglés)
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.
El primer procedimiento del método de la burbuja es:
Generar un ciclo que inicie desde uno hasta el número de
elementos del arreglo.
Generar un segundo ciclo dentro del anterior que inicie
desde cero hasta el número de elementos del arreglo menos dos.
Dentro del segundo ciclo debe existir una comparación que
determina el tipo de ordenamiento (ascendente o descendente) entre el primer
elemento (posición generado por el segundo ciclo) y el segundo elemento (el que
le sigue), si la respuesta a la
condición es verdadera se realiza un intercambio entre los dos elementos.
Para realizar el intercambio se genera un almacenamiento
temporal, el cual guarda el dato del primer elemento, el segundo elemento toma
el lugar del primero y en el lugar del segundo se coloca lo que contiene el
almacenamiento temporal.
Un segundo procedimiento del método de la burbuja es:
Generar un ciclo que inicie desde cero hasta el número de
elementos menos dos.
Generar un segundo ciclo desde el valor del ciclo anterior
mas uno hasta el número de elementos menos uno;
Dentro del segundo ciclo debe existir una comparación que
determina el tipo de ordenamiento (ascendente o descendente) entre el primer
elemento (posición generada por el primer ciclo) y el segundo elemento
(posición generada por el segundo ciclo), si la respuesta a la condición es
verdadera se realiza un intercambio entre los dos elementos.
Para realizar el intercambio se genera un almacenamiento
temporal, el cual guarda el dato del primer elemento, el segundo elemento toma
el lugar del primero y en el lugar del segundo se coloca lo que contiene el
almacenamiento temporal.
Un tercer procedimiento del método de la burbuja es el
siguiente:
Generar un ciclo que inicie desde uno hasta el número de
elementos menos uno.
Generar un segundo ciclo que inicie desde el número de
elementos menos uno y mientras que ese valor sea mayor o igual al del ciclo
anterior (con decrementos).
Dentro del segundo ciclo debe existir una comparación que
determina el tipo de ordenamiento (ascendente o descendente) entre el primer
elemento (posición generada por el segundo ciclo) y el segundo elemento
(posición generada por el segundo ciclo menos uno), si la respuesta a la
condición es verdadera se realiza un intercambio entre los dos elementos.
Para realizar el intercambio se genera un almacenamiento
temporal, el cual guarda el dato del primer elemento, el segundo elemento toma
el lugar del primero y en el lugar del segundo se coloca lo que contiene el
almacenamiento temporal
Ordenamiento Shell
El método se denomina Shell en honor de su inventor Donald
Shell. Su implementación original, requiere O(n2) comparaciones e intercambios
en el peor caso. . Aunque es fácil desarrollar un sentido intuitivo de cómo
funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El algoritmo Shell sort mejora el ordenamiento por inserción
comparando elementos separados por un espacio de varias posiciones. Esto
permite que un elemento haga "pasos más grandes" hacia su posición
esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio
cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento
por inserción, pero para entonces, ya está garantizado que los datos del vector
están casi ordenados.
El procedimiento para
aplicar el algoritmo de shellsort es el siguiente:
Generar un ciclo que se encargue de controlar el tamaño que
deben tener los incrementos.
Este ciclo debe iniciar con la división del tamaño del
arreglo entre dos.
Mientras que el incremento sea mayor a cero debe continuar.
Y el cambio de incremento se elige de entre dos opciones: un
uno o la división del incremento anterior entre dos.
Un segundo ciclo dentro del anterior, controla el número de
comparaciones que se deben hacer según el tamaño del incremento.
El control de este ciclo debe iniciar con el incremento
generado anteriormente.
Mientras el control del ciclo sea menor que el tamaño del
arreglo.
El control debe cambiar de uno en uno.
Un tercer ciclo dentro del segundo controla en que momento
se detienen las comparaciones o se hacen los posibles intercambios entre los
elementos.
El control de este ciclo debe iniciar con el valor del ciclo
anterior.
Mientras que el control sea mayor o igual al incremento del
primer ciclo y el elemento del arreglo de la posición del control de este ciclo
menos el incremento, sea mayor que el elemento del arreglo de la posición
control de este ciclo, realice los intercambios entre estas posiciones.
Y el control se decremente con el valor del incremento.
Ordenamiento por
inserción
Es una manera muy natural de ordenar para un ser humano, y
puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma
arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un
conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor,
se toma el elemento k+1 y se compara con todos los elementos ya ordenados,
deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores
han sido desplazados una posición a la derecha) o cuando ya no se encuentran
elementos (todos los elementos fueron desplazados y este es el más pequeño). En
este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.
Ordenamiento por selección
Es un algoritmo de ordenamiento que requiere
O(n²) operaciones
para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:
Buscar el mínimo elemento de la lista
Intercambiarlo con el primero
Buscar el mínimo en el resto de la lista
Intercambiarlo con el segundo
Y en general:
Buscar el mínimo elemento entre una 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
