Neste artigo, discutiremos propriedades importantes de diferentes técnicas de classificação, incluindo a sua complexidade, estabilidade e restrições de memória. Antes de entender este artigo, você deve entender o básico de diferentes técnicas de classificação (Veja : Técnicas de classificação).
Análise de complexidade temporal –
Discutimos a melhor, média e pior caso de complexidade de diferentes técnicas de classificação com cenários possíveis.
Seleção baseada em comparação –
Na classificação baseada em comparação, elementos de um array são comparados entre si para encontrar o array ordenado.
- Seleção de Bolhas e Inserção –
Complexidade média e pior caso: n^2
Complexidade do melhor caso: n quando o array já está ordenado.
Pior caso: quando o array está em ordem inversa. - Seleção de ordenação –
Complexidade dos melhores, médios e piores casos: n^2 que é independente da distribuição dos dados. - Merge sort –
Complexidade dos melhores, médios e piores casos: nlogn que é independente da distribuição dos dados. - Heap sort –
Complexidade dos melhores, médios e piores casos: nlogn que é independente da distribuição dos dados. - Ordenação rápida –
É uma abordagem de divisão e conquista com relação de recorrência:T(n) = T(k) + T(n-k-1) + cn
Pior caso: quando o array é ordenado ou ordenado inverso, o algoritmo de partição divide o array em duas subarrays com elementos 0 e n-1. Portanto,
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Best case e Average case: Em uma média, o algoritmo de partição divide o array em dois subarrays com o mesmo tamanho. Portanto,
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Classificação não baseada em comparação –
Na classificação não baseada em comparação, os elementos do array não são comparados uns com os outros para encontrar o array classificado.
- Classificação Radix –
Complexidade de tempo do melhor, médio e pior caso: nk onde k é o número máximo de dígitos em elementos de array. - Classificação de contagem –
Complexidade de tempo do melhor, médio e pior caso: n+k onde k é o tamanho do array de contagem. - Ordenação do balde –
Complexidade do melhor e pior tempo: n+k onde k é o número de baldes.
Pior complexidade de tempo de caixa: n^2 se todos os elementos pertencerem ao mesmo balde.
>
Técnica de ordenação –
Técnica de ordenação está no lugar se não usar nenhuma memória extra para ordenar o array.
Dentre as técnicas baseadas em comparação discutidas, apenas a ordenação por fusão é técnica de outplaced, pois requer um array extra para fundir as subarrays ordenadas.
Dentre as técnicas não baseadas em comparação discutidas, todas são técnicas de outplaced. A ordenação da contagem usa um array de contagem e a ordenação do balde usa uma tabela de hash para ordenar o array.
Técnica Online/Offline –
Uma técnica de ordenação é considerada Online se ela pode aceitar novos dados enquanto o procedimento está em andamento, ou seja, dados completos não são necessários para iniciar a operação de ordenação.
Dentre as técnicas baseadas em comparação discutidas, apenas a Ordenação de Inserção se qualifica para isso por causa do algoritmo subjacente que ela usa, ou seja ele processa o array (não apenas elementos) da esquerda para a direita e se novos elementos são adicionados à direita, ele não tem impacto na operação em andamento.
Técnica estável/instável –
Uma técnica de ordenação é estável se não alterar a ordem dos elementos com o mesmo valor.
Sair de técnicas baseadas em comparação, ordenação de bolhas, ordenação de inserções e ordenação de fusões são técnicas estáveis. A ordenação de seleção é instável, pois pode alterar a ordem dos elementos com o mesmo valor. Por exemplo, considere o array 4, 4, 1, 3.
Na primeira iteração, o elemento mínimo encontrado é 1 e é trocado por 4 na posição 0. Portanto, a ordem de 4 em relação a 4 na 1ª posição irá mudar. Da mesma forma, a classificação rápida e a classificação por pilha também são instáveis.
Sair de técnicas não baseadas em comparação, a classificação por contagem e a classificação por balde são técnicas de classificação estáveis, enquanto a estabilidade da classificação por radix depende do algoritmo subjacente utilizado para a classificação.
Análise de técnicas de classificação :
- Quando o array está quase ordenado, a ordenação de inserção pode ser preferida.
- Quando a ordem de entrada não é conhecida, a ordenação de fusão é preferida porque tem a pior complexidade de tempo de nlogn e também é estável.
- Quando o array está ordenado, a ordenação de inserção e bolha dá complexidade de n mas a ordenação rápida dá complexidade de n^2.
Que – 1. Qual algoritmo de ordenação levará menos tempo quando todos os elementos do array de entrada são idênticos? Considere implementações típicas de algoritmos de ordenação.
(A) Inserção Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort
Solution: Como discutido, a ordenação da inserção terá a complexidade de n quando a matriz de entrada já estiver ordenada.
Que – 2. Considere o algoritmo de Quicksort. Suponha que existe um procedimento para encontrar um elemento pivot que divide a lista em duas sub-listas cada uma das quais contém pelo menos um quinto dos elementos. Deixe T(n) ser o número de comparações necessárias para ordenar n elementos. Então, (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Solução: A complexidade da classificação rápida pode ser escrita como:
T(n) = T(k) + T(n-k-1) + cn
Como dada em questão, uma lista contém 1/5 do total de elementos. Portanto, outra lista conterá 4/5 do total de elementos. Colocando valores, obtemos:
T(n) = T(n/5) + T(4n/5) + cn, que corresponde à opção (B).
Tabela Comparativa de Complexidade de Tempo e Espaço :
| Algoritmo de ordenação | Complexidade temporal | Complexidade espacial | |||
|---|---|---|---|---|---|
| Best Case | Média Case | Worst Case | Worst Case | ||
| Bubble Sort | Ω(N) | Θ(N2) | O(N2) | O(1) | |
| Selection Sort | Ω(N2) | Θ(N2) | O(N2) | O(1) | |
| Insertion Sort | Ω(N) | Θ(N2) | O(N2) | O(1) | |
| > | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) | |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N log N) | O(1) |
| Quick Sort | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) | |
| Radix Sort | Ω(N k) | Θ(N k) | O(N k) | O(N + k) | |
| >Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) | |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) | |
