ORDENAÇÃO EM TEMPO LINEAR. Ordenação em Tempo Linear Algoritmos de ordenação por comparação: InsertSort; Quicksort; MergeSort; Heapsort... Possuem limite

  • Published on
    07-Apr-2016

  • View
    220

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>ORDENAO EM TEMPO LINEAR</p></li><li><p>Ordenao em Tempo LinearAlgoritmos de ordenao por comparao:InsertSort;Quicksort;MergeSort;Heapsort...</p><p>Possuem limite assinttico inferior: O(n lg n);</p><p>Podem existir algoritmos melhores?</p></li><li><p>Ordenao em Tempo LinearA resposta SIM, desde que:A entrada possua caractersticas especiais;Algumas restries sejam respeitadas;O algoritmo no seja puramente baseado em comparaes;A implementao seja feita da maneira adequada.Tempo linear: (n);Algoritmos:Ordenao por contagem (Counting sort);Radix sort;Bucket sort.</p></li><li><p>ORDENAO POR CONTAGEMCounting Sort</p></li><li><p>COUNTING SORTAspectos Positivos:Ordena vetores em tempo linear para o tamanho do vetor inicial;No realiza comparaes; um algoritmo de ordenao estvel;Aspecto Negativo:Necessita de dois vetores adicionais para sua execuo, utilizando, assim, mais espao na memria. </p></li><li><p>COUNTING SORTFuncionamento:</p><p>A ordenao por contagem pressupe que cada um dos n elementos do vetor de entrada um inteiro entre 1 e k (k representa o maior inteiro presente no vetor).</p><p>A ideia bsica determinar, para cada elemento de entrada x, o numero de elementos menores ou iguais a x. Com essa informao possvel determinar exatamente onde o elemento x ser inserido.</p></li><li><p>EXEMPLO Na lista A acima o elemento circulado 7 possui 5 elementos menores que ele. Dessa forma o elemento 7 dever ser inserido no ndice 6 (5 + 1) do vetor de sada B.592072895A = 7B = 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9</p></li><li><p>SIMULAO - COUNTING SORTO algoritmo recebe um vetor desordenado como entrada:Em seguida, gera os vetores adicionais B e C: O vetor B do mesmo tamanho do vetor A (8 elementos). O vetor C do tamanho do maior elemento de A + 1 (5 + 1 = 6).</p></li><li><p>SIMULAO - COUNTING SORTSe o valor de um elemento de entrada i, incrementamos C[i]:C[i] contm um nmero de elementos de entrada igual a i paracada i = 0,1,2,...,k.Agora fazemos C[i] = C[i] + C[i-1] para determinarmos quantoselementos de entrada so menores que ou iguais a i:</p></li><li><p>SIMULAO - COUNTING SORTAgora, partindo do maior para o menor ndice, fazemosB[C[A[j]]] = A[j]. Assim, colocamos cada elemento A[j] em suaPosio ordenada no vetor B:</p><p>Para j = 8B[C[A[8]]] B[C[3]] B[7]B[7] = A[8] B[7] = 3Exemplo:</p></li><li><p>SIMULAO - COUNTING SORTEm seguida decrementamos o valor de C[A[j]] toda vez que Inserimos um valor no vetor B. isso faz com que o prximoelemento de entrada com valor igual a A[j], se existir, v paraa posio imediatamente anterior a A[j] no vetor B. C[3] = C[3] 1:</p></li><li><p>SIMULAO - COUNTING SORTAps as iteraes de (comprimento de [A] at 1) temos o vetor desada B ordenado!!!</p></li><li><p>ALGORITMO COUNTING SORT01CountingSort(A, B, k) {02for I0 to k03 do C[i] 004for j1 to comprimento [A]05 do C[A[j]] C[A[j]] + 106for I2 to k07 do C[i] = C[i] + C[i-1]08for j comprimento [A] downto 109 do B[C[A[j]]] = A[j]10C[A[j]] = C[A[j]] - 111}</p></li><li>COUNTING SORT IN Cvoid coutingSort(int *A, int n, int *B, int *C, int k){ int i; // Passo 1 - Contagem do nmero de cada elemento do intervalofor(i=0; i</li><li><p>ORDENAO RADIXSORT</p></li><li><p>INTRODUO</p></li><li><p>Radixsort</p></li><li><p>ExercciosImplementar os algoritmos RadixSort e CountSort realizando experimentos que avaliem a quantidade de operaes (comparaes) e o tempo de execuo para: vetores com 1.000, 10.000, 100.000 e um milho de nmeros inteiros entre 0 e 99.999. Os nmeros inteiros sero gerados aleatoriamente.</p></li></ul>