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!

view sourceprint?

01.def bubblesort_2(seq):

02. """Ordenamento por bolhas.

03. Pára mal fica ordenado = não há mais trocas!

04. """

05. copia = seq[:]

06. cont= len(seq)-1

07. troca = True

08. while troca:

09.  cont = cont -1

10.  troca=False

11.  for i in range(cont+1):

12.   if copia[i] > copia[i+1]:

13.    copia[i],copia[i+1] = copia[i+1],copia[i]

14.    troca=True

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