Ordena e funcionará

Antes en Python :

  • Funcións
  • Listas (datos estruturados)

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

 

Problema
Ordena unha lista polo método de inserción: inserimos valores despois de comparalos, sabendo se son menores que os anteriores. Se a lista é [A,B,C,D], comparamos A con B. Se B é menor inserimos B antes de A. Se non, comparamos C con B e logo con A e o inserimos se é menor que algún deles. Para inserir temos que facer un oco na lista.

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.
  • Percorremos os valores da lista usando o índice. Comenzamos polo elemento 1 e o comparamos co 2.
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.

Solución proposta (lembra, non é única):

Pseudocódigo Python3

 

algoritmo

 

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:

  1. 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].
  2. Modifica o programa para que ordene en sentido inverso, de maior a menor.
  3. Modifica o programa para que ordene datos que lle vas dando desordenados por teclado (con input). Terás que almacenalos nunha lista.

Comezo

2. Ordenación burbulla

Problema
É unha variante do anterior. Recorremos a lista varias veces comparando cada elemento co seu adxacente e ordenándoos se está desordenados, Se temos unha lista = [A,B,C,D] compararíamos A con B ordenando, logo o que quede en 2º lugar co 3º e ordenando, e por último o 3º co 4º. Logo volvemos a empezar.

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 ata que estén ordenados
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.

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:

 

  1. Dado o vector [4,3,5,7] debuxa as iteracións que faría o algoritmo burbulla ata ordenalo.
  2. O programa so amosa a función. Engade o código para que ordene a lista do exercicio anterior.
  3. Engade como dato de entrada un vector con nomes e aplícalle a función para ordenalo.

Comezo

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