Metodos de oredenacion

Metodos de ordenación

Nombre del alumno:
Daniel Alberto frias Lerma
Materia:
Programación orientada a objetos
Registro:
10310131

Ordenamiento de burbuja

El Ordenamiento 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 ordenequivocado. 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 paraoperar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar. Este algoritmo realiza el ordenamiento de una lista a de n valores, en este caso de n términos numerados del 0 al n-1, consta de dos bucles anidados uno con el índice i, que da un tamaño menor al recorrido de la burbuja en sentido inverso de 2 a n, y un segundo loop con el índice j, con un recorridodesde 0 hasta n-i, para cada iteración del primer bucle, que indica el lugar de la burbuja.
La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan, si el primero es menor que el segundo sus valores se intercambian.
Esta comparación se repite en el centro de los dos bucles, dando lugar a la postre a una lista ordenada, puede verse que el número de repeticiones sola depende den, y no del orden de los términos, esto es si pasamos al algoritmo una lista ya ordenada, realizara todas las comparaciones exactamente igual que para una lista no ordenada, esta es una característica de este algoritmo, luego verano una variante que evita este inconveniente.
Para comprender el funcionamiento, veamos un ejemplo sencillo:
Tenemos una lista de números que hay que ordenar:

|Podemos ver que la lista que tiene cinco términos, luego:

El índice i hará un recorrido de 2 hasta n:

Que en este caso será de 2 a 5. Para cada uno de los valores de i, j tomara sucesivamente los valores de 0 hasta n-i:

Para cada valor de j, obtenido en ese orden, se compara el valor del índice j con el siguiente:

Si el termino j es menor, en su caso podría se mayor, que el termino j+1,los valores se permutan, en caso contrario se continúa con la iteración.
|
Para el caso del ejemplo, tenemos que:

Para la primera iteración del primer bucle:

y j tomara los valores de 0 hasta 3:

Cuando j vale 0, se comparan , el 55 y el 86, dado que 55 < 86 no se permutan el orden.
Ahora j vale 1 y se comparan  el 86 y el 48 Como 86 > 48, se permutan, dando lugar a una nuevalista.
Se repite el proceso hasta que j valga 3, dando lugar a una re lista super ordenada, podemos ver que el termino de mayor valor esta en el lugar más alto.
|
Ahora i vale 3, y j hará un recorrido de 0 a 2.
Primero j vale 0, se comparan , el 55 y el 48, como 55 > 48 se permutan dando lugar a la nueva lista.
Para j = 1 se compara el 55 con el 16 y se cambian de orden.
Para j = 2 secompara el 55 y el 82 y se dejan como están, finalizando el bucle con una lista mejor ordenada, puede verse que los dos valores más altos ya ocupan su lugar. No se ha realizado ninguna comparación con el termino cuarto, dado que ya se sabe que después del primer ciclo es el mayor de la lista.
Método Quicksort
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica dedivide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n
El algoritmo consta de los siguientes pasos:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al...