O nosso objetivo é analisar os seguintes tipos de ordenação :
a. Selection Sort
b. Bubble Sort
c. Insertion Sort
d. Selection Sort
Este método é um dos mais simples e intuitivos dentre os métodos existentes. Sua estratégia básica é selecionar o menor elemento da sequência considerada e colocá-lo no início da sequência. Assim, dada uma sequência de tamanho n, várias iterações são efetuadas, sendo que a cada vez que esta estratégia é aplicada, uma nova sequência é gerada pela eliminação do menor elemento da sequência original.
Procedure SelectionSort ( var vet : vetor; n : integer);
{ordenado crescente}
var
i, j, pmin : integer;
begin
for i¬ 1 to (n-1) do
begin
pmin ¬ i;
for j¬ (i+1) to n do
if vet[j] < vet[pmin]
then pmin ¬ j;
trocar (vet[i], vet[pmin] ) ;
end;
end;
b. Bubble Sort
A estratégia utilizada pelo BubbleSort consiste de comparações e trocas entre elementos consecutivos da sequência, a fim de "empurrar" o maior elemento para a última posição. Assim, várias iterações são efetuadas e, para cada sequência considerada, a aplicação da estratégia gera uma nova sequência pela eliminação do maior elemento da sequência original.
Além disto, uma variável de controle (lógica) é utilizada para registrar a ocorrência ou não de troca entre elementos da sequência. Quando nenhuma troca é efetuada, tem-se que a sequência considerada já estava ordenada. Esta particularidade determina, em alguns casos, um número menor de comparações que o método SelectionSort.
Procedure BubbleSort ( var vet : vetor ; n integer) ;
{ordem crescente}
var
i, limite : integer;
trocou : boolean;
begin
limite ¬ n;
repeat
trocou ¬ false;
for i¬ 1 to (limite - 1) do
begin
if vet[i] > vet [i+1] then
begin
trocar(vet[i], vet[i+1]);
trocou ¬ true;
end;
end;
limite ¬ limite - 1
until not trocou
end;
c. Insertion Sort
Este método baseia-se no seguinte processo de inserção controlada:
-Com o primeiro elemento da seqüência forma-se uma seqüência de tamanho 1, ordenada.
-Cada elemento restante da seqüência original é inserido na seqüência, de modo que esta permaneça ordenada. Isto é feito através de uma pesquisa na seqüência ordenada que determina a posição que o novo elemento deverá ser inserido.
-Quando um elemento é inserido a frente de outro, estes deverão ser deslocados de uma posição.
RECURSIVIDADE
Recursão é um método geral para resolver problemas reduzindo-os a problemas mais simples do mesmo tipo. A estrutura geral de uma solução recursiva de um problema é assim :
Resolva de forma recursiva um problema.
-Se o problema é trivial, faça o óbvio (resolva-o)
-Simplifique o problema
-Resolva de forma recursiva (um problema mais simples)
-Combine (na medida do possível) a solução do(os) problemas mais simples em uma solução do problema original.
Um subprograma recursivo chama a si próprio constantemente, cada vez em uma situação mais simples, até chegar ao caso trivial, quando para. Devemos lembrar que recursividade deve ser utilizada na solução de problemas que tenham a natureza recursiva.
Exemplos :
a. Somatório de inteiros - Se n =1; Somatório = 1. Caso contrário Somatório = n + Somatório(n-1)
b. Fatorial - Se n=0 ou n=1 ; Fatorial = 1. Caso contrário Fatorial = n*Fatorial(n-1)
c. MDC - Se b divide a, então o MDC é b. Caso contrário, MDC(a,b) = MDC(b,a mod b)
d. N-ésimo termo da série de Finonacci . 1° e 2° = 1 e n-ésimo = (n-1)+(n-2)
e. Torre de hanoi