Curso de Basic
Algoritmos de Ordenação


  Os algoritmos de ordenação nos permitem colocar uma lista numérica, alfanumérica ou de nomes em ordem crescente ou decrescente.
  Existem diversas soluções para a ordenação de listas, desde algoritmos simples e lentos até outros mais complexos, porém rápidos, como o Quick Sort. Entretanto, este curso irá abordar somente os algoritmos de ordenação mais simples, como o Bubble Sort, Selection Sort, Insertion Sort e Shell Sort.
  Primeiramente, será criada uma lista de 10 números aleatórios, no qual será ordenada de forma crescente por cada um desses algoritmos. Ao final, o conceito será extendido a uma lista de nomes, que será ordenada pelo algoritmo Bubble Sort.


 Bubble Sort

  O algoritmo de Bubble Sort consiste em comparar elementos subjacentes da lista e trocá-los de posição, caso o elemento que esteja na posição i seja maior que o elemento que esteja na posição i+1.

  O algoritmo consiste em dois loops aninhados:
  Loop interno

  A varredura varia de i=1 até i=N-1, onde N é o tamanho da lista.
  Caso o elemento i da lista seja maior que o elemento i+1, troque-os de posição na lista.
  Ao final dessa iteração (loop), o maior número da lista estará na última posição.

  Vejamos como funciona a varredura (loop interno) do Bubble Sort. Para isso, utilizaremos a seguinte lista com 4 elementos: { 4, 5, 2, 3 }.
  O loop interno varia de i=1 até i=N-1. Assim temos para cada valor de i:
Pos     1  2  3  4

i=0   { 4, 5, 2, 3 }
i=1   { 4, 5, 2, 3 }  4 > 5 ? Não e não troca.
i=2   { 4, 5, 2, 3 }  5 > 2 ? Sim e troca.
i=3   { 4, 2, 5, 3 }  5 > 3 ? Sim e troca.

  Ao final dessa rodada, o loop interno gerou a seguinte lista:
{ 4, 2, 3, 5 }

  Loop externo

  Ao final da execução do loop interno, o útimo elemento da lista é descartado da ordenação, ou seja, N=N-1.
  Conforme visto no exemplo acima, uma passada somente na lista não é o suficiente para ordená-la por completo. Dessa forma, o loop interno é disparado mais uma vez.
  Esta operação é realizada até que o tamanho da lista seja igual a 2, onde restam apenas dois elementos para a troca. Dessa forma, o loop externo varia também de 1 até N-1.

  Para o exemplo anterior, temos:
N=3
{ 4, 2, 3, 5 }  O último elemento está descartado na próxima rodada do loop interno.

  Execução completa:
Pos     1  2  3  4

i=0   { 4, 5, 2, 3 }

j=1   1a. rodada do loop interno
i=1   { 4, 5, 2, 3 }  4 > 5 ? Não e não troca.
i=2   { 4, 5, 2, 3 }  5 > 2 ? Sim e troca.
i=3   { 4, 2, 5, 3 }  5 > 3 ? Sim e troca.
      { 4, 2, 3, 5 }

j=2   2a. rodada do loop interno
i=1   { 4, 2, 3, 5 }  4 > 2 ? Sim e troca.
i=2   { 2, 4, 3, 5 }  4 > 3 ? Sim e troca.
      { 2, 3, 4, 5 }

j=3   3a. rodada do loop interno
i=1   { 2, 3, 4, 5 }  2 > 3 ? Não e não troca.
      { 2, 3, 4, 5 }

  Otimização do algoritmo

  O algoritmo pode ser otimizado, introduzindo-se um flag que indica se houve alguma troca durante a execução da rodada corrente do loop interno. Caso não haja qualquer troca, pode-se encerrar o programa, uma vez que a lista já está ordenada.

  Pseudo-código para o Bubble Sort:
para j ← 1 até N-1 faça
  flag ← falso;

  para i ← 1 até N-j faça
    se lista(i) > lista (i+1) então
      troca(lista(i), lista(i+1));
      flag ← verdadeiro;
    fim_se  
  fim_para

  se flag = falso então
    fim;
  fim_se
fim_para

  O programa em Basic que cria uma lista, ordena e calcula o tempo gasto para ordenar é mostrado a seguir.
5 N=10
10 DIM V(N)
20 FOR I=1 TO N
30 V(I) = 1 + INT(RND(-TIME)*100)
40 NEXT I
50 PRINT"Vetor desordenado:"
60 GOSUB 500
70 PRINT:PRINT"Ordenando usando o Bubble Sort ...":PRINT
80 TIME=0
90 GOSUB 600
100 T=TIME
120 PRINT"Vetor ordenado:"
130 GOSUB 500
140 PRINT:PRINT"Tempo:";T/60;"segundos."
150 END
500 '
510 ' Imprime
520 '
530 FOR I=1 TO N
540 PRINT V(I);
550 NEXT I
560 PRINT
570 RETURN
600 '
610 ' Bubble Sort
620 '
630 FOR J=1 TO N-1
640 FLAG=0
650 FOR I=1 TO N-J
660 IF V(I) > V(I+1) THEN AUX=V(I):V(I)=V(I+1):V(I+1)=AUX:FLAG=1
670 NEXT I
680 IF FLAG=0 THEN RETURN
690 NEXT J
700 RETURN


 Selection Sort

  o Selection Sort consiste em ir colocando os menores valores no inicio da lista, onde cada iteração busca pelo menor valor da lista restante.

  O algoritmo consiste em dois loops aninhados:
  Loop interno

  Assume-se o primeiro elemento da lista como o menor valor encontrado antes de começar a varrer a lista. Então, guarda-se a posição do menor valor da lista na variável P, ou seja, P=1.
  A varredura varia de i=2 até i=N, onde N é o tamanho da lista.
  O valor do elemento atual lista(i) é comparado com o menor valor encontrado lista(P). Caso o valor do elemento corrente seja menor, então guarde a posição i em P.
  Ao final dessa iteração (loop), será trocado o menor número encontrado com o primeiro elemento da lista.

  Vejamos como funciona a varredura (loop interno) do Selection Sort. Para isso, utilizaremos a seguinte lista com 4 elementos: { 4, 5, 2, 3 }.
  O loop interno varia de i=2 até i=N. Assim temos para cada valor de i:
Pos     1  2  3  4

i=0   { 4, 5, 2, 3 }  P=1, lista(P)=4
i=2   { 4, 5, 2, 3 }  5 < 4 ? Não.
i=3   { 4, 5, 2, 3 }  2 < 4 ? Sim. P=3, lista(P)=2
i=4   { 4, 5, 2, 3 }  3 < 2 ? Não.

  O menor número encontrado na lista, que é o 2, encontra-se na posição 3. Dessa forma, trocam-se as posições 1 e 3:
{ 4, 5, 2, 3 }
  +--->
    <---+
{ 2, 5, 4, 3 }

  Loop externo

  Ao final da execução do loop interno, o primeiro elemento da lista é descartado da ordenação.
  Conforme visto no exemplo acima, uma passada somente na lista não é o suficiente para ordená-la por completo. Dessa forma, o loop interno é disparado mais uma vez.
  Esta operação é realizada até que o tamanho da lista seja igual a 2, onde restam apenas dois elementos. Dessa forma, o loop externo varia de 1 até N-1.

  Para o exemplo anterior, temos:
{ 2, 5, 4, 3 }  O primeiro elemento está descartado para a próxima iteração.

  Execução completa:
Pos     1  2  3  4

j=1
i=0   { 4, 5, 2, 3 }  P=1, lista(P)=4
i=2   { 4, 5, 2, 3 }  5 < 4 ? Não.
i=3   { 4, 5, 2, 3 }  2 < 4 ? Sim. P=3, lista(P)=2
i=4   { 4, 5, 2, 3 }  3 < 2 ? Não.
Troca { 2, 5, 4, 3 }

j=2
i=0   { 2, 5, 4, 3 }  P=2, lista(P)=5
i=3   { 2, 5, 4, 3 }  4 < 5 ? Sim. P=3, lista(P)=4
i=4   { 2, 5, 4, 3 }  3 < 4 ? Sim. P=4, lista(P)=3
Troca { 2, 3, 4, 5 }

j=3
i=0   { 2, 3, 4, 5 }  P=3, lista(P)=4
i=4   { 2, 3, 4, 5 }  5 < 4 ? Não.
Troca { 2, 3, 4, 5 }

  Pseudo-código para o Selection Sort:
para j ← 1 até N-1 faça
  P ← j;

  para i ← j+1 até N faça
    se lista(i) < lista(P) então
      P ← i;
    fim_se  
  fim_para

  troca(lista(j), lista(P));
fim_para

  O programa em Basic que cria uma lista, ordena e calcula o tempo gasto para ordenar é mostrado a seguir.
5 N=10
10 DIM V(N)
20 FOR I=1 TO N
30 V(I) = 1 + INT(RND(-TIME)*100)
40 NEXT I
50 PRINT"Vetor desordenado:"
60 GOSUB 500
70 PRINT:PRINT"Ordenando usando o Selection Sort ...":PRINT
80 TIME=0
90 GOSUB 600
100 T=TIME
120 PRINT"Vetor ordenado:"
130 GOSUB 500
140 PRINT:PRINT"Tempo:";T/60;"segundos."
150 END
500 '
510 ' Imprime
520 '
530 FOR I=1 TO N
540 PRINT V(I);
550 NEXT I
560 PRINT
570 RETURN
600 '
610 ' Selection Sort
620 '
630 FOR J=1 TO N-1
640 P=J
650 FOR I=J+1 TO N
660 IF V(I) < V(P) THEN P=I
670 NEXT I
680 AUX=V(P) : V(P)=V(J) : V(J)=AUX
690 NEXT J
700 RETURN


 Insertion Sort

  O Insertion Sort consiste em dividir a lista em uma parte ordenada e outra não ordenada, inserindo a cada rodada um elemento da lista não ordenada na lista ordenada, na posição correta.

  Inicialmente, a primeira posição da lista é considerada como a lista ordenada e o restante como lista não ordenada.
  Então, varre-se a lista não ordenada, inserindo os elementos uma a um na lista ordenada.
  A inserção de novos elementos na lista ordenada deverá ser na posição correta, ou seja, de forma ordenada.

  Vejamos como funciona o Insertion Sort. Para isso, utilizaremos a seguinte lista com 4 elementos: { 4, 5, 2, 3 }.
   - Lista ordenada
   - Lista não ordenada

Passo 0:
{ 4, 5, 2, 3 }

Passo 1:
{ 4, 5, 2, 3 }  Inserir o elemento 5 na lista ordenada.
{ 4, 5, 2, 3 }

Passo 2:
{ 4, 5, 2, 3 } Inserir o elemento 2 na lista ordenada.
{ 2, 4, 5, 3 }

Passo 3:
{ 2, 4, 5, 3 } Inserir o elemento 3 na lista ordenada.
{ 2, 3, 4, 5 }

  A primeira vista, esse algoritmo parece mais simples que os demais. Entretanto, há a necessidade de varrer a lista ordenada quando um elemento é inserido, de forma a encontrar a posição dele. Além disso, pode ser necessário o deslocamento dos demais elementos da lista para o "encaixe" desse número.

  Pseudo-código para o Insertion Sort:
para j ← 2 até N faça
  para i ← 1 até j-1 faça
    se lista(i) > lista(J) então
      aux ← lista(j);
        para k ← j-1 até i passo -1 faça
          lista(k+1) ← lista(k);
        fim_para
      lista(i) ← aux;
    fim_se  
  fim_para
fim_para

  O programa em Basic que cria uma lista, ordena e calcula o tempo gasto para ordenar é mostrado a seguir.
5 N=10
10 DIM V(N)
20 FOR I=1 TO N
30 V(I) = 1 + INT(RND(-TIME)*100)
40 NEXT I
50 PRINT"Vetor desordenado:"
60 GOSUB 500
70 PRINT:PRINT"Ordenando usando o Insertion Sort ...":PRINT
80 TIME=0
90 GOSUB 600
100 T=TIME
120 PRINT"Vetor ordenado:"
130 GOSUB 500
140 PRINT:PRINT"Tempo:";T/60;"segundos."
150 END
500 '
510 ' Imprime
520 '
530 FOR I=1 TO N
540 PRINT V(I);
550 NEXT I
560 PRINT
570 RETURN
600 '
610 ' Insertion Sort
620 '
630 FOR J=2 TO N
640 FOR I=1 TO J-1
650 IF V(I) <= V(J) THEN 710
660 AUX=V(J)
670 FOR K=J-1 TO I STEP -1
680 V(K+1)=V(K)
690 NEXT K
700 V(I)=AUX
710 NEXT I,J
720 RETURN


 Shell Sort

  O Shell Sort é uma variação do Insertion Sort, onde elementos distantes H posições são trocados de forma a melhorar a performance do algoritmo.

  O algoritmo funciona muito bem para vetores grandes, onde sua performance, se comparado a dos anteriores, é bem superior. Para se ter uma idéia, testes feitos em um MSX 1 constataram que o Insertion Sort leva em média 58 segundos para ordenar um vetor de 100 elementos, enquanto que o Shell Sort levou apenas 13 segundos para mesmo vetor.

  Passos:   Exemplo: seja o vetor V = { 7, 4, 3, 8, 1, 9, 2, 5, 10, 6 }. Para um vetor com 10 posições, H incial é igual a 4 (ver pseudo-código abaixo).
H=4

i=5
{ 7, 4, 3, 8, 1, 9, 2, 5, 10, 6 }  1 < 7 ? Sim. Troca de posição.
{ 1, 4, 3, 8, 7, 9, 2, 5, 10, 6 }

i=6
{ 1, 4, 3, 8, 7, 9, 2, 5, 10, 6 }  9 < 4 ? Não.

i=7
{ 1, 4, 3, 8, 7, 9, 2, 5, 10, 6 }  2 < 3 ? Sim. Troca de posição.
{ 1, 4, 2, 8, 7, 9, 3, 5, 10, 6 }

i=8
{ 1, 4, 2, 8, 7, 9, 3, 5, 10, 6 }  5 < 8 ? Sim. Troca de posição.
{ 1, 4, 2, 5, 7, 9, 3, 8, 10, 6 }

i=9
{ 1, 4, 2, 5, 7, 9, 3, 8, 10, 6 } 10 < 7 ? Não.
Observe que agora são três itens comparados.
A comparação e troca é feita em cascata, começando pelo item mais a direita:
10 compara com o 7 e depois o 7 compara com o 1.

i=10
{ 1, 4, 2, 5, 7, 9, 3, 8, 10, 6 } 6 < 9 ? Sim. Troca de posição.
{ 1, 4, 2, 5, 7, 6, 3, 8, 10, 9 } 6 < 4 ? Não.

H=1
...

  Pseudo-código para o Shell Sort:
H ← 1;

enquanto H < N faça
  H ← H*3 + 1;
fim_enquanto

faça
  H ← H/3;

  para i ← H+1 até N faça
    aux ← V[i];
    j ← i-H;

    enquanto j>0 e aux<V[j] faça
      V[j+H] ← V[j];
      j ← j-H;
    fim_enquanto

    V[j+H] ← aux;
  fim_para
enquanto H>1;

  O programa em Basic que cria uma lista, ordena e calcula o tempo gasto para ordenar é mostrado a seguir.
5 N=10
10 DIM V(N)
20 FOR I=1 TO N
30 V(I) = 1 + INT(RND(-TIME)*100)
40 NEXT I
50 PRINT"Vetor desordenado:"
60 GOSUB 500
70 PRINT:PRINT"Ordenando usando o Shell Sort ...":PRINT
80 TIME=0
90 GOSUB 600
100 T=TIME
120 PRINT"Vetor ordenado:"
130 GOSUB 500
140 PRINT:PRINT"Tempo:";T/60;"segundos."
150 END
500 '
510 ' Imprime
520 '
530 FOR I=1 TO N
540 PRINT V(I);
550 NEXT I
560 PRINT
570 RETURN
600 '
610 ' Shell Sort
620 '
630 H=1
640 H=H*3+1 : IF H<N THEN 640
650 H=H\3
660 FOR I=H+1 TO N
670 AUX=V[I]
680 J=I-H
690 IF J<=0 THEN 730 ELSE IF AUX>=V[J] THEN 730
700 V[J+H]=V[J]
710 J=J-H
720 GOTO 690
730 V[J+H]=AUX
740 NEXT I
750 IF H>1 THEN 650
760 RETURN


 Comparativo de desempenho

  Os quatro algoritmos podem ser rodados de forma a comparar o desempenho de cada um deles, variando-se o tamanho da lista.
  Para isso, vamos rodar cada algoritmo 20 vezes e calcular a média dos tempos. Em cada um deles, acrescente as seguintes linhas:
14 TT=0
15 FOR EX=1 TO 20
e
145 TT=TT+T/60
146 NEXT EX
147 TT=TT/20
148 PRINT"Média:";TT

  A partir desse código, a média é calculada automaticamente.

  Para cada experimento, utilizar os seguintes valores para N: 10, 25, 50 e 100.

  Tempos obtidos nas experiências (MSX 1):

Algoritmo N=10 N=25 N=50 N=100
Bubble 0,79 4,96 21,37 88,72
Selection 0,52 2,82 10,52 40,04
Insertion 0,62 3,74 14,72 58,37
Shell 0,66 2,20 5,64 13,56

  Obs: tempo em segundos.


 Ordenar lista com nomes

  A linguagem Basic do MSX permite a comparação de strings, de forma a saber se uma seqüência de caracteres é classificada em ordem alfabética antes ou depois da outra. Veja o exemplo a seguir.
10 A$="MSX"
20 B$="PINGUIM"
30 IF A$<B$ THEN PRINT"MSX vem primero" ELSE PRINT"PINGUIM VEM PRIMEIRO"
  Saída:
  MSX vem primero

  Dessa forma, basta substituir os vetores numéricos nos algoritmos apresentados por vetores alfanuméricos, ou seja, por exemplo, substituir v(n) por v$(n).

  Exemplo de ordenação de nomes usando o Bubble Sort.
5 N=10
10 DIM V$(N)
20 FOR I=1 TO N
30 READ V$(I)
40 NEXT I
50 PRINT"Vetor desordenado:"
60 GOSUB 500
70 PRINT:PRINT"Ordenando usando o Bubble Sort ...":PRINT
80 TIME=0
90 GOSUB 600
100 T=TIME
120 PRINT"Vetor ordenado:"
130 GOSUB 500
140 PRINT:PRINT"Tempo:";T/60;"segundos."
150 END
500 '
510 ' Imprime
520 '
530 FOR I=1 TO N
540 PRINT V$(I);" ";
550 NEXT I
560 PRINT
570 RETURN
600 '
610 ' Bubble Sort
620 '
630 FOR J=1 TO N-1
640 FLAG=0
650 FOR I=1 TO N-J
660 IF V$(I) > V$(I+1) THEN SWAP V$(I),V$(I+1):FLAG=1
670 NEXT I
680 IF FLAG=0 THEN RETURN
690 NEXT J
700 RETURN
800 DATA Paula, Renata, Carolina, Aline, Fabiana
810 DATA Julia, Bianca, Diva, Carol, Marcia

  Obs: nesse exemplo utilizamos o comando SWAP para a troca de posições. Experimente utilizar o comando SWAP nos outros algoritmos e veja se há ganho de performance.


 Ordenar lista de nomes manualmente com o Bubble Sort

  O algoritmo a seguir ilustra como funciona a ordenação de strings de forma manual, sem a utilização da comparação de strings. Essa ilustração é útil em linguagens onde não é possível comparar strings, como por exemplo, o Assembly.

  Anteriormente, o empate entre valores não afetava o algoritmo de ordenação. Entretanto, agora cada elemento é composto e não mais simples, fazendo com que parte da cadeia seja analisada para desempatar as strings.
  Vejamos como:
Com números:
4 compara com 4 - empate, ok!

Com strings:
"A" compara com "A" - empate, ok!
Mas:
"A" compara com "AB" - Não é empate !

  Os passos de comparação de strings são descritos a seguir:   Exemplos:
"Dado" com "Dada"

"Dado" x "Dada" - "D" = "D", próxima letra.
"Dado" x "Dada" - "a" = "a", próxima letra.
"Dado" x "Dada" - "d" = "d", próxima letra.
"Dado" x "Dada" - "o" > "a", Troca.


"AB" com "A"
"AB" x "A" - "A" = "A", próxima letra.
Estourou a segunda string. Nesse caso, troca.

  O programa em Basic que cria uma lista de nomes, ordena e calcula o tempo gasto para ordenar é mostrado a seguir.
5 N=10
10 DIM V$(N)
20 FOR I=1 TO N
30 READ V$(I)
40 NEXT I
50 PRINT"Lista desordenada:"
60 GOSUB 500
70 PRINT:PRINT"Ordenando lista usando o Bubble Sort ...":PRINT
80 TIME=0
90 GOSUB 600
100 T=TIME
120 PRINT"Lista ordenada:"
130 GOSUB 500
140 PRINT:PRINT"Tempo:";T/60;"segundos."
150 END
500 '
510 ' Imprime
520 '
530 FOR I=1 TO N
540 PRINT V$(I)
550 NEXT I
560 PRINT
570 RETURN
600 '
610 ' Bubble Sort
620 '
630 FOR J=1 TO N-1
640 FLAG=0
650 FOR I=1 TO N-J
660 P=1 : TA=LEN(V$(I)) : TB=LEN(V$(I+1))
670 LA$=MID$(V$(I),P,1) : LB$=MID$(V$(I+1),P,1)
680 IF LA$ = LB$ AND P<=TA AND P<=TB THEN P=P+1 : GOTO 670
690 IF LA$ > LB$ OR (P<=TA AND P>TB) THEN AUX$=V$(I):V$(I)=V$(I+1):V$(I+1)=AUX$:FLAG=1
700 NEXT I
710 IF FLAG=0 THEN RETURN
720 NEXT J
730 RETURN
1000 DATA Pedro, Maria Antonieta, Catarina, Paulo, Paula, Maria, Saulo, Fabio, Pamela, Diego


 Ordenação Decrescente

  A ordenação de números ou strings de forma decrescente pode ser alcançada realizando pequenas alterações nos algoritmos apresentados ou através da simples reversão do vetor, uma vez que os valores já estão em ordem sequencial.

  A rotina a seguir reverte um vetor, de forma a apresentar os números de forma decrescente.
800 '
810 ' Reverte vetor
820 '
830 FOR I=1 TO N/2
840 AUX=V(I) : V(I)=V(N-I+1) : V(N-I+1)=AUX
850 NEXT I
860 RETURN


<< Anterior Basic Próxima >>


/MARMSX/CURSOS/Basic