Curso de Basic
Algoritmos de Ordenação
Você está em: MarMSX >> Cursos >> BASIC
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:
- O mais interno é responsável por varrer a lista, comparando elementos subjacentes e realizando eventuais trocas.
- O mais externo é responsável por disparar a varredura várias vezes, eliminando da ordenação o último elemento da lista (maior número) ao final de cada rodada do loop interno.
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:
- O mais interno é responsável por varrer a lista, encontrando o menor valor e trocando com a primeira posição da lista restante.
- O mais externo é responsável por disparar a varredura várias vezes, eliminando da ordenação o primeiro elemento da lista (menor número) ao final de cada rodada do loop interno.
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:
- Determinar o tamanho máximo de H baseado no tamanho da lista.
- Deslocando H até o final da lista, de uma em uma posição:
- Trocar todos os itens distantes H posições, desde que o índice não seja negativo.
- Diminuir o valor de H e repetir a operação, até que H=1.
- Nesse caso, o algoritmo se torna de Insertion Sort.
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:
- Devemos comparar sempre começando pela primeira letra de cada uma.
- Caso dê empate, passe para a próxima letra de cada string.
- Compare novamente, até que as letras sejam diferentes ou termine uma string.
- Se a letra atual da primeira string for maior que a segunda ou a segunda string tenha estourado o tamanho, troque as strings de posição.
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