67
Análise e Projeto de Algoritmos Aula 10. Ordenação Linear Karina Mochetti 2018.2 Karina Mochetti Aula 10. Ordenação Linear

Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Embed Size (px)

Citation preview

Page 1: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Análise e Projeto de AlgoritmosAula 10. Ordenação Linear

Karina Mochetti

2018.2

Karina Mochetti Aula 10. Ordenação Linear

Page 2: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Resumo Ordenação por Comparação

O limite inferior da ordenação por comparação é O(n log n).

Algoritmo Melhor Caso Pior Caso Caso Médio In Place EstávelInsertion Sort O(n) O(n2) O(n2) Sim SimSelection Sort O(n2) O(n2) O(n2) Sim Não

HeapSort O(n log n) O(n log n) O(n log n) Sim NãoMergeSort O(n log n) O(n log n) O(n log n) Não SimQuickSort O(n log n) O(n2) O(n log n) Não Não

Karina Mochetti Aula 10. Ordenação Linear

Page 3: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Linear Sort

São algoritmos que não utilizam somente comparações durante aordenação. Assim, com um custo a mais em outras operações oucom restrições sobre o vetor, eles são lineares no número decomparações e atribuições.

Karina Mochetti Aula 10. Ordenação Linear

Page 4: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos menores que x .

Sabendo que os valores do vetor vão de 0 a k .Crie um vetor de k elementos.Percorra o vetor contando cada elemento.O vetor final terá o número de elementos menores que x edará a ordem dos elementos do vetor original.

Karina Mochetti Aula 10. Ordenação Linear

Page 5: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Counting Sort(A) {for (i=0; i <= k; i++) C[i] = 0;for (j=0; j < n; j++) C[A[j]] += 1;for (i=1; i <= k; i++) C[i] += C[i-1];for (j=n-1; j >= 0; j--) {

B[C[A[j]]] = A[j];C[A[j]]--;

}return B;

}

Karina Mochetti Aula 10. Ordenação Linear

Page 6: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 7: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 8: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 9: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 10: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 11: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 12: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 13: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 14: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 15: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 16: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 17: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 18: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 19: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 20: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 21: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 22: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 23: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 24: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 25: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 26: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 27: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 28: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 29: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 30: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 31: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 32: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 33: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 34: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 35: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 36: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 37: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 38: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 39: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Page 40: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Counting Sort

Percorre o vetor contando o número de elementos.

A complexidade do Counting Sort é O(k + n). Assim, se ovalor de k for O(n), o algoritmo será linear.É preciso saber os valores máximo e mínimos existentes novetor, e eles precisam caber na memória.Os valores pode ir de k1 a k2, contanto que k2 − k1 seja umnúmero de elementos que caiba na memória.Ele não realiza nenhuma comparação e é estável.

Karina Mochetti Aula 10. Ordenação Linear

Page 41: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Suponha que cada número tenha no máximo d dígitosPara cada dígito utiliza um algoritmo linear estável paraordená-losFaça isso do menos significativo para o mais e no fim osnúmeros estarão ordenados

Karina Mochetti Aula 10. Ordenação Linear

Page 42: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Radix Sort(A) {for (i=1; i <= d; i++)A = Counting Sort(A, i);

}

Karina Mochetti Aula 10. Ordenação Linear

Page 43: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Karina Mochetti Aula 10. Ordenação Linear

Page 44: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Karina Mochetti Aula 10. Ordenação Linear

Page 45: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Karina Mochetti Aula 10. Ordenação Linear

Page 46: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Karina Mochetti Aula 10. Ordenação Linear

Page 47: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Karina Mochetti Aula 10. Ordenação Linear

Page 48: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Radix Sort

Ordena os elementos pelo número menos significativo com umalgoritmo auxiliar estável.

Suponha que cada elemento tenha d dígitos e seja descrito nabase k

Usando um algoritmo linear como o Counting Sort, temos quea complexidade do Radix Sort será O(d(n + k)). Se d forconstante k = O(n), então o Radix Sort é linear, isto é, O(n).Para cada passo precisamos calcular cada dígito de cadanúmero. Dependendo de como o input estiver, isso podeacarretar em mais custo.

Karina Mochetti Aula 10. Ordenação Linear

Page 49: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Sabendo que os valores do vetor vão de 0 a 99.Separe cada elemento por decimais [0, 9], [10, 19] ... [90, 99]Ordene cada sub-vetor de forma linear.Crie o vetor final unindo cada sub-vetor.

Karina Mochetti Aula 10. Ordenação Linear

Page 50: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Bucket Sort(A) {for (i=0; i < k; i++)

B[i] = vazio;for (i=0; i < n; i++)

insere A[i] em B[A[i] / k];for (i=0; i < k; i++)

ordene B[i] com insertionSort();contate B[0], B[1], ..., B[k-1] em Breturn B;

}

Karina Mochetti Aula 10. Ordenação Linear

Page 51: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 52: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 53: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 54: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 55: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 56: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 57: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 58: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 59: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 60: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 61: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 62: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Karina Mochetti Aula 10. Ordenação Linear

Page 63: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Bucket Sort

Divide o vetor em intervalos menores, separa os valores por essesintervalos e usa um algoritmo linear para ordená-los.

Assume que os elementos estão dentro de determinadointervalo e que estão bem distribuídos dentro desse intervalo.Se existem k buckets, então chamaremos o insertionSort() kvezes para lista com aproximadamente n/k elementos.Para k = O(n), temos: kO(n2/k2) = O(n), com uma entradadistribuída uniformemente.

Karina Mochetti Aula 10. Ordenação Linear

Page 64: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Exercício

Mostre cada passo da ordenação do seguinte vetor por CountingSort.

42, 4, 8, 42, 42, 23, 15, 16 15, 8, 4, 4, 23, 23, 23, 42, 16, 23, 4, 8

Mostre cada passo da ordenação do seguinte vetor por Radix Sort.

421, 150, 160, 235, 400, 801, 042, 015, 016, 023, 004, 008, 402

Mostre cada passo da ordenação do seguinte vetor por Bucket Sort.

42, 15, 16, 23, 4, 8, 78, 37, 33, 29, 90, 66, 44, 50, 57, 99

Karina Mochetti Aula 10. Ordenação Linear

Page 65: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Exercício: Solução

Mostre cada passo da ordenação do seguinte vetor por CountingSort.

42, 4, 8, 42, 42, 23, 15, 16, 15, 8, 4, 4, 23, 23, 23, 42, 16, 23, 4, 8

04 -> 4 -> 408 -> 3 -> 715 -> 2 -> 916 -> 2 -> 1123 -> 5 -> 1642 -> 4 -> 20

4, 4, 4, 4, 8, 8, 8, 15, 15, 16, 16, 23, 23, 23, 23, 23, 42, 42, 42, 42

Karina Mochetti Aula 10. Ordenação Linear

Page 66: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Exercício: Solução

Mostre cada passo da ordenação do seguinte vetor por Radix Sort.

421, 150, 160, 235, 400, 801, 042, 015, 016, 023, 004, 008, 402

421 150 400 004150 160 801 008160 400 402 015235 421 004 016400 801 008 023801 042 015 042042 402 016 150015 023 421 160016 004 023 235023 235 235 400004 015 042 402008 016 150 421402 008 160 801

004, 008, 015, 016, 023, 042, 150, 160, 235, 400, 402, 421, 801Karina Mochetti Aula 10. Ordenação Linear

Page 67: Análise e Projeto de Algoritmos - ic.uff.brkmochetti/MaterialDidatico/tradicionais/05/files/aula10.pdf · Bucket Sort Divideovetoremintervalosmenores,separaosvaloresporesses intervaloseusaumalgoritmolinearparaordená-los

Exercício: Solução

Mostre cada passo da ordenação do seguinte vetor por Bucket Sort.

42, 15, 16, 23, 4, 8, 78, 37, 33, 29, 90, 66, 44, 50, 57, 99

00-09 -> 4, 810-19 -> 15, 1620-29 -> 23, 2930-39 -> 33, 3740-49 -> 42, 4450-59 -> 50, 5760-69 -> 6670-79 -> 7880-89 ->90-99 -> 90, 99

4, 8, 15, 16, 23, 29, 33, 37, 42, 44, 50, 57, 66, 78, 90, 99

Karina Mochetti Aula 10. Ordenação Linear