UNICAMP – Universidade Estadual de Campinas

IC – Instituto de Computação

 

Disciplina: MO417 – Complexidade de Algoritmos I

Professor: João Meidanis

 

 

Ata de Aula

 

 

Assunto: Ordenação em Tempo Linear

Capítulo do Livro Texto Adotado (*): Capítulo 8

Data da Aula: 19/03/2003

Data de Entrega da Ata: 24/03/2003

Redator: Marcelo Fantinato

 

* Livro Texto adotado: Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática. 2002.

 

 

 


Tópicos desta Ata:

1)     Introdução

2)     Limites Inferiores para Ordenação por Comparação

2.1)           O Modelo de Árvore de Decisão

2.2)           Limite Inferior no Tempo de Execução para o Pior Caso

3)     Algoritmos de Ordenação em Tempo Linear

3.1)           Ordenação por Contagem (Counting Sort)

3.2)           Ordenação da Raiz (Radix Sort)

3.3)           Ordenação por Balde (Bucket Sort)

4)     Conclusão

 

 

 

 

1)    Introdução

 

Este capítulo aborda três algoritmos de ordenação que são executados em tempo linear, ou seja, que ordenam n números no tempo Theta(n).

 

Primeiramente é apresentado um limite inferior para os algoritmos de ordenação por comparação que prova que nenhum deles pode ser executado em tempo linear. Depois são apresentados então algoritmos de ordenação que não são por comparação que o podem ser.

 

 

2)    Limites Inferiores para Ordenação por Comparação

 

Todos os algoritmos de ordenação por comparação possuem a seguinte propriedade:

“a seqüência ordenada que eles determinam se baseia apenas em comparações entre elementos de entrada”.

 

Por esses algoritmos de ordenação por comparação possuírem essa propriedade em comum, é possível definir um limite inferior que seja comum a todos eles. Esse limite é definido com base no conceito de árvore de decisão.

 

 

2.1)      Árvores de Decisão

 

Uma árvore de decisão representa as comparações executadas por um algoritmo de ordenação quando ele opera sobre uma entrada de um tamanho dado. Assim, uma árvore de decisão permite a visualização de ordenações por comparação de modo abstrato.

 

Uma árvore de decisão possui as seguintes propriedades:

·          Árvore Binária;

·          Árvore possui no mínimo n! folhas (para n igual ao número de elementos do array a ser ordenado);

·          Cada folha contém uma permutação dos dados de entrada.

 

O comprimento do maior caminho da árvore (da raiz até uma folha) é utilizado para chegar a um limite inferior, conforme desejado (o caminho mais longo da árvore representa o pior caso do algoritmo).

 

Dica do professor:

 

Dado um algoritmo de ordenação por comparação, é sempre possível construir sua árvore de decisão a partir do seguinte procedimento:

-          Fixar o n;

-          Verificar qual é a primeira comparação do algoritmo, a qual pode resultar em Sim ou Não. Neste passo, é necessário saber quais são os índices que estão sendo comparados;

-          A primeira comparação é colocada como a raiz da árvore, incluindo os arcos Sim e Não;

-          Continuar esse procedimento para cada nó da árvore. Em cada próxima comparação, é necessário saber quais são os índices que estão sendo comparados.

 

Deve se analisar sempre o índice original, ou seja, não devem ser consideradas as trocas de índices ocorridas durante o processo.

 

Se o algoritmo de ordenação por comparação estiver correto, para cada entrada chega-se em uma folha (que é uma permutação da entrada).

 

Questionamento de Aluno:

 

Foi questionado se existe apenas uma árvore de decisão para todos os algoritmos de ordenação por comparação ou se deve existir uma árvore de decisão para cada algoritmo.

 

A turma concluiu que existe um sentimento geral de que a árvore de decisão depende do algoritmo, devendo então existir uma árvore de decisão para cada algoritmo. Embora a árvore possua sempre as mesmas propriedades (como ser binária e possuir no mínimo n! folhas), a árvore para algoritmos diferentes pode ser diferente tendo, por exemplo, topologias e elementos diferentes.

 

 

2.2)      Limite Inferior no Tempo de Execução para o Pior Caso

 

É provado que qualquer algoritmo de ordenação por comparação exige Ômega(n * lg n) comparações no pior caso. Ou seja, qualquer um desses algoritmos realiza no mínimo n * lg n comparações para chegar no resultado final. Portanto, nunca um algoritmo de ordenação por comparação terá um tempo de execução para o pior caso igual a n.

 

Questionamento de Aluno:

 

Foi questionado por que foi usado no livro o Insertion Sort, que possui tempo de execução quadrático no pior caso – Theta(n2), se o intuito é chegar em um resultado geral para todos os algoritmos de ordenação por comparação.

 

O professor disse que o Insertion Sort foi usado apenas como um exemplo de árvore de decisão. Ele foi usado por ser o mais fácil, visto que ele não faz tantas trocas. Entretanto, a regra é geral e vale para qualquer algoritmo de ordenação por comparação.

 

Questionamento de Aluno:

 

Foi questionado que parece ser muito difícil montar a árvore para outros algoritmos além do Insertion Sort, como – por exemplo – o Quick Sort.

 

O professor disse que é difícil mesmo. Mas as árvores de decisão para algoritmos de ordenação por comparação são usadas apenas para provar teoremas na teoria e não são muito usadas na prática. Para se ter uma idéia, no caso de uma árvore com n elementos, deve existir no mínimo n! elementos folha, o que é inviável de se construir.

 

 

3)    Algoritmos de Ordenação em Tempo Linear

 

 

3.1)      Ordenação por Contagem (Counting Sort)

 

A ordenação por Contagem pressupõe que cada um dos n elementos de entrada é um inteiro no intervalo de 1 a k, para algum inteiro k. Assim, por exemplo, pode-se ordenar 50 números que variam de 1 a 15, com k = 15.

 

Exemplos de k:

 

-          ao ordenar idades, k poderia ser igual a 100 ou igual a 200;

-          ao ordenar RAs, k poderia ser igual a 999999;

-          ao ordenar RGs, k poderia ser igual a 99999999.

 

Idéia Básica do Algoritmo:

·          Determinar, para cada elemento de entrada x, o número de elementos menores que x;

·          Usar essa informação para inserir o elemento x diretamente em sua posição no arranjo de saída.

 

Exemplo Simples (sem considerar que pode haver vários elementos com o mesmo valor):

     Se existem 17 elementos menores que x, então x é colocado na posição de saída 18.

 

Características do algoritmo de ordenação por contagem apresentado no livro:

·          O algoritmo não usa comparações, mas utiliza dupla indexação;

·          A ordenação não é feira localmente, ou seja, o algoritmo exige um espaço de armazenamento de trabalho temporário;

·          Não é um algoritmo recursivo;

·          As estruturas de repetição são todos do tipo for (existem quatro for no algoritmo);

·          O algoritmo é estável;

·          O tempo de execução é fornecido em função do valor de k.

 

Tempo de execução do algoritmo ordenação por contagem: Theta(k + n).

Tempo de execução do algoritmo ordenação por contagem quando k = O(n):Theta(n).

 

Importância da propriedade de estabilidade de um algoritmo:

 

Um algoritmo é estável quando números com o mesmo valor aparecem no arranjo de saída na mesma ordem em que se encontram no arranjo de entrada.

 

Essa propriedade é importante quando os dados satélites que acompanham os elementos sendo ordenado devem ser transportados juntamente com o elemento.

 

O algoritmo de ordenação por contagem é estável já que ele faz a leitura no array intermediário de trás para frente na hora de criar o vetor resultante. Mas é a manutenção desta estabilidade que obriga que o algoritmo utilize um array auxiliar. Se a propriedade de estabilidade não precisasse ser mantida, o algoritmo já poderia ir trabalhando no próprio array inicial, usando menos memória.

 

Errata:

 

Algoritmo COUNTING-SORT (página 136)

 

Linha 6 – o correto é:

     for i ← 1 to k

 

Dúvida Levantada (Está certo ou errado no livro):

 

Parágrafo 4, página 137. A seguinte frase parece estar sem sentido:

 

“Ou seja, os vínculos entre dois números são rompidos pela regra de que qualquer número que aparecer primeiro no arranjo de entrada aparecerá primeiro no arranjo de saída”

 

Esta dúvida não foi muito discutida e assim a turma não chegou a uma conclusão sobre isso.

Nota do instrutor: consultando o original em inglês verificamos que a frase original é: "That is, ties between numbers are broken by the rule that whichever number appears first in the input array appears first in the output array", cuja tradução seria algo como: "Ou seja, empates entre números são resolvidos pela regra de que o número que aparece primeiro no vetor de entrada aparece primeiro no vetor de saída". Aparentemente o(a) tradutor(a) se confundiu, interpretando o verbo "to break ties" do inglês como "romper vínculos" ao invés do correto aqui que seria "resolver empates".

 

 

3.2)      Ordenação da Raiz (Radix Sort)

 

O algoritmo radix sort ordena os elementos de um array em função dos valores contidos em cada um de seus dígitos.

 

Este algoritmo ordena n elementos de um array A, que possuem d dígitos cada um, onde o dígito 1 é o dígito de mais baixa ordem e o dígito d é o dígito de mais alta ordem.

 

Idéia Básica do Algoritmo:

·          Para i de 1 a d, ordenar os elementos de A sobre o dígito i, através de um algoritmo de ordenação estável.

 

Tempo de execução do algoritmo radix sort:

·          Dados n números de d dígitos em que cada dígito pode assumir até k valores possíveis, radix sort ordena corretamente esses números no tempo Theta(d(n + k));

·          Dados n números de b bits e qualquer inteiro positivo r <= b, radix sort ordena corretamente esses números no tempo Theta((b/r)(n + 2r)).

 

Dependendo da escolha de k ou b e r, o resultado final para o tempo de execução do radix sort pode ser Theta(n).

 

Quando é preferível usar o radix sort ou um outro algoritmo como o quick sort?

 

Determinar o algoritmo de ordenação preferível depende das características das implementações, da máquina subjacente e dos dados de entrada e da importância de espaço de armazenamento da memória primária.

 

 

3.3)      Ordenação por Balde (Bucket Sort)

 

O algoritmo bucket sort pressupõe que a entrada possui uma distribuição uniforme dos dados. Além disso, os dados devem pertencer ao intervalo [0, 1).

 

Idéia Básica do Algoritmo:

·          Primeiramente, dividir o intervalo [0, 1) em n subintervalos de igual tamanho (chamados de baldes);

·          Depois, distribuir os n números de entrada entre os baldes;

·          Depois, ordenam-se os números em cada balde – usando algum outro algoritmo de ordenação qualquer;

·          Por último, percorrem-se os baldes em ordem, listando os elementos contidos em cada um.

 

Através deste procedimento, espera-se que muitos números não caiam em cada balde – devido à distribuição realizada de forma uniforme. Na realidade, espera-se que cada número caia em um balde diferente.

 

Tempo de execução do algoritmo bucket sort (encontrada usando linearidade de expectativa):

·          Theta(n) + n*O(2 – 1/n) = Theta(n).

 

Análise do pior caso:

·          Se todos os números caíssem num balde só: o tempo de execução seria igual ao do algoritmo usado na ordenação dos números existentes em cada balde.

 

Questão Levantada pelo Professor:

 

Só é possível ordenar números de 0 a 1? E se fossem números de 0 a 10, seria possível?

 

Foi sugerido por um aluno que no caso de números de 0 a 10, poderia simplesmente dividir todos os números por 10, ordená-los e depois multiplicá-los por 10 novamente.

 

 

4)    Conclusões

 

Nesta aula foram apresentados três algoritmos de ordenação que são executados em tempo linear, ou seja, que ordenam n números no tempo Theta(n). Portanto, todos esses três algoritmos de ordenação superam o limite inferior encontrado no tempo de execução para o pior caso dos algoritmos de ordenação por comparação que é de Ômega(n * lg n).

 

Apesar disso, nem sempre é mais vantajoso ou viável usar um desses 3 algoritmos por serem mais eficientes em relação ao tempo de execução. Isso porque cada um desses três algoritmos pressupõe algo sobre os dados contidos no array de entrada. Assim, eles não podem ser aplicados com esse tempo de execução linear para qualquer caso de ordenação. Além disso, deve-se ainda avaliar a necessidade ou não de uma ordenação estável e de uma ordenação local. Cada um dos algoritmos de ordenação visto até esta aula possui vantagens e desvantagens dependendo de algumas condições.