Nestes exercicios imos repasar algúns dos algoritmos para ordenar dos que xa falamos na páxina de Algoritmos de Ordenación, no apartado de Antes de Scratch, basada na magnífica páxina Algorithmique / Programmation de Pascal LOEWENGUTH con licenza cc-by. Neste apartado vermos:
1. Ordenación por inserción
- 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.
- Percorremos os valores da lista usando o índice. Comenzamos polo elemento 1 e o comparamos co 2.
- 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.
Solución proposta (lembra, non é única):
| Pseudocódigo | Python3 |
|
|
|
Unha vez creada a función facemos o programa chamando á función, dándolle datos de entrada (parámetros) e pedindo que os mostre na saída:
Imos introducir dúas listas: unha de números Vector1 = [3,2,1] e outra de palabras Vector2 = ['Víbora','Cobra','Pitón'].
[Repl.it: Ordenar por inserción]
Exercicios:
- Dada unhan lista de 5 elementos, calcula o número de pasos que tes que dar para ordenala supoñendo que está no peor caso. Exemplo: a lista é [8,6,4,2,1].
- Modifica o programa para que ordene en sentido inverso, de maior a menor.
- Modifica o programa para que ordene datos que lle vas dando desordenados por teclado (con input). Terás que almacenalos nunha lista.
2. Ordenación burbulla
- 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 ata que estén ordenados
- 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.
Solución proposta (lembra, non é única):
Aquí imos ver directamente o código en Python:
| Código en Python | Comentarios |
|---|---|
 |
Orde para intercambiar dous elementos adxacentes: vector[actual], vector[actual + 1] =vector[actual + 1],vector[actual] Variable iteracion Emprégase para percorrer o vector varias veces. Esta variable vai contando o número de veces que iteramos. Despois da 1ª iteración, sabemos seguro que o último elemento xa é o maior, polo que na 2ª iteración só percorremos o vector ata o penúltimo item. Despois da 2ª iteración só percorremos a lista ata o antepenúltimo, etc... Bucle while So vai pararse cando poñamos o valor da variable lóxica permutation a false. O valor cambiámolo a False ao principio do bucle e sempre que haxa que facer algún novo cambio pasará a True. Cando esté todo ordenado xa non volverá cambiar a True e o bucle remata. |
Exercicios:
- Dado o vector [4,3,5,7] debuxa as iteracións que faría o algoritmo burbulla ata ordenalo.
- O programa so amosa a función. Engade o código para que ordene a lista do exercicio anterior.
- Engade como dato de entrada un vector con nomes e aplícalle a función para ordenalo.
Binarizar e outras conversións Ordena e funcionará Máis orde Que ordene Python