Algoritmo de ordenacion
Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande en la última posición, una vez acomodado el más grande, prosigue a encontrar y acomodar el siguiente más grande comparando de nuevo los numeros desde el inicio del vector, y así siguehasta ordenar todo los elementos el arreglo. Este algoritmo es muy deficiente ya que al ir comparando las casillas para buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación.
Entonces:
Dado un vector a1, a2, a3, ... an
1) Comparar a1 con a2 eintercambiarlos si a1>a2 (o a1 vec[j+1]){ T(1)
aux=vec[j]; T(1)
vec[j]=vec[j+1]; T(1)
vec[j+1]=aux;} T(1)
}
}
El procedimiento de la burbuja es el siguiente:
▪ Ircomparando desde la casilla 0 numero 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 halla ordenado todas las casillas del vector.
▪ Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelvea compararlo cuando esto ya no es necesario.
Ejemplo:
|Variables |Vector |
|pos |0 |1 |2 |3 |4 |5 |6 |7 | |i |j |a[j] |a[j+1] |inicio |44 |55 |12 |42 |94 |18 |6 |67 | |0 |1 |55 |12 |cambio |44 |12 |55 |42 |94 |18 |6 |67 | |0 |2 |55 |42 |cambio |44 |12 |42 |55 |94 |18 |6 |67 | |0|4 |94 |18 |cambio |44 |12 |42 |55 |18 |94 |6 |67 | |0 |5 |94 |6 |cambio |44 |12 |42 |55 |18 |6 |94 |67 | |0 |6 |94 |67 |cambio |44 |12 |42 |55 |18 |6 |67 |94 | |1 |0 |44 |12 |cambio |12 |44 |42 |55 |18 |6 |67 |94 | |1 |1 |44 |42 |cambio |12 |42 |44 |55 |18 |6 |67 |94 | |1 |3 |55 |18 |cambio |2 |42 |44 |18 |55 |6 |67 |94 | |1 |4 |55 |6 |cambio |12 |42 |44 |18 |6 |55 |67 |94 | |2 |2 |44 |18 |cambio|12 |42 |18 |44 |6 |55 |67 |94 | |2 |3 |44 |6 |cambio |12 |42 |18 |6 |44 |55 |67 |94 | |3 |1 |42 |18 |cambio |12 |18 |42 |6 |44 |55 |67 |94 | |3 |2 |42 |6 |cambio |12 |18 |6 |42 |44 |55 |67 |94 | |4 |1 |18 |6 |cambio |12 |6 |18 |42 |44 |55 |67 |94 | |5 |0 |12 |6 |ordenado |6 |12 |18 |42 |44 |55 |67 |94 | |Ventajas:
• Fácil implementación.
• No requiere memoria adicional.
Desventajas:• Muy lento.
• Realiza numerosas comparaciones.
• Realiza numerosos intercambios.
ORDENACIÓN POR EL MÉTODO SHELL
El método de shell es una versión mejorada del método de inserción directa recibe ese nombre en honor a su autor Donald L. Shell quien lo propuso en 1959.
Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método deordenación Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.
Ejemplo:
Se desean ordenar las siguientes claves del arreglo
A: 15, 67, 08, 16, 44, 27, 12, 35, 56, 21, 13, 28, 60, 36, 07, 10
Primera Pasada
Loselementos se dividen en 8 grupos:
A: 15, 67, 08, 16, 44, 27, 12, 35 | 56, 21, 13, 28, 60, 36, 07, 10
La ordenación produce:
A: 15, 21, 08, 16, 44, 27, 07, 10, 56, 67, 13, 28, 60, 36, 12, 35
Segunda Pasada
Se dividen los elementos en 4 grupos:
A: 15, 21, 08, 16 | 44, 27, 07, 10 | 56, 67, 13, 28 | 60, 36,12, 35
La ordenación produce:
A: 15, 21, 07, 10, 44, 27, 08, 16, 56,...
Regístrate para leer el documento completo.