Algoritmo Burbuja Y Quicksort
Páginas: 7 (1543 palabras)
Publicado: 21 de septiembre de 2012
Métodos de Ordenamiento Algoritmo Burbuja Algoritmo Quicksort
Algoritmo de ordenamiento que compara cada elemento de una lista (vector o matriz) con el siguiente, intercambiándolos de posición si están en el orden equivocado. Si se desea ordenar de menor a mayor, los elementos se intercambian si es que el primero es mayor al segundo, en caso de querer ordenar de mayor a menor, se realiza elproceso inverso. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios; lo que indica que la lista está ordenada.
Ventajas Fácil Implementación Requerimientos mínimos de memoria
Desventajas Lento Realiza numerosas comparaciones
1. Para efectos prácticos, asumimos que el vector está lleno y que queremos ordenarlo de menor a mayor. Tenemos: 9 4 6 0 1 310 7 2
2. La idea es ir comparando la primera casilla con la segunda, cambiándolos de orden si el primer número es mayor al segundo (si no es así, se mantienen en el orden actual). Luego comparamos la segunda casilla con la tercera, luego la tercera con la cuarta y así sucesivamente hasta llegar a la última. Tras realizar este proceso, sabemos que en la última casilla ha quedado el número mayorque se encuentra en el vector.
9
4
¿9>4?
6
0
1
3
10
7
2
(hay intercambio)
4
9
6
¿9>6?
0
1
3
10
7
2
(hay intercambio)
4
6
9
0
¿9>0?
1
3
10
7
2
(hay intercambio)
4
6
0
9
1
¿9>1?
3
10
7
2
(hay intercambio)
4
6
0
1
9
3
¿9>3?
10
7
2
(hayintercambio)
4
6
0
1
3
9
10
¿9>10?
7
2
(no hay intercambio)
4
6
0
1
3
9
10
7
2
(hay intercambio)
¿10>7?
4
6
0
1
3
9
7
10
2
(hay intercambio)
¿10>2?
4
6
0
1
3
9
7
2
10
Número mayor del vector
3. Tras ordenar los números, es necesario repetir el proceso. Comenzamos comparandodesde la primera casilla, pero ésta vez llegaremos hasta la casilla anterior a la última, pues en ella, se encuentra el número mayor del vector. En pocas palabras, por cada vez que recorro el vector, disminuye en 1 el límite superior de comparación.
4
6
¿4>6?
0
1
3
9
7
2
10
(hay intercambio)
4
6
0
¿6>0?
1
3
9
7
2
10
(hay intercambio)
40
6
1
¿6>1?
3
9
7
2
10
(hay intercambio)
4
0
1
6
3
¿6>3?
9
7
2
10
(hay intercambio)
4
0
1
3
6
9
¿6>9?
7
2
10
(no hay intercambio)
4
0
1
3
6
9
7
¿9>7?
2
10
(hay intercambio)
4
0
1
3
6
7
9
2
¿9>2?
10
(hay intercambio)
4
0
1
3
6
72
9
10
La comparación llega hasta acá porque en la última casilla ya se encuentra el número mayor del vector
4. Con la misma mecánica, se realiza este proceso cuantas veces sea necesario para tener completamente ordenado el vector.
Para realizar este proceso, es necesario tener dos variables. “i”: Comienza en 0 y llega hasta el límite superior de comparación (“j”) “j”: Comienza enel límite superior y disminuye en 1 por cada vez que se recorra el vector. El límite superior se calcula dependiendo de la cantidad de casillas que posea el vector. Por ejemplo, si el vector posee 9 casillas, el límite superior será 8. Se terminará de comparar en el momento en el cual la variable que al comienzo contenía el límite superior (“j”), llegue a 1. En ese caso, se llegará a la casillanúmero 2, ya que en la primera, se encuentra el número menor.
El código para este proceso sería:
(El vector “p” en este caso se trabaja como puntero pues el programa fue implementado con memoria dinámica. Ver archivo .c del algoritmo burbuja)
Algoritmo que se basa en la famosa técnica “divide y vencerás”, donde, el vector o matriz se va dividiendo en sub-vectores (o submatrices) para...
Algoritmo de ordenamiento que compara cada elemento de una lista (vector o matriz) con el siguiente, intercambiándolos de posición si están en el orden equivocado. Si se desea ordenar de menor a mayor, los elementos se intercambian si es que el primero es mayor al segundo, en caso de querer ordenar de mayor a menor, se realiza elproceso inverso. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios; lo que indica que la lista está ordenada.
Ventajas Fácil Implementación Requerimientos mínimos de memoria
Desventajas Lento Realiza numerosas comparaciones
1. Para efectos prácticos, asumimos que el vector está lleno y que queremos ordenarlo de menor a mayor. Tenemos: 9 4 6 0 1 310 7 2
2. La idea es ir comparando la primera casilla con la segunda, cambiándolos de orden si el primer número es mayor al segundo (si no es así, se mantienen en el orden actual). Luego comparamos la segunda casilla con la tercera, luego la tercera con la cuarta y así sucesivamente hasta llegar a la última. Tras realizar este proceso, sabemos que en la última casilla ha quedado el número mayorque se encuentra en el vector.
9
4
¿9>4?
6
0
1
3
10
7
2
(hay intercambio)
4
9
6
¿9>6?
0
1
3
10
7
2
(hay intercambio)
4
6
9
0
¿9>0?
1
3
10
7
2
(hay intercambio)
4
6
0
9
1
¿9>1?
3
10
7
2
(hay intercambio)
4
6
0
1
9
3
¿9>3?
10
7
2
(hayintercambio)
4
6
0
1
3
9
10
¿9>10?
7
2
(no hay intercambio)
4
6
0
1
3
9
10
7
2
(hay intercambio)
¿10>7?
4
6
0
1
3
9
7
10
2
(hay intercambio)
¿10>2?
4
6
0
1
3
9
7
2
10
Número mayor del vector
3. Tras ordenar los números, es necesario repetir el proceso. Comenzamos comparandodesde la primera casilla, pero ésta vez llegaremos hasta la casilla anterior a la última, pues en ella, se encuentra el número mayor del vector. En pocas palabras, por cada vez que recorro el vector, disminuye en 1 el límite superior de comparación.
4
6
¿4>6?
0
1
3
9
7
2
10
(hay intercambio)
4
6
0
¿6>0?
1
3
9
7
2
10
(hay intercambio)
40
6
1
¿6>1?
3
9
7
2
10
(hay intercambio)
4
0
1
6
3
¿6>3?
9
7
2
10
(hay intercambio)
4
0
1
3
6
9
¿6>9?
7
2
10
(no hay intercambio)
4
0
1
3
6
9
7
¿9>7?
2
10
(hay intercambio)
4
0
1
3
6
7
9
2
¿9>2?
10
(hay intercambio)
4
0
1
3
6
72
9
10
La comparación llega hasta acá porque en la última casilla ya se encuentra el número mayor del vector
4. Con la misma mecánica, se realiza este proceso cuantas veces sea necesario para tener completamente ordenado el vector.
Para realizar este proceso, es necesario tener dos variables. “i”: Comienza en 0 y llega hasta el límite superior de comparación (“j”) “j”: Comienza enel límite superior y disminuye en 1 por cada vez que se recorra el vector. El límite superior se calcula dependiendo de la cantidad de casillas que posea el vector. Por ejemplo, si el vector posee 9 casillas, el límite superior será 8. Se terminará de comparar en el momento en el cual la variable que al comienzo contenía el límite superior (“j”), llegue a 1. En ese caso, se llegará a la casillanúmero 2, ya que en la primera, se encuentra el número menor.
El código para este proceso sería:
(El vector “p” en este caso se trabaja como puntero pues el programa fue implementado con memoria dinámica. Ver archivo .c del algoritmo burbuja)
Algoritmo que se basa en la famosa técnica “divide y vencerás”, donde, el vector o matriz se va dividiendo en sub-vectores (o submatrices) para...
Leer documento completo
Regístrate para leer el documento completo.