Ordenação pelo Método Bolha
> O Método Bolha, também chamado de Bubble Sort, é um método de ordenação de vetores por seleção e troca. É um dos métodos mais simples, mas, dentre todos os métodos simples, é o mais eficaz. É adequado apenas para arquivos pequenos.
Esse método funciona da seguinte forma: esse método irá percorrer o vetor várias vezes e, durante a análise, ele irá comparar os valores dois a dois e, caso estejam fora da ordem, esse algoritmo trocará a posição desses valores, deixando estes ordenados, ou seja, deixando-os em ordem crescente. Isso irá se repetir com todas as posições do vetor até a última posição, garantindo que o elemento de maior valor seja levado para a última posição.
Vale ressaltar que o tempo de consumo do Bubble Sort é proporcional ao número de execuções da comparação sendo que, no melhor caso, o algoritmo executa n²/2 operações relevantes, onde n representa o número de elementos do vetor e, no pior caso, são feitas 2n² operações no vetor.
Se o vetor a ser ordenado for colocado na vertical, com o Item[n] em cima e Item[1] embaixo, durante cada passo o menor elemento “sobe” até encontrar um elemento maior ainda, como se uma bolha subisse dentro de um tudo de acordo com sua densidade e, por isso, esse método recebe o nome de “bolha”.
Exemplo:
#include
int main(void)
{
int i, j,v[100], n, temp;
for (i = n - 1; i > 0; i--)
for (j = 0; j < i; j++)
if (v[j] > v[j+1])
{
temp = v[j];
v[j] = v[j+1;
v[j+1 = temp;
}
return 0;
}
Método da Bolha Melhorado
O Método da Bolha Melhorado é o próprio método bolha, mas com algumas alterações. Esse método é finalizado quando nenhuma alteração foi feita após uma passada no vetor, diminuindo o tempo de consumo do algoritmo.
Exemplo:
#include
int main(void)
{
int i, j, v[100], n, temp, troca;
troca = 1;
for (i= n-1; (i >= 1) && (troca == 1); i--) {
troca = 0;
for (j= 0; j < i ;j++) {
if (v[j] < v[j+1]) {
temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
troca = 1;
}
}
}
return 0;
}
Ordenação pelo Método Quicksort
O Método Quicksort é o algoritmo de ordenação interna mais rápido que se conhece para uma ampla variedade de situações, sendo provavelmente mais utilizado do que qualquer outro algoritmo. O algoritmo foi inventado por C. A. R. Hoare na década de 1960, quando visitava a Universidade de Moscou como estudante. Esse algoritmo foi publicado em 1962, depois de uma série de refinamentos.
A ideia básica do Quicksort é partir o problema de ordenar um conjunto com n itens em dois problemas menores. Depois de dividir o problema, os problemas menores são ordenados independentemente e depois os resultados são combinados para produzir a solução do problema maior.
A parte mais delicada desse método se refere à divisão da partição. Deve-se rearranjar o vetor na forma A[Esq..Dir] através da escolha arbitrária de um item x do vetor chamado pivô, de tal forma que ao final o vetor A está particionado em uma parte esquerda com chaves menores ou iguais a x e uma parte direita com chaves maiores ou iguais a x.
O Procedimento do Algoritmo Quicksort se dá da seguinte forma:
1. Escolher arbitrariamente um item do vetor e colocar este valor em x;
2. Percorrer o vetor a partir da esquerda até que um item A[i] ³ x é encontrado; da mesma maneira, percorrer o vetor a partir da direita até que um item A[j] £ x é encontrado;
3. Como os itens A[i] e A[j] não estão na ordem correta no vetor final, eles devem ser trocados;
4. Continuar o processo até que os índices i e j se cruzem em algum ponto do vetor.
Ao final do processo, o vetor A[Esq..Dir] está particionado de tal forma que:
>> Os itens em A[Esq], A[Esq+1], ... , A[j] são menores ou iguais a x.
>> Os itens A[i], A[i+1], ... , A[Dir] são maiores o iguais a x.
O método é ilustrado para o conjunto de seis chaves apresentado na figura abaixo. O item x é escolhido como sendo A[(i+j)div2]. Como inicialmente i = 1 e j = 6, então x = A[3] = D, o qual aparece em destaque na segunda linha da mesma figura. A varredura a partir da posição 1 pára no item O e a varredura a partir da posição 6 pára no item A, sendo os dois itens trocados, como mostrado na terceira linha da figura. A seguir, a varredura a partir da posição 2 pára no item R e a varredura a partir da posição 5 pára no item D, e então os dois itens são trocados, como mostrado na quarta linha.
Neste momento i e j se cruzam (i = 3 e j = 2), o que encerra o processo de partição.
1 2 3 4 5 6
i = 1 O R D E N A
i = 2 A R D E N O
i = 3 A D R E N O
Feito este procedimento, o algoritmo agora terá de fazer a ordenação, ou seja, o refinamento final do procedimento Quicksort.
Veja o exemplo de ordenação usando o Quicksort:
1 2 3 4 5 6
Chaves iniciais O R D E N A
i = 1 A D R E N O
i = 2 A D
i = 3 E R N O
i = 4 N R O
i = 5 O R
i = 6 A D E N O R
Algoritmo do Procedimento Partição:
procedure Particao (Esq, Dir: Índice; var i, j : Índice);
var pivô, x: Item;
begin
i := Esq;
j := Dir;
pivô := A[(i+j) div 2)];
repeat;
while pivô.Chave > A[i].Chave do i := i+1;
while pivô.Chave < A[j].Chave do j :=j-1;
if i <= j then begin
x := A[i]; A[i] := A[j]; A[j] :=x;
i := i+1; j :=j-1;
end;
until i>j;
end;
Analisando a procedure:
>> Esq e Dir são índices para definir os sub-vetores do vetor original A a ser particionado
>> i e j retornam as posições finais das partições, onde:
> A[Esq], A[Esq+1],..., A[j] são menores ou iguais a x
> A[i], A[i+1],..., A[Dir] são maiores ou iguais a x
>> O vetor é uma variável global ao procedimento Partição
Procedimento Quicksort:
procedure Quicksort (var A: Vetor);
{-- Entra aqui o procedimento partição --}
procedure Ordena (Esq, Dir : Índice);
var i, j, Índice;
begin
partição (Esq, Dir, i, j);
if Esq < j then Ordena (Esq, j);
if i < Dir then Ordena (i, Dir);
end;
begin
Ordena (1, n);
end;
Uma característica interessante do Quicksort é a sua ineficiência para arquivos já ordenados quando a escolha do pivô e inadequada. Por exemplo, a escolha sistemática dos extremos de um arquivo já ordenado leva ao seu pior caso. O pior caso pode ser evitado através de pequenas modificações no programa.
Ordenação pelo Método Selection Sort
O algoritmo de ordenação por seleção (selection sort) é um dos métodos de ordenação mais simples que existem. Além disso, o método possui um comportamento espetacular quanto ao número de movimentos de registros, cujo tempo de execução é linear no tamanho da entrada, o que é muito difícil de ser batido por qualquer outro método. Consequentemente, este é o algoritmo a ser utilizado para arquivos com registros muito grandes.
Este método possui alguns aspectos negativos, são eles: o fato do arquivo já estar ordenado não ajudar em nada, pois o custo continua quadrático; o algoritmo não é estável, pois ele nem sempre deixa os registros com chaves iguais na mesma posição relativa.
Este método funciona da seguinte forma: selecione o menor item do vetor e a seguir troque-o com o item que está na primeira posição do vetor. Repita estas duas operações com os n-1 itens restantes, depois com os n-2 itens, até que reste apenas um elemento. Ou seja, o método passará sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição e assim por diante.
Exemplo de algoritmo:
procedure Seleção (var A: Vetor);
var i, j, Min : Índice;
x : Item;
begin
for i := 1 to n-1 do
begin
Min i := i;
for j := i+1 to n do if A [j].Chave < A[Min].Chave then Min := j;
x := A[Min]; A[Min] := A[i]; A[i] := x;
end;
end;
Nenhum comentário:
Postar um comentário