Aula 13

Aula 13

                  ---------------------------------
                  Ordenação / importância / métodos
                  ---------------------------------


Nota. Ver mais informação sobre ordenação nos "slides" das aulas teóricas.


Muitos métodos (... Knuth, The Art of Computer Progr. VOL III)



                          -----------------
                          ORDENAR VECTORES?
                          -----------------

- muitos métodos

                          ------------------
                          Seleccão do mínimo
                          ------------------

     IDEIA
     PROGRAMA

 - Completar programa da contagem de letras...
 - Testar com diversos programas... comprimidos


                   -------------------------------
                   método da bolha ("bubble sort")
                   -------------------------------


Trocando adjacentes v[i] <-> v[i+1],  se v[i] > v[i+1]


Uma passagem pelo vactor torna-o mais ordenado.

Tantas passagens até não haver troca nenhuma.


Escreva 

    int passagem(int n, int v[])

    ...

    while(passagem(n,v));    <--- fica ordenado quando acabar.


Quantas comparações?
    no máximo (n-1)^2

Aula 13