Estrutura de dados - técnicas de classificação
A classificação refere-se à organização dos dados em um formato específico. O algoritmo de classificação especifica a maneira de organizar os dados em uma ordem específica. As ordens mais comuns são em ordem numérica ou lexicográfica.
A importância da classificação reside no fato de que a pesquisa de dados pode ser otimizada para um nível muito alto, se os dados forem armazenados de maneira classificada. A classificação também é usada para representar dados em formatos mais legíveis. A seguir estão alguns exemplos de classificação em cenários da vida real -
Telephone Directory - A lista telefônica armazena os números de telefone das pessoas classificadas por seus nomes, para que os nomes possam ser pesquisados facilmente.
Dictionary - O dicionário armazena as palavras em ordem alfabética para que a pesquisa de qualquer palavra seja fácil.
Classificação no local e não no local
Os algoritmos de classificação podem exigir algum espaço extra para comparação e armazenamento temporário de alguns elementos de dados. Esses algoritmos não requerem nenhum espaço extra e a classificação ocorre no local ou, por exemplo, dentro do próprio array. Isso é chamadoin-place sorting. A classificação por bolha é um exemplo de classificação no local.
No entanto, em alguns algoritmos de classificação, o programa requer espaço maior ou igual aos elementos sendo classificados. A classificação que usa igual ou mais espaço é chamadanot-in-place sorting. Merge-sort é um exemplo de classificação não no local.
Classificação estável e não estável
Se um algoritmo de classificação, após classificar o conteúdo, não alterar a sequência de conteúdo semelhante em que aparecem, ele é chamado stable sorting.
Se um algoritmo de classificação, após classificar o conteúdo, alterar a sequência de conteúdo semelhante em que aparecem, ele é chamado unstable sorting.
A estabilidade de um algoritmo é importante quando desejamos manter a sequência dos elementos originais, como em uma tupla, por exemplo.
Algoritmo de classificação adaptativo e não adaptativo
Um algoritmo de classificação é considerado adaptativo, se tirar vantagem de elementos já 'classificados' na lista a ser classificada. Ou seja, ao classificar se a lista de fontes já tiver algum elemento classificado, os algoritmos adaptativos levarão isso em consideração e tentarão não reordená-los.
Um algoritmo não adaptativo é aquele que não leva em consideração os elementos já classificados. Eles tentam forçar cada elemento a ser reordenado para confirmar sua classificação.
Termos importantes
Alguns termos são geralmente criados durante a discussão de técnicas de classificação, aqui está uma breve introdução a eles -
Ordem crescente
Uma sequência de valores está em increasing order, se o elemento sucessivo for maior que o anterior. Por exemplo, 1, 3, 4, 6, 8, 9 estão em ordem crescente, pois cada próximo elemento é maior do que o elemento anterior.
Ordem Decrescente
Uma sequência de valores está em decreasing order, se o elemento sucessivo for menor que o atual. Por exemplo, 9, 8, 6, 4, 3, 1 estão em ordem decrescente, pois cada próximo elemento é menor que o elemento anterior.
Ordem não crescente
Uma sequência de valores está em non-increasing order, se o elemento sucessivo for menor ou igual ao elemento anterior na sequência. Essa ordem ocorre quando a sequência contém valores duplicados. Por exemplo, 9, 8, 6, 3, 3, 1 estão em ordem não crescente, pois cada próximo elemento é menor ou igual a (no caso de 3), mas não maior do que qualquer elemento anterior.
Ordem não decrescente
Uma sequência de valores está em non-decreasing order, se o elemento sucessivo for maior ou igual ao elemento anterior na sequência. Essa ordem ocorre quando a sequência contém valores duplicados. Por exemplo, 1, 3, 3, 6, 8, 9 estão em ordem não decrescente, pois cada próximo elemento é maior ou igual a (no caso de 3), mas não menor que o anterior.