Máis orde

Antes en Python :

  • Funcións
  • Algoritmos de ordenamento

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:

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

 

algoritmo

 

 

 

Exercicio:

  1. 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].
  2. Comenta o código do algoritmo indicando que fan as variables comienzo e fin.

 

Comezo

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:

 

  1. 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.

 

Comezo

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]

Comezo

 

Binarizar e outras conversións Ordena e funcionará Máis orde Que ordene Python