Análise e Projeto de Algoritmos -...

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

Karina Mochetti

2018.2

Karina Mochetti Aula 10. Ordenação Linear

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

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

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

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

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

Counting Sort

Percorre o vetor contando o número de elementos.

Karina Mochetti Aula 10. Ordenação Linear

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

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

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

Radix Sort

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

Karina Mochetti Aula 10. Ordenação Linear

Radix Sort

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

Karina Mochetti Aula 10. Ordenação Linear

Radix Sort

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

Karina Mochetti Aula 10. Ordenação Linear

Radix Sort

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

Karina Mochetti Aula 10. Ordenação Linear

Radix Sort

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

Karina Mochetti Aula 10. Ordenação Linear

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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