Problema 10.4

Vamos melhorar o algoritmo de ordenamento por bolhas (bubble sort) evitandio que ele continue a efectuar comparações quando o vector já está ordenado. Como sabemos que o vector está ordenado? Simples: quando percorremos o vector sem haver trocas entre elementos!

def bubblesort_2(seq):
 """Ordenamento por bolhas.
 Pára mal fica ordenado = não há mais trocas!
 """
 copia = seq[:]
 cont= len(seq)-1
 troca = True
 while troca:
  cont = cont -1
  troca=False
  for i in range(cont+1):
   if copia[i] > copia[i+1]:
    copia[i],copia[i+1] = copia[i+1],copia[i]
    troca=True
 return copia

Então o que fizemos? Passamos a ter um ciclo condicional (while) controlado por uma variávewl booleana, que indica se houve ou não trocas na etapa anterior. Como temos que percorrer pelo menos uma vez o vector, inicializamos a variável booleana de controlo a True. No interior do ciclo começamos por assumir que não houve trocas. Percorremos o vector. Caso não haja nenhuma troca, ele mantém-se com o valor False e saímos do ciclo. Caso contrário, passa a verdadeira e retomamos o ciclo no seu início.