Introdução às Estruturas de Dados/Algoritmos de Ordenação

Ordenação é o ato de se colocar os elementos de uma sequência de informações, ou dados, em uma relação de ordem predefinida. O termo técnico em inglês para ordenação é sorting, cuja tradução literal é "classificação".

Dado uma seqüencia de n dados:

$<a_{1},a_{2},...,a_{n}>$

O problema de ordenação é uma permutação dessa seqüencia:

$<a_{1}^{\prime },a_{2}^{\prime },...,a_{n}^{\prime }>$

tal que:

$a_{1}^{\prime }\leq a_{2}^{\prime }\leq ...\leq a_{n}^{\prime }$

para alguma relação de ordem.

Algumas ordens são facilmente definidas. Por exemplo, a ordem numérica, ou a ordem alfabética --crescentes ou decrescentes. Contudo, existem ordens, especialmente de dados compostos, que podem ser não triviais de se estabelecer.

Um algoritmo que ordena uma conjunto, geralmente representada num vetor, é chamado de algoritmo de ordenação. Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem -- em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica.Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.

Entre os mais importantes, podemos citar bubble sort (ou ordenação por flutuação), heap sort (ou ordenação por heap), insertion sort (ou ordenação por inserção), merge sort (ou ordenação por mistura) e o quicksort. Existem diversos outros, que o aluno pode com dedicação pesquisar por si. Para estudo no entanto nos concentraremos nos principais : Selection Sort, Bubble Sort e Quicksort.

Natureza dos Dados

Para melhor escolha de um método de ordenação é preciso saber sobre a natureza dos dados que serão processados. Entre elas destacam-se duas: Tempo de acesso a um elemento e a possibilidade de acesso direto a um elemento.

O tempo de acesso a um elemento é a complexidade necessária para acessar um elemento em uma estrutura;

1 Ex: Uma estante de livros com seu títulos bem visíveis.

A possibilidade de acesso direto é a capacidade ou impossibilidade de acessar um elemento diretamente na estrutura.

1 Ex: Uma pilha de livros dentro de uma caixa, onde precisamos tirar um a um para saber qual a sua natureza.

Para classificarmos estes dois ambientes de atuação, costumamos utilizar o meio em que está armazenado os dados. Em termos computacionais utiliza-se a designação Ordenação Interna, quando queremos ordenar informações em memória. E Ordenação Externa, quando queremos ordenar informações em arquivo.

Selection Sort (Ordenação por Seleção)

O Selection Sort utiliza um o conceito de "selecionar o elemento mais apto". Ele seleciona o menor ou maior valor do vetor p.ex. e passa para a primeira (ou última posição dependendo da ordem requerida), depois o segundo menor para a segunda posição e assim sucessivamente com (n-1) elementos restantes até os dois últimos.

Teste de Mesa de Selection Sort

Vetor inicial:

4

3

1

2

Primeira passagem: Posição 0- compara 4 com 3.Como 3 é menor que 4 este é fixado como mínimo, compara 3 com 1. Como este é menor do que 3 é fixado como mínimo.Compara 1 com 2. Como continua sendo menor, é fixado. Ao chegar ao final do vetor, como 1 é o menor elemento em comparação com o 4, eles trocam de posição.

1

3

4

2

Segunda Passagem: Posição 1- como já temos 1 como o menor elemento do vetor, passamos para a posição 1. Comparamos 3 com 4.Como é menor, 3 continua como mínimo.Compara com 2. Como 2 é menor este é fixado como mínimo.Ao chegar ao final do vetor, como 2 é o menor elemento em comparação com o 3, eles trocam de posição.

1

2

4

3

Terceira Passagem: Posição 2- pegamos o elemento da posição 2 (4) e comparamos com o 3. Como 3 é o último elemento do vetor e é menor do que 4 , trocamos as posições.Como os dois elementos são os últimos do vetor, o Selection Sort encerra-se.

1

2

3

4

Algoritmo do Selection Sort

O algoritmo normalmente é implementado por duas repetições iterando sobre a estrutura em questão. Um exemplo de algoritmo é:

para i=0 até n-1

mínimo=i

para j=i+1 até N

se vetor[j]<vetor[mínimo]

mínimo=j

auxiliar=vetor[i]

vetor[i]=vetor[mínimo]

vetor[mínimo]=auxiliar

Bubble Sort (Ordenação Bolha)

O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A idéia é comparar dois elementos e trocá-los de posição, até que os elementos de maior valor sejam levados para o final do vetor. O processo continua até a ordenação total do vetor lembrando a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

A complexidade desse algoritmo é de ordem quadrática (O(n²)). Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados. Também é necessária uma condição de parada, geralmente uma flag ou variável que armazena se houve troca ou não na passagem. Se uma passagem chega ao seu final sem troca a ordenação cessa.

Teste de Mesa

Vetor inicial:

4

2

5

1

Primeira Passagem: compara 4 com 2. 4 maior que 2.Mudam de posição.

2

4

5

1

Segunda Passagem: compara 4 com 5. 4 menor que 5.Permanece.

2

4

5

1

Terceira passagem: compara 5 com 1. 1 menor que 5.Mudam de posição.

2

4

1

5

Quarta passagem: compara 2 com 4. 2 menor que 4.Permanece.

2

4

1

5

Quinta passagem: compara 4 com 1. 1 menor que 4.Mudam de posição.

2

1

4

5

Sexta passagem: compara 4 com 5. 4 menor que 5.Permanece.

2

1

4

5

Sétima passagem: compara 2 com 1. 1 menor que 2.Trocam de posição.

1

2

4

5

Oitava passagem: compara 2 com 4. 2 menor do que 4.Permanece.

1

2

4

5

Nona passagem: compara 4 com 5. 4 menor do que 5. Permanece.

1

2

4

5

Décima passagem: não há mudanças. Sai do laço.

1

2

4

5

Algoritmo Bubble Sort

O algoritmo pode ser descrito em pseudo-código como segue abaixo. V é um VETOR de elementos que podem ser comparados e n é o tamanho desse vetor.

BUBBLESORT (V[], n) 1 houveTroca <- verdade # uma variável de controle

2 enquanto houveTroca for verdade faça

3 houveTroca <- falso

4 para i de 1 até n-1 faça

5 se V[i] vem depois de V[i + 1]

6 então troque V[i] e V[i + 1] de lugar e

7 houveTroca <- verdade

Quicksort (Ordenação Rápida)

O quicksort (Ordenação Rápida) é um método de ordenação baseado no conceito de dividir-e-conquistar. Inicialmente ele seleciona um elemento o qual é chamado de pivô, depois remove este pivô e particiona os elementos restantes em duas sequências, uma com os valores menores do que o pivô e outras com valores maiores.

Exemplo de código na linguagem C:

void quickSort( int a[ ], int l, int r)

{

    int j, i;

    if( l < r )

    {

        j = partition(a, l, r);

        for(i = 0; i < r; ++i)

            printf(" %d ", a[i]);

        printf("\n");

        quickSort(a, l, j-1);

        quickSort(a, j+1, r);

    }

}

int partition( int a[], int l, int r)

{

    int pivo, i, j, t;   

    pivo = a[l];   

    i = l; j = r+1;   

    while(1)

    {       

    do ++i;

    while( a[i] <= pivo && i <= r );       

    do --j; while( a[j] > pivo );       

    if( i >= j ) break;       

    // troca os elementos.       

    t = a[i]; a[i] = a[j];

    a[j] = t;   

    }   

    t = a[l];

    a[l] = a[j];

    a[j] = t;

    return j;

}

Resumo

• Algoritmo de ordenação é uma implementação em uma linguagem de programação para ordenar um conjunto de dados.

• Existem diversos tipos de algoritmos de ordenação. Os principais são Selection Sort, Bubble Sort e Quicksort.

Ligações externas

• Sorting Algorithm na Wikipédia em inglês