Métodos de Ordenação

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE PERNAMBUCO
CAMPUS BELO JARDIM
ANNE INGRID F. BEZERRA
TÉCNICO INFORMÁTICA
2º C
MÉTODOS DE ORDENAÇÃO
Belo Jardim - PE
05-05-2009
Métodos de Ordenação
Ordenação consiste ao método de reorganizar um conjunto de objetos em

ordem crescente ou decrescente comparando os elementos para determinar
qual deles vem em primeira ordem na lista ordenada, tendo como objetivo
facilitar a recuperação de itens de um determinado conjunto.
Existem muitos algoritmos de ordenação, a escolha mais eficiente vai

depender de vários fatores, tais como: número de itens a ser classificado; se os
valores já estão agrupados em subconjuntos ordenados etc.
Atualmente há uma grande necessidade de guardar informações e possuí-

las ordenadas, seja por ordem alfabética, por idade, localidade entre outros.
Os principais Métodos de ordenação são:
•Método de ordenação por selecção (Selecção Directa)
• Método de ordenação por inserção (com Pivot)
• Método de ordenação por bolha (Bubble Sort)
• Método de torneio (Quick Sort)
Métodos de ordenação Bolha (“Bubble Sort”)
Por ser simples e fácil de entender e implementar, o Bubble Sort está entre os
mais conhecidos algoritmos de ordenação. Porém, devido a sua baixa
eficiência, devemos tratá-lo como uma solução mais para desenvolvimento de
raciocínio que de uso recorrente (embora não seja um problema usá-lo em
casos onde não exige muita performance, como quando desejamos ordenar
um conjunto com poucos elementos).
Seu princípio é a comparação e troca de valores entre posições consecutivas,

fazendo com que os valores mais altos ( ou mais baixos) migrem (“borbulhem”)
para o final do vetor a ser ordenado.
Ex:
int aux;
for ( i=0; i <= tam-2; i++ )
for ( j=0; j<= tam-2-i; j++ )
if ( Array[j] > Array[j+1] )
aux = Array[j];
Array[j] = Array[j+1];
Array[j+1] = aux
Selecção
O método de ordenação por Selecção Directa é levemente mais eficiente

que o método Bubblesort, ainda que se trate de um algoritmo apenas para
estudo e ordenação de pequenas listas. A lógica consiste em se varrer a lista
comparando todos os seus elementos com o primeiro. Caso o primeiro
elemento esteja desordenado em relação ao elemento que está sendo
comparado com ele no momento, é feita a troca. Ao se chegar ao final da lista,
teremos o menor valor ( ou o maior, conforme a comparação ) na primeira
posição do arranjo.
Int aux;
for( i=0; i <= tam - 2; i++ ) {
for( j=i+1; j <= tam - 1; j++ ) {
if ( Array[j] < Array[i] ) {
aux = Array[j];
Array[j] = Array[i];
Array[i] = aux;
Comparações de tempo:
Existe um ciclo que é executado n vezes, mas o tempo não é de ordem n,

pois é necessária a informação do menor elemento e isto produz outro ciclo,
logo o algoritmo é de ordem N^2.
Inserção
Este método é o mais rápido entre os outros métodos considerados básicos.

O algoritmo, consiste em ordenar uma lista utilizando uma sub-lista ordenada
localizada em seu inicio, e a cada novo passo, acrescentamos a esta sub-lista
mais um elemento, até que atingimos o último elemento da lista fazendo assim
com que ela se torne ordenada. Funciona como se ordenássemos um baralho
que temos na mão direita, para a mão esquerda, passando uma carta de cada
vez.
long int aux;

long int j;
for( long int i=1; i <= tam - 1; i++ ) {
aux = Array[i];
j = i - 1;
while ( j >= 0 && aux < Array[j] ) {
Array[j + 1] = Array[j] ;
j--;
}
Array[j+1] = aux;
Métodos mais eficientes

Merge sort
Este método baseia-se na estratégia do dividir para conquistar! A sua ideia

é dividir o vector em duas partes iguais, até que resultem dois vectores com
apenas um único elemento.
void merge(int M[50], int p, int r) {

int q;
if (p<r) {
q=((p+r)/2);
merge(M,p,q);
merge(M,q+1,r);
intercala(M,p,q,r);
}
}
void intercala(int M[50], int p, int q, int r) {

int prim, res, seg, k;
int C[50];
prim = res = p;
seg = q+1;
while(prim<=q && seg<=r) {
if(M[prim]<=M[seg]) {
C[res] = M[prim];
prim++;
} else {
C[res] = M[seg];
seg++;
}
res++;
}
if(prim>q)
for(k=seg; k<=r; k++) {
C[res] = M[k];
res++;
} else {
for(k=prim; k<=q; k++) {
C[res] = M[k];
res++;
}
}
for(k=p; k<=r; k++)
M[k] = C[k];
Que tempos de ordenação podemos esperar?
O algoritmo requer 2n passos, um para copiar a lista para a sequência

intermediária e outra para a reordenar. Logo é de O(2nlog(n)) = O(n log n).
Quicksort
O quicksort é um dos algoritmos de ordenação mais simples e eficientes que
existem. O seu principio é muito semelhante ao mergesort.
Primeiro a lista a ordenar é partida em duas partes, de maneira a que os

elementos primeira parte sejam menores ou iguais a todos os elementos da
segunda. Recursivamente, as duas partes são ordenadas pelo mesmo
algoritmo e são então combinadas para dar a lista final. O primeiro passo é
escolher um elemento x e depois dividir. A ideia usada neste algoritmo também
é a dividir para conquistar
void quick(int Q[50], int inicio, int fim) {

int meio;
if (inicio<fim) {
meio = particiona(Q, inicio, fim);
quick(Q, inicio, meio-1);
quick(Q, meio+1, fim);
}
}
int particiona(int Q[50], int inicio, int fim) {
int pivo,ultbaixo,temp,i;
pivo = Q[inicio];
ultbaixo = inicio;
for(i=inicio+1; i<=fim; i++) {
if (Q[i]<=pivo) {
ultbaixo++;
temp = Q[i];
Q[i] = Q[ultbaixo];
Q[ultbaixo] = temp;
}
}
temp = Q[inicio];
Q[inicio] = Q[ultbaixo];
Q[ultbaixo] = temp;
return(ultbaixo);
}
No melhor caso, quando a partição da lista produz duas listas de igual

tamanho, o algoritmo tem O(N*logN). No Pior caso, quando a divisão faz com
que todos os elementos se posicionem de um lado, o algoritmo tem O(n^2).

Métodos de Ordenação

Enviado por

Direitos autorais:

Formatos disponíveis

Métodos de Ordenação

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Métodos de Ordenação

Enviado por

Direitos autorais:

Formatos disponíveis

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE PERNAMBUCO

CAMPUS BELO JARDIM

ANNE INGRID F. BEZERRA

Ordenação consiste ao método de reorganizar um conjunto de objetos em

Existem muitos algoritmos de ordenação, a escolha mais eficiente vai

Atualmente há uma grande necessidade de guardar informações e possuí-

Os principais Métodos de ordenação são:

•Método de ordenação por selecção (Selecção Directa)

• Método de ordenação por inserção (com Pivot)

• Método de ordenação por bolha (Bubble Sort)

• Método de torneio (Quick Sort)

Métodos de ordenação Bolha (“Bubble Sort”)

Seu princípio é a comparação e troca de valores entre posições consecutivas,

O método de ordenação por Selecção Directa é levemente mais eficiente

Existe um ciclo que é executado n vezes, mas o tempo não é de ordem n,

Este método é o mais rápido entre os outros métodos considerados básicos.

long int aux;

Métodos mais eficientes

Este método baseia-se na estratégia do dividir para conquistar! A sua ideia

void merge(int M[50], int p, int r) {

void intercala(int M[50], int p, int q, int r) {

Que tempos de ordenação podemos esperar?

O algoritmo requer 2n passos, um para copiar a lista para a sequência

Primeiro a lista a ordenar é partida em duas partes, de maneira a que os

void quick(int Q[50], int inicio, int fim) {

No melhor caso, quando a partição da lista produz duas listas de igual

Você também pode gostar