Continuamos repasando algoritmos de ordenar, que xa temos comentado no apartado de Antes de scratch, pero agora vendo o código en Python. Faremos referencia e copiaremos cousas da magnífica páxina Algorithmique / Programmation de Pascal LOEWENGUTH con licenza cc-by. Neste apartado veremos:
- Ordenacion batedora, tamén chamada burbulla bidireccional
- Ordenación gnomo, basada na forma de ordenar gnomos plantas no xardín.
- Ordenación rápida: tamén chamada quicksort
Ordenación batedora
Problema
Ordena unha lista polo método da batedora, tamén chamado burbulla bidirecional, pois aplica o método burbulla para adiante e a para atrás, para que se ordenen igual de rápidos os números grandes e os pequenos.
Análise
- Dada unha lista, cos elementos a ordenar, cada elemento ten un valor e un índice, posición.
- Collemos dous elementos, un á esquerda e outro á dereita e os comparamos. O de estar á esquerda o sabemos polo índice.
- Se o menor está na dereita, creamos un oco na esquerda e inserimos ese elemento.
- Collemos o elemento que quedou á dereita e o ordenamos co inmediatamente superior.
- Cando rematamos de comparar os adxacentes repetimos toda a iteración pero empezando pola parte superior da lista.
Algoritmo
- Lista para gardar datos.
- Bucle for i....in range....para recorrer a lista.
- Unha variable para almacenar o dato a mover e outra variable para almacenar a posición do dato a comparar.
- Unha variable dirección para poder percorrer o vector de adiante a atrás. que vai cambiando de valor en cada iteración.
Solución proposta (lembra, non é única):
| Pseudocódigo | Python3 |
|---|---|
|
|
|
Exercicio:
- Dada unhan lista de 5 elementos, calcula o número de pasos que tes que dar para ordenala polo método batedora. Exemplo: a lista é [8,6,4,2,1].
- Comenta o código do algoritmo indicando que fan as variables comienzo e fin.
Ordenación gnomo
Problema
Ordena unha lista polo método gnome. É similar ao de inserción, pero agora comparamos cada elemento co do lado. Se temos unha lista [A,B,C,D] comparamos A con B e ordenamos. Logo B ou A (o quede na dereita) con C e ordenamos. Unha vez feito isto voltamos a comparar o de 2º lugar do 1º. O algoritmo é moito máis sinxelo.
Análise
- Dada unha lista, cos elementos a ordenar, cada elemento ten un valor e un índice, posición.
- Collemos dous elementos, un á esquerda e outro á dereita e os comparamos. O de estar á esquerda o sabemos polo índice.
- Se o menor está na dereita, creamos un oco na esquerda e inserimos ese elemento.
- Collemos o elemento que quedou á dereita e o ordenamos co inmediatamente superior.
- Cando rematamos de comparar os adxacentes repetimos toda a iteración pero empezando pola parte superior da lista.
Algoritmo
- Lista para gardar datos.
- Bucle for i....in range....para recorrer a lista.
- Dúas variables para intercambiar dous valores (onde pon intercambiar no pseudocódigo, ti tes que facelo gardando os valores en dúas variables e intercambiando despois).
Solución proposta (agora so damos o pseudocódigo):
| Pseudocódigo en pSeint |
|
PROCEDIMIENTO Gnome_sort(vector[]) pos := 1 MIENTRAS pos < longitud(vector) SI (vector[pos] >= vector[pos-1]) pos := pos + 1 SI NO intercambiar vector[pos] Y vector[pos-1] SI (pos > 1) pos := pos - 1 FIN SI FIN SI FIN MIENTRAS FIN PROCEDIMIENTO |
Exercicio:
- Dado o pseudocódigo intenta escribir en Python o algoritmo do método gnomo para ordenar. Lembra que precisas dúas variables para facer o que en pseudocódigo chama intercambiar.
Ordenación rápida: quicksort
Problema
Ordena unha lista polo método da ordenación rápida, tamén chamado quicksort, que emprega a estratexia recursiva: dividir a lista en dúas partes, escoller un número máximo e ordenar volvendo dividir á metade e así recursivamente.
Análise
- Escollo un número da lista ao chou que será o pivote.
- Recoloco todos os demais elementos da lista a un lado ou a outro segundo sexan menores ou maiores co pivote.
- Agora o elemento pivote está xa colocado na súa posición definitiva e teño a lista separada en dúas sublistas.
- En cada sublista aplicarei outra vez a ordenación rápida ata dividila en outras dúas sublistas.
- E así sucesivamente ata rematar de dividir.
Algoritmo
- O código deste algoritmo é máis dificil de entender pero revela todo o poder de Python, pois é máis compacto. Utiliza a recursividade para chamar a función en bucle. Cando estudes a recursividade volta por aquí.
- Lista para gardar datos.
- Bucle for i....in range....para recorrer a lista.
- Tres variables, unha para o maior, outro para o menor e outra pivote.
Solución proposta (lembra, non é única):
[Repl.it: quicksort]
Binarizar e outras conversións Ordena e funcionará Máis orde Que ordene Python