TODOS LOS METODOS DE ORDENAMIENTO
Enviado por monto2435 • 5 de Diciembre de 2018 • 3.672 Palabras (15 Páginas) • 272 Visitas
...
En el caso de la operación de ordenamiento, los criterios que generalmente se siguen para determinar su eficiencia son:
- tiempo menor de ejecución en computadora;
- menor número de instrucciones
Sin embargo, generalmente el mejor criterio para medir la eficiencia de un método de ordenamiento será la medida del número de comparaciones entre los elementos afectados. El algoritmo de ordenación A será más eficiente que el B, si requiere menor número de comparaciones.
- Método de la Burbuja
El método de intercambio directo o mejor conocido como burbuja, es el más usado entre los principiantes por su fácil comprensión y programación; pero probablemente es el más ineficiente.
El método de la burbuja consiste en comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces se intercambian de posición. Puede funcionar llevando los elementos más pequeños a la izquierda o los más grandes a la derecha.
Procedimiento Burbuja(E/S TaDatos aDatos)
Var
eCont1, eCont2, eAux : entero
Inicio
Desde eCont1 = 1 Hasta Longitud(aDatos) hacer
Desde eCont2 = eCont1 + 1 Hasta Longitud(aDatos) hacer
Si (aDatos[eCont1] > aDatos[eCont2]) entonces
Hacer eAux = aDatos[eCont1]
Hacer aDatos[eCont1] = aDatos[eCont2]
Hacer aDatos[eCont2] = eAux
Fin Si
Fin Desde
Fin Desde
Fin //Burbuja
Si se toma en cuenta que tras una pasada puede suceder que ya estén todos los elementos ordenados, no sería necesario seguir realizando comparaciones, por eso este método puede mejorarse usando una bandera que indique si se ha hecho algún intercambio en la última pasada, de lo contrario, ya están ordenados y se termina el proceso.
Procedimiento BurbujaMejorado(E/S aDatos : TaDatos)
Var
eCont1, eCont2, eAux : entero
lIntercambio : lógico
Inicio
Hacer eCont1 = 1
Hacer lIntercambio = Verdadero
Mientras (lIntercambio y eCont
Hacer lIntercambio = FALSO
Desde eCont2 = eCont1 + 1 Hasta Longitud(aDatos) hacer
Si (aDatos[eCont1] > aDatos[eCont2]) entonces
Hacer eAux = aDatos[eCont1]
Hacer aDatos[eCont1] = aDatos[eCont2]
Hacer aDatos[eCont2] = eAux
Hacer lIntercambio = VERDADERO
Fin Si
Fin Si
Fin Desde
Fin //Burbuja
El tiempo de ejecución de la burbuja se determina por el número de comparaciones, en el peor de los casos O(n2). La complejidad para el caso peor es 0(n2) comparaciones y 0(n2) intercambios. En el mejor de los casos, la ordenación por burbuja puede terminar en menos de n − 1 pasadas pero requiere, normalmente, muchos más intercambios que la ordenación por selección y su prestación media es mucho más lenta, sobre todo cuando los arreglos a ordenar son grandes.
Ventaja: Su principal ventaja es la simplicidad del algoritmo.
Desventaja: Solo compara los elementos adyacentes del arreglo. Si el algoritmo comparara primero elementos separados por un amplio intervalo y después se centrara progresivamente en intervalos más pequeños, el proceso sería más eficaz. Esto llevó al desarrollo de ordenación Shell y QuickSort.
- Método por Sacudida (Shaker Sort)
Más conocido como sacudida es una optimización del método de la burbuja. La idea básica de este algoritmo consiste en mezclar las dos formas en que se puede realizar el método de la burbuja.
En este algoritmo cada pasada tiene dos etapas:
- En la primera etapa "de derecha a izquierda", se trasladan los elementos más pequeños hacia la parte izquierda del arreglo, almacenando en una variable la posición del último elemento intercambiado.
- En la segunda etapa, "de izquierda a derecha", se trasladan los elementos más grandes hacia la derecha y se almacena en otra variable la posición del último elemento intercambiado.
- Las pasadas sucesivas trabajan con los componentes del arreglo comprendidos entre las posiciones almacenadas en las variables auxiliares. El algoritmo termina cuando en una etapa no se producen intercambios o cuando el contenido de la variable que almacena en el extremo izquierdo es mayor que el contenido de la variable que almacena el extremo derecho.
15
67
08
16
44
27[pic 1]
12[pic 2]
35
[pic 3][pic 4][pic 5]
[pic 6][pic 7]
[pic 8]
Primera Pasada
Después de primer etapa
08
15
67
12
16
44
27
...