O n MC448 — An´alise de Algoritmos I onde n A a ser ...rdahab/cursos/mc458/2013-1s/Welcome_files/4up... · Counting Sort suponha que o vetor A a ser ordenado contenha n n´umeros

MC448 — Analise de Algoritmos I

Cid Carvalho de Souza e Candida Nunes da Silva

1 de Maio de 2006

Cid Carvalho de Souza e Candida Nunes da Silva MC448 — Analise de Algoritmos I

Algoritmos lineares para ordenacao

Os seguintes algoritmos de ordenacao tem complexidade O(n),onde n e o tamanho do vetor A a ser ordenado:




Counting Sort: Elementos sao numeros inteiros “pequenos”;mais precisamente, inteiros x onde x ! O(n).





Radix Sort: Elementos sao numeros inteiros de comprimentomaximo constante, isto e, independente de n.





Radix Sort: Elementos sao numeros inteiros de comprimentomaximo constante, isto e, independente de n.

Bucket Sort: Elementos sao numeros reais uniformementedistribuıdos no intervalo [0..1).


Counting Sort


Counting Sort

suponha que o vetor A a ser ordenado contenha n numerosinteiros, todos menores ou iguais a k, onde k ! O(n).


Counting Sort


o algoritmo a seguir ordena os n numeros em tempoO(n + k); isto e O(n).


Counting Sort



o algoritmo usa dois vetores auxiliares:


Counting Sort



o algoritmo usa dois vetores auxiliares:1 C de tamanho k que guarda em C [i ] o numero de ocorrencias

de elementos ! i em A.


Counting Sort



o algoritmo usa dois vetores auxiliares:1 C de tamanho k que guarda em C [i ] o numero de ocorrencias

de elementos ! i em A.2 B de tamanho n onde se constroi o vetor ordenado.


Counting Sort - Algoritmo

CountingSort(A, k)

! Entrada: - Vetor A de tamanho n

- o valor k do maior inteiro em A

! Saida: O vetor A em ordem crescente1. para i := 1 ate k facaC [i ] := 02. para j := 1 ate n facaC [A[j]] := C [A[j]] + 13. para i := 2 ate k facaC [i ] := C [i ] + C [i " 1]4. para j := n ate 1 faca5. B [C [A[j]]] := A[j]6. C [A[j]] := C [A[j]] " 17 retorne(B)


Counting Sort - Complexidade



O algoritmo nao faz comparacoes entre elementos de A.




Sua complexidade deve ser medida em funcao do numero dasoutras operacoes, aritmeticas, atribuicoes, etc.





Claramente, o numero de tais operacoes e uma funcao emO(n + k), ja que temos dois loops simples com n iteracoes edois com k iteracoes.






Assim, quando k ! O(n), este algoritmo tem complexidadeO(n).






Assim, quando k ! O(n), este algoritmo tem complexidadeO(n).

Algo de errado com o limite inferior de !(n log n) para ordenacao ?


Algoritmos in-place e estaveis



Algoritmos de ordenacao podem ser ou nao in-place ouestaveis.




Um algoritmo de ordenacao e in-place se a memoria adicionalrequerida e independente do tamanho do vetor que esta sendoordenado.





Exemplos: o Quicksort e o Heapsort sao metodos deordenacao in-place, ja o Mergesort e o Counting Sort nao.






Um metodo de ordenacao e estavel se elementos iguaisocorrem no vetor ordenado na mesma ordem em que saopassados na entrada.






Um metodo de ordenacao e estavel se elementos iguaisocorrem no vetor ordenado na mesma ordem em que saopassados na entrada.

Exemplos: o Counting Sort e o Quicksort sao exemplos demetodos estaveis (desde que certos cuidados sejam tomadosna implementacao). O Heapsort nao e.


O Radix Sort


O Radix Sort

O algoritmo Radix Sort ordena um vetor A de n numerosinteiros com um numero constante d de dıgitos, atraves deordenacoes parciais dıgito a dıgito.


O Radix Sort


Esse algoritmo surgiu no contexto de ordenacao de cartoesperfurados; a maquina ordenadora so era capaz de ordenar oscartoes segundo um de seus dıgitos.


O Radix Sort



Poderıamos entao ordenar os numeros iniciando a ordenacao apartir do dıgito mais significativo i , mas, para prosseguirassim, terıamos que separar os elementos da entrada emsubconjuntos com o mesmo valor no dıgito i .


O Radix Sort



Poderıamos entao ordenar os numeros iniciando a ordenacao apartir do dıgito mais significativo i , mas, para prosseguirassim, terıamos que separar os elementos da entrada emsubconjuntos com o mesmo valor no dıgito i .

Podemos tambem ordenar os numeros ordenando-os segundocada um de seus digitos, comecando pelo menos significativo.Assim e o algoritmo Radix Sort.


O Radix Sort

Suponha que os elementos do vetor A a ser ordenado sejamnumeros inteiros de ate d dıgitos. O Radix Sort e simplesmente:


O Radix Sort

Suponha que os elementos do vetor A a ser ordenado sejamnumeros inteiros de ate d dıgitos. O Radix Sort e simplesmente:

RadixSort(A, d)

1. para i := 1 ate d faca2. ordene os elementos de A pelo i -esimo dıgito

usando um metodo estavel


O Radix Sort - Exemplo

329457657839436720355



329457657839436720355

#

720355436457657329839

$



329457657839436720355

#

720355436457657329839

$

#

720329436839355457657$



329457657839436720355

#

720355436457657329839

$

#

720329436839355457657$

#

329355436457657720839$


O Radix Sort - Corretude

O seguinte argumento indutivo garante a corretude do algoritmo:




Sabemos, por hipotese de inducao, que os numeros estaoordenados com relacao aos i " 1 dıgitos menos significativos.




Sabemos, por hipotese de inducao, que os numeros estaoordenados com relacao aos i " 1 dıgitos menos significativos.

Ordenando os numeros com relacao ao i -esimo dıgito, via umalgoritmo estavel, teremos entao os numeros ordenados comrelacao aos i dıgitos menos significativos, pois, para doisnumeros com o i -esimo dıgito distintos, o de menor valor nodıgito estara antes do de maior valor, e se ambos possuem oi -esimo dıgito igual, entao a ordem dos dois tambem estaracorreta pois utilizamos um metodo de ordenacao estavel e,por hipotese de inducao, os dois elementos ja estavamordenados segundo os i " 1 dıgitos menos significativos.


O Radix Sort - Complexidade



A complexidade do Radix Sort depende da complexidade doalgoritmo estavel usado para ordenar cada dıgito doselementos.




Se essa complexidade estiver em "(f (n)), obtemos umacomplexidade total de "(d f (n)) para o Radix Sort.





Como supomos d constante, a complexidade reduz-se para"(f (n)).






Se o algoritmo estavel for, por exemplo, o Counting Sort,obtemos a complexidade "(n + k).






Se o algoritmo estavel for, por exemplo, o Counting Sort,obtemos a complexidade "(n + k).

Supondo k ! O(n), resulta numa complexidade linear em n.

E o limite inferior de !(n log n) para ordenacao ?





Em contraste, um algoritmo por comparacao como oMergeSort teria complexidade n log n.




Assim, o Radix Sort e mais vantajoso que o MergeSort quandod < log n, ou seja, o numero de dıgitos for menor que log n.





Se considerarmos que n tambem e um limite superior para omaior valor a ser ordenado, entao O(log n) e uma estimativapara o tamanho, em dıgitos, desse numero.





Se considerarmos que n tambem e um limite superior para omaior valor a ser ordenado, entao O(log n) e uma estimativapara o tamanho, em dıgitos, desse numero.

Isso significa que nao ha diferenca significativa entre odesempenho do MergeSort e do Radix Sort?





A vantagem de se usar o Radix Sort fica evidente quandointerpretamos os dıgitos de forma mais geral que simplesmente0..9, embora seja esse o significado literal de “dıgitos”.




Tomemos o seguinte exemplo: suponha que desejemosordenar um conjunto de 220 numeros de 64 bits. Entao, oMergeSort faria cerca de 20 % 220 comparacoes e usaria umvetor auxiliar de tamanho 220.




Tomemos o seguinte exemplo: suponha que desejemosordenar um conjunto de 220 numeros de 64 bits. Entao, oMergeSort faria cerca de 20 % 220 comparacoes e usaria umvetor auxiliar de tamanho 220.

Se interpretarmos cada numero do conjunto como tendo 4dıgitos em base 216, e usarmos o Radix Sort com o Counting

Sort como metodo estavel, a complexidade de tempo seria daordem de 4(220 + 216) operacoes, uma reducao substancial.Mas, note que utilizamos dois vetores auxiliares, um detamanho 216 e outro de tamanho 220.





O nome Radix Sort vem da base (em ingles radix) em queintepretamos os dıgitos.




Veja que se o uso de memoria auxiliar for muito limitado,entao o melhor mesmo e usar um algoritmo de ordenacao porcomparacao in-place.




Veja que se o uso de memoria auxiliar for muito limitado,entao o melhor mesmo e usar um algoritmo de ordenacao porcomparacao in-place.

Note que e possıvel usar o Radix Sort para ordenar outrostipos de elementos, como datas, palavras em ordemlexicografica e qualquer outro tipo que possa ser visto comouma d-upla ordenada de itens comparaveis.


O Bucket Sort


O Bucket Sort

Assim como o Counting Sort, supoe que os n elementos aserem ordenados tem uma natureza peculiar. Neste caso, oselementos estao distribuıdos uniformemente no intervalosemi-aberto [0, 1).


O Bucket Sort


A ideia e dividir o intervalo [0, 1) em n segmentos de mesmotamanho (buckets) e distribuir os n elementos nos seusrespectivos segmentos. Como os elementos estao distribuıdosuniformemente, espera-se que o numero de elementos sejaaproximadamente o mesmo em todos os segmentos.


O Bucket Sort


A ideia e dividir o intervalo [0, 1) em n segmentos de mesmotamanho (buckets) e distribuir os n elementos nos seusrespectivos segmentos. Como os elementos estao distribuıdosuniformemente, espera-se que o numero de elementos sejaaproximadamente o mesmo em todos os segmentos.

Em seguida, os elementos de cada segmento sao ordenadospor um metodo qualquer. Finalmente, os segmentosordenados sao concatenados em ordem crescente.


O Bucket Sort - codigo

BucketSort(A)

1. n := comprimento de A

2. para i := 1 ate n faca3. insira A[i ] na lista ligada B [&nA[i ]']4. para i := 0 ate n " 1 faca5. ordene a lista B [i ] com Insertion Sort

6. Concatene as listas B [0],B [1], . . . ,B [n " 1] nessa ordem.


Bucket Sort - Exemplo

A =

1 .782 .173 .394 .265 .726 .947 .218 .129 .2310 .68


Bucket Sort - Exemplo

A =

1 .782 .173 .394 .265 .726 .947 .218 .129 .2310 .68

B =

01 .12, .172 .21, .23, .263 .39456 .687 .72, .7889 .94


O Bucket Sort - corretude



A corretude do algoritmo depende do fato de que elementos x

e y de A, x < y , ou terminem no mesmo segmento ou sejamdestinados a segmentos diferentes B [i ] e B [j],respectivamente, onde i < j .





A primeira possibilidade implica que x aparecera antes de y

na concatenacao final, ja que cada segmento e ordenado.





A primeira possibilidade implica que x aparecera antes de y

na concatenacao final, ja que cada segmento e ordenado.

Na segunda hipotese, temos que, se x < y , entaoi = &nx' ( &ny' = j . Como i )= j , temos i < j .


O Bucket Sort - complexidade



E claro que o pior caso do Bucket Sort e quadratico,supondo-se que as ordenacoes dos segmentos seja feita comordenacao por insercao.




Entretanto, o tempo esperado e linear.




Entretanto, o tempo esperado e linear.Intuitivamente, a ideia da demonstracao e que, como os n

elementos estao distribuıdos uniformemente no intervalo[0, 1), entao o tamanho esperado das listas tambem euniforme, em "(1).






Portanto as ordenacoes das n listas B [i ] leva tempo totalesperado em "(n).






Portanto as ordenacoes das n listas B [i ] leva tempo totalesperado em "(n).

Os detalhes podem ser vistos no livro de Cormen, Leiserson eRivest.


Documents

O n MC448 — An´alise de Algoritmos I onde n A a ser ...rdahab/cursos/mc458/2013-1s/Welcome_files/4up... · Counting Sort suponha que o vetor A a ser ordenado contenha n n´umeros