Algoritmo de classificação

Um algoritmo de ordenação é, em ciência da computação ou matemática , um algoritmo que permite organizar uma coleção de objetos de acordo com uma determinada relação de ordem . Os objetos a serem classificados são elementos de um conjunto fornecido com uma ordem total . Por exemplo, é comum classificar inteiros de acordo com a relação de ordem usual "é menor ou igual a". Os algoritmos de classificação são usados ​​em muitas situações. Eles são particularmente úteis para muitos algoritmos mais complexos , incluindo alguns algoritmos de pesquisa , como pesquisa dicotômica. Eles também podem ser usados ​​para formatar dados canonicamente ou torná-los mais legíveis para o usuário.

A coleção a ser ordenada é freqüentemente dada na forma de array , a fim de permitir acesso direto aos diferentes elementos da coleção, ou na forma de uma lista , que pode acabar sendo mais adequada para certos algoritmos e para o uso da programação funcional .

Um bom número de algoritmos de classificação procedem por comparações sucessivas e podem, portanto, ser definidos independentemente do conjunto ao qual os elementos pertencem e da relação de ordem associada. O mesmo algoritmo pode, por exemplo, ser usado para classificar números reais de acordo com a relação de ordem usual "é menor ou igual a" e cadeias de caracteres de acordo com a ordem lexicográfica . Esses algoritmos naturalmente se prestam a uma implementação polimórfica .

Os algoritmos de classificação são freqüentemente estudados em cursos de algoritmo para introduzir conceitos como complexidade algorítmica ou terminação .

Critérios de classificação

A classificação dos algoritmos de ordenação é muito importante, pois permite escolher o algoritmo mais adequado ao problema tratado, tendo em consideração as restrições por ele impostas. As principais características que distinguem os algoritmos de ordenação, além do seu princípio de funcionamento, são a complexidade temporal , a complexidade espacial e o caráter estável.

Princípio da Operação

É feita uma distinção entre algoritmos que procedem por comparações sucessivas entre elementos, conhecidas como "classificação por comparação", de algoritmos mais especializados que fazem suposições restritivas sobre a estrutura dos dados a serem classificados (por exemplo, classificação por contagem, aplicável apenas se os dados são tomadas em um conjunto limitado conhecido de antemão).

Os algoritmos de classificação por comparação lêem entradas apenas por meio de uma função de comparação binária ou ternária (quando o caso de igualdade é tratado de maneira diferente). Existem ainda princípios operacionais diferentes dentro desta classe: alguns algoritmos de classificação por comparação procedem por inserções sucessivas, outros por fusão, outros ainda por seleção.

Na ausência de detalhes, o termo “algoritmo de classificação” geralmente significa um algoritmo de classificação que procede por comparações.

Complexidade algorítmica

• A complexidade de tempo ( média ou no pior caso ) mede o número de operações elementares para classificar uma coleção de itens. Este é o principal critério para comparar algoritmos de classificação, uma vez que é uma estimativa direta do tempo de execução do algoritmo. No caso dos algoritmos de ordenação por comparação, a complexidade do tempo é mais frequentemente assimilada ao número de comparações realizadas, sendo a comparação e possível troca de dois valores realizada em tempo constante.
• A complexidade espacial ( em média ou no pior caso ) representa, por sua vez, a quantidade de memória que o algoritmo precisará para funcionar. Isso pode depender, como o tempo de execução, do tamanho da entrada. É comum que as complexidades espaciais média e de pior caso sejam as mesmas. Muitas vezes, isso é implicitamente o caso quando uma complexidade é fornecida sem indicação adicional.

A complexidade do tempo é freqüentemente observada e é expressa como uma função do número de itens a serem classificados usando as notações de Landau e . T{\ displaystyle T}não{\ displaystyle n} O{\ displaystyle O}Θ{\ displaystyle \ Theta}

Alguns algoritmos de ordenação simples apresentam complexidade no tempo quadrático, ou seja , enquanto outros, mais desenvolvidos, apresentam complexidade quase linear . T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}T(não)=O(nãoregistro⁡(não)){\ displaystyle T (n) = O (n \ log (n))}

A complexidade de tempo médio de um algoritmo baseado em uma função de comparação não pode ser melhor do que . Os tipos que requerem apenas comparações em média são, portanto, considerados ótimos. Esse resultado constitui um limite inferior assintótico, mas também mostramos que o número exato de comparações necessárias é reduzido em . O(nãoregistro⁡(não)){\ displaystyle O (n \ log (n))}O(nãoregistro⁡(não)){\ displaystyle O (n \ log (n))}⌈registro2⁡(não!)⌉{\ displaystyle \ lceil \ log _ {2} (n!) \ rceil}

Demonstração

O problema de ordenação consiste, dada uma série de elementos de um conjunto totalmente ordenado (por exemplo, fornecido com a ordem usual), em determinar uma permutação de tal que é ordenado. você=(você1,você2,...,vocênão){\ displaystyle u = (u_ {1}, u_ {2}, \ dots, u_ {n})}NÃO{\ displaystyle \ mathbb {N}}σ{\ displaystyle \ sigma}1,...,não{\ displaystyle 1, \ dots, n}(vocêσ(1),...,vocêσ(não)){\ displaystyle (u _ {\ sigma (1)}, \ dots, u _ {\ sigma (n)})}

Para simplificar, presume-se que todos os elementos a serem classificados são distintos, o que torna a permutação única. O resultado permanece verdadeiro a fortiori no caso geral. σ{\ displaystyle \ sigma}

Um algoritmo de classificação por comparações sucessivas é modelado como uma árvore binária . Cada nó da árvore corresponde a uma comparação entre dois elementos e , e compreende dois filhos que representam as duas comparações possíveis a seguir, dependendo do resultado da primeira. vocêeu{\ displaystyle u_ {i}}vocêj{\ displaystyle u_ {j}}

Cada execução do algoritmo em uma permutação de pode ser associada ao caminho que vai da raiz a uma folha correspondente a essa execução; duas entradas diferentes estão necessariamente associadas a dois caminhos diferentes. O número de permutações de elementos distintos dois por dois sendo , o número de folhas da árvore é maior ou igual a este valor. você{\ displaystyle u}não{\ displaystyle n}não!{\ displaystyle n!}

Limite inferior para a complexidade do pior caso

Observe a altura da árvore ( ou seja, sua profundidade máxima, que corresponde ao número de comparações no pior caso ). O número máximo de folhas em uma árvore de altura binária é . h{\ displaystyle h}h{\ displaystyle h}2h{\ displaystyle 2 ^ {h}}

Por isso, é: . Por um lado ,. Por outro lado, usando a fórmula de Stirling , obtemos assintoticamente . 2h≥não!{\ displaystyle 2 ^ {h} \ geq n!}h≥⌈registro2⁡(não!)⌉{\ displaystyle h \ geq \ lceil \ log _ {2} (n!) \ rceil}h≥não⋅registro2⁡(não)-não/em⁡2=Θ(nãoregistro⁡não){\ displaystyle h \ geq n \ cdot \ log _ {2} (n) -n / \ ln 2 = \ Theta (n \, \ log n)}

O fato de haver espécies mostra, por outro lado, que é possível ter de forma assintótica . Este limite, portanto, fornece a complexidade mínima no pior caso de um algoritmo de classificação por comparações. não⋅registro2⁡(não){\ displaystyle n \ cdot \ log _ {2} (n)}h≤não⋅registro2⁡(não){\ displaystyle h \ leq n \ cdot \ log _ {2} (n)}

Limite inferior para complexidade média

Dada uma árvore binária , denotamos a profundidade média das folhas de . Se todas as permutações dos elementos de entrada forem igualmente prováveis, então o número médio de comparações do tipo com uma árvore de comparação é . NO{\ displaystyle A}F(NO){\ displaystyle F (A)}NO{\ displaystyle A}NO{\ displaystyle A}F(NO){\ displaystyle F (A)}

Para um número fixo de nós, as árvores minimizantes são as árvores binárias completas (ou seja, aquelas cujas folhas estão no último ou penúltimo nível). Na verdade, em uma árvore incompleta, há uma folha profunda e, no máximo, uma folha funda . Pendurando a primeira folha na segunda, obtemos uma árvore como . F{\ displaystyle F}NO{\ displaystyle A}h{\ displaystyle h}h-2{\ displaystyle h-2}NO′{\ displaystyle A '}F(NO′)<F(NO){\ displaystyle F (A ') <F (A)}

A função assume o mesmo valor para todas as árvores binárias completas com folhas. Qualquer um deles e sua altura. Todas as folhas são pelo menos profundas , então a profundidade média das folhas é de pelo menos (novamente usando a propriedade ). F{\ displaystyle F}não!{\ displaystyle n!}NO{\ displaystyle A}h{\ displaystyle h}h-1{\ displaystyle h-1}h-1=Ω(nãoregistro⁡não){\ displaystyle h-1 = \ Omega (n \, \ log n)}2h≥não!{\ displaystyle 2 ^ {h} \ geq n!}

Para certos tipos de dados (inteiros, cadeias de caracteres de tamanho limitado), no entanto, existem algoritmos que são mais eficientes em termos de tempo de execução, como classificação de contagem ou classificação de base . Esses algoritmos não usam a comparação entre os elementos (o limite n · log (n) não se aplica, portanto, a eles), mas exigem suposições sobre os objetos a serem classificados. Por exemplo, a classificação por contagem e a classificação por base se aplicam a inteiros que sabemos pertencer ao conjunto [1, m ] com uma suposição adicional para a classificação por base de que m é uma potência de 2 (c 'isto é, do formulário 2k ).

Ordenando no local

Diz- se que uma classificação está em vigor se ela usar apenas um número muito limitado de variáveis ​​e modificar diretamente a estrutura que está classificando. Isso requer o uso de uma estrutura de dados adaptada (uma matriz, por exemplo). Este personagem pode ser muito importante se você não tiver muita memória.

No entanto, em geral, os próprios dados não são movidos, mas apenas referências (ou ponteiros ) a eles são modificados .

Classificação estável

Uma classificação é considerada estável se preserva a ordem inicial dos elementos que a ordem considera iguais. Para definir essa noção, é necessário que a coleção a ser ordenada seja ordenada de uma determinada maneira (o que costuma ser o caso para muitas estruturas de dados , por exemplo, para listas ou arrays).

Exemplo:

Vamos definir a relação de ordem definida nos pares de inteiros por ssi , que permite ordenar dois pares de acordo com seu primeiro valor. ≼{\ displaystyle \ preccurlyeq}(no,b)≼(vs,d){\ displaystyle (a, b) \ preccurlyeq (c, d)}no≤vs{\ displaystyle a \ leq c}

Ou seja, uma lista de pares de inteiros que se deseja ordenar de acordo com a relação previamente definida. eu=[(4,1);(3,2);(3,3);(5,4)]{\ displaystyle L = [(4.1); (3.2); (3.3); (5.4)]}≼{\ displaystyle \ preccurlyeq}

Uma vez que e são iguais para a relação , chamar um algoritmo de classificação com entrada pode levar a duas saídas diferentes: (3,2){\ displaystyle (3,2)}(3,3){\ displaystyle (3.3)}≼{\ displaystyle \ preccurlyeq}eu{\ displaystyle L}

• eu1=[(3,2);(3,3);(4,1);(5,4)]{\ displaystyle L_ {1} = [(3.2); (3.3); (4.1); (5.4)]}
• eu2=[(3,3);(3,2);(4,1);(5,4)]{\ displaystyle L_ {2} = [(3.3); (3.2); (4.1); (5.4)]}

eu1{\ displaystyle L_ {1}}e são classificados de acordo com , mas mantêm apenas a ordem relativa. Em , aparece antes , portanto, um algoritmo de classificação que teria tomado como entrada e retornado como saída seria instável. eu2{\ displaystyle L_ {2}}≼{\ displaystyle \ preccurlyeq}eu1{\ displaystyle L_ {1}}eu2{\ displaystyle L_ {2}}(3,3){\ displaystyle (3.3)}(3,2){\ displaystyle (3,2)}eu{\ displaystyle L}eu2{\ displaystyle L_ {2}}

Algoritmos de classificação instáveis ​​podem ser retrabalhados especificamente para torná-los estáveis; no entanto, isso pode custar a velocidade e / ou pode exigir espaço de memória adicional.

Entre os algoritmos listados abaixo, as classificações estáveis ​​são: a classificação por bolha , a classificação por inserção e a classificação por mesclagem . Os outros algoritmos requerem memória adicional para armazenar a ordem inicial dos elementos. O(não){\ displaystyle O (n)}

Classificação interna e externa

Uma classificação interna é realizada inteiramente na memória central, enquanto uma classificação externa usa arquivos em uma memória de massa para classificar os volumes que são muito grandes para caber na memória central. Certos tipos de classificação, como classificação por mesclagem ou classificação por distribuição, são facilmente adaptados para o uso de memória externa. Outros algoritmos, por outro lado, acessam os dados de forma que não se prestem a esse uso, pois exigiriam a realização constante de leituras / escritas entre as memórias principal e externa.

Classificação paralela

Certos algoritmos permitem explorar as capacidades multitarefa da máquina. Deve-se notar também que certos algoritmos, em particular aqueles que funcionam por inserção, podem ser iniciados sem conhecer todos os dados a serem ordenados; podemos então classificar e produzir os dados a serem classificados em paralelo.

Comparação de algoritmos

A tabela abaixo torna possível comparar diferentes algoritmos de classificação procedendo por comparações. y representa o número de itens a serem classificados. Todas as complexidades devem ser interpretadas usando um O maiúsculo de Landau . Presume-se que operações básicas como comparações e trocas podem ser realizadas em tempo constante. não{\ displaystyle n}

Tabela comparativa de tipos usando comparações

Sobrenome	Caso ideal	Caso médio	Pior caso	Complexidade espacial	Estábulo
Ordenação rápida	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	não2{\ displaystyle n ^ {2}}	registro⁡não{\ displaystyle \ log n}em média, no pior caso; Variante Sedgewick: pior cenárionão{\ displaystyle n} registro⁡não{\ displaystyle \ log n}	Não
Mesclar classificação	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	não{\ displaystyle n}	sim
Classificar por pilha	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	1{\ displaystyle 1}	Não
Classificar por inserção	não{\ displaystyle n}	não2{\ displaystyle n ^ {2}}	não2{\ displaystyle n ^ {2}}	1{\ displaystyle 1}	sim
Introsort	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	registro⁡não{\ displaystyle \ log n}	Não
Classificar por seleção	não2{\ displaystyle n ^ {2}}	não2{\ displaystyle n ^ {2}}	não2{\ displaystyle n ^ {2}}	1{\ displaystyle 1}	Não
Timsort	não{\ displaystyle n}	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	não{\ displaystyle n}	sim
Classificação de conchas	não{\ displaystyle n}	nãoregistro2⁡não{\ displaystyle n \ log ^ {2} n} ou não3/2{\ displaystyle n ^ {3/2}}	nãoregistro2⁡não{\ displaystyle n \ log ^ {2} n}para a sequência de espaçamento mais conhecida	1{\ displaystyle 1}	Não
Classificação por bolha	não{\ displaystyle n}	não2{\ displaystyle n ^ {2}}	não2{\ displaystyle n ^ {2}}	1{\ displaystyle 1}	sim
Triagem de árvores	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n} (árvore balanceada)	não{\ displaystyle n}	sim
Smoothsort	não{\ displaystyle n}	nãoregistro⁡não{\ displaystyle n \ log n}	nãoregistro⁡não{\ displaystyle n \ log n}	1{\ displaystyle 1}	Não
Seleção de coquetéis	não{\ displaystyle n}	não2{\ displaystyle n ^ {2}}	não2{\ displaystyle n ^ {2}}	1{\ displaystyle 1}	sim
Classificação de pente	não{\ displaystyle n}	nãoregistro⁡não{\ displaystyle n \ log n}	não2{\ displaystyle n ^ {2}}	1{\ displaystyle 1}	Não
Tipo par-ímpar	não{\ displaystyle n}	não2{\ displaystyle n ^ {2}}	não2{\ displaystyle n ^ {2}}	1{\ displaystyle 1}	sim

Exemplos de algoritmos de classificação

Classificar por comparação

Algoritmos rápidos

• Sort merge ( merge sort ) - em todos os casos; estábulo; não está instalado por padrão. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}Este algoritmo é baseado no princípio “dividir para conquistar” . Para uma determinada entrada, o algoritmo divide em duas partes de tamanhos semelhantes, classifica cada uma delas usando o mesmo algoritmo e, em seguida, mescla as duas partes classificadas. É adequado para implementações de lista e tabela. É usado em particular pelo algoritmo híbrido Timsort .
• Classificação rápida ( quicksort ) - em média e na melhor das hipóteses, na pior das hipóteses; instável; em vigor na variante Sedgewick. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}Este método é baseado no princípio “dividir para conquistar” . Um valor é escolhido como pivô e os elementos menores que o pivô são dissociados, por trocas sucessivas, dos elementos maiores que o pivô; cada um desses dois subconjuntos é classificado da mesma maneira. A complexidade pode ser quase independente dos dados usando um pivô aleatório ou aplicando uma permutação aleatória ao array antes de classificá-lo.
• Classificar por heap ( classificação de heap ) - em todos os casos; no lugar, mas instável. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}Esta é uma melhoria na classificação por seleção . A ideia é a mesma (inserir os elementos um a um em uma estrutura já ordenada), mas o algoritmo usa uma estrutura de heap , muitas vezes implementada por meio de um array. Este algoritmo funciona muito bem em conjunto com a Classificação rápida. Na verdade, é eficaz quando se suspeita que os dados estão próximos do pior caso (quadrático) do tipo rápido.
• Introsort - em todos os casos; instável, mas no lugar. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}É um híbrido de classificação rápida e classificação de pilha .
• Árvore de classificação - em média, pior caso, melhor caso. ; nem estável nem no lugar. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}T(não)=O(não){\ displaystyle T (n) = O (n)}A ideia é inserir os elementos um a um em uma árvore de pesquisa binária e , em seguida, ler a árvore de acordo com um caminho em profundidade. Essa classificação é uma das mais lentas (entre as classificações rápidas) e uma das mais intensivas em memória por causa da estrutura de árvore binária a ser tratada. É possível torná-lo quase linear em todos os casos Mantendo uma árvore balanceada ( cf Árvore AVL ).
• Smoothsort - em média e no pior caso, no melhor caso; no lugar, mas instável. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}T(não)=O(não){\ displaystyle T (n) = O (n)}Sort inspirado na classificação por heap , mas que usa uma árvore não invertida . Essa classificação é muito rápida para conjuntos que já estão quase classificados.

Para um determinado algoritmo de classificação instável, é fácil obter uma variante estável usando uma matriz adicional para armazenar a ordem inicial dos elementos. No entanto, o algoritmo resultante não está em vigor.

Algoritmos moderadamente rápidos

• Classificação de shell ( classificação de shell ) - para a série de etapas e para a série de etapas  ; instável; no lugar. T(não)=O(nãoregistro2⁡não){\ displaystyle T (n) = O (n \ log ^ {2} n)}2p3q{\ displaystyle 2 ^ {p} 3 ^ {q}}T(não)=O(não3/2){\ displaystyle T (n) = O (n ^ {3/2})}2k-1{\ displaystyle 2 ^ {k} -1}Esta ordenação baseia-se na ordenação por inserção das sub-sequências da entrada obtida retirando os elementos espaçados por um passo constante, para uma sequência de passos predefinidos. A complexidade varia dependendo da escolha desta suíte. Não sabemos de uma série de doações .O(nãoregistro⁡não){\ displaystyle O (n \ log n)}
• Sort merge ( merge sort ) - em todos os casos; estábulo; não está instalado por padrão. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}Este algoritmo é baseado no princípio “dividir para conquistar” . Para uma determinada entrada, o algoritmo divide em duas partes de tamanhos semelhantes, classifica cada uma delas usando o mesmo algoritmo e, em seguida, mescla as duas partes classificadas. É adequado para implementações de lista e tabela. É usado em particular pelo algoritmo híbrido Timsort .
• Classificação rápida ( quicksort ) - em média e na melhor das hipóteses, na pior das hipóteses; instável; em vigor na variante Sedgewick. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}Este método é baseado no princípio “dividir para conquistar” . Um valor é escolhido como pivô e os elementos menores que o pivô são dissociados, por trocas sucessivas, dos elementos maiores que o pivô; cada um desses dois subconjuntos é classificado da mesma maneira. A complexidade pode ser quase independente dos dados usando um pivô aleatório ou aplicando uma permutação aleatória ao array antes de classificá-lo.
• Classificar por heap ( classificação de heap ) - em todos os casos; no lugar, mas instável. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}Esta é uma melhoria na classificação por seleção . A ideia é a mesma (inserir os elementos um a um em uma estrutura já ordenada), mas o algoritmo usa uma estrutura de heap , muitas vezes implementada por meio de um array. É interessante usar essa classificação se suspeitarmos que os dados a serem classificados serão freqüentemente casos quadráticos para a classificação rápida.
• Introsort - em todos os casos; instável, mas no lugar. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}Este é um algoritmo híbrido que usa os algoritmos de classificação rápida e classificação de heap .
• Árvore de classificação - em média, pior caso, melhor caso. ; nem estável nem no lugar. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}T(não)=O(não){\ displaystyle T (n) = O (n)}A ideia é inserir os elementos um a um em uma árvore de pesquisa binária e , em seguida, ler a árvore de acordo com um caminho em profundidade. Essa classificação é uma das mais lentas (entre as classificações rápidas) e uma das mais intensivas em memória por causa da estrutura de árvore binária a ser tratada. É possível torná-lo quase linear em todos os casos, mantendo uma árvore balanceada ( cf Árvore AVL ).
• Smoothsort - em média e no pior caso, no melhor caso; no lugar, mas instável. T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}T(não)=O(não){\ displaystyle T (n) = O (n)}Classificar inspirado na classificação por heap , mas que usa uma árvore não invertida. Essa classificação é muito rápida para conjuntos que já estão quase classificados.
• Classificação pente ( classificação pente ) - no melhor caso, em média e no pior caso; instável, mas no lugar. T(não)=O(não){\ displaystyle T (n) = O (n)}T(não)=O(nãoregistro⁡não){\ displaystyle T (n) = O (n \ log n)}T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}Esta é uma variante mais eficiente da classificação por bolha , não apenas comparando itens consecutivos. Podemos dizer que a classificação por bolha é a classificação Shell para a classificação por inserção .

Para um determinado algoritmo de classificação instável, é fácil obter uma variante estável usando uma matriz adicional para armazenar a ordem inicial dos elementos. No entanto, o algoritmo resultante não está em vigor. por trabalhar em listas).

• É, a cada iteração, identificar o menor dos elementos que ainda não foram classificados e trocá-lo com o primeiro deles. Essa classificação é rápida para entradas pequenas e é codificada de forma concisa.
• Classificação de inserção - em média e pior caso, melhor caso; estável e no lugar. T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}T(não)=O(não){\ displaystyle T (n) = O (n)}Esta é a classificação frequentemente usada naturalmente para classificar cartas de jogar: os valores são inseridos um após o outro em uma lista classificada (inicialmente vazia). Freqüentemente, é o mais rápido e o mais usado para classificar pequenas entradas. Também é eficaz para entradas que já estão quase classificadas.
• Classificação por bolha - em média e na pior das hipóteses, na melhor das hipóteses; estável e no lugar. T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}T(não)=O(não){\ displaystyle T (n) = O (n)}O algoritmo consiste em percorrer a entrada do início ao fim e, para cada par de elementos consecutivos, invertê-los se estiverem mal ordenados. Esta operação é repetida até que a estrutura seja classificada (sem inversão durante a última passagem). Este algoritmo é ineficiente e raramente usado na prática; seu interesse é principalmente educacional.
• Coquetel de seleção - em média e na pior das hipóteses, na melhor das hipóteses; estável e no lugar. T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}T(não)=O(não){\ displaystyle T (n) = O (n)}Esta é uma variante da classificação por bolha na qual a entrada é percorrida alternadamente em ambas as direções. Se torna possível lidar de forma mais eficaz com alguns casos problemáticos para classificação de bolhas, permanece essencialmente semelhante a este último e o interesse é, mais uma vez, principalmente educacional.
• Tipo par-ímpar - em média e pior caso, melhor caso; estável e no lugar. T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}T(não)=O(não){\ displaystyle T (n) = O (n)}Esta é uma variante da classificação por bolha, que funciona comparando sucessivamente todos os itens do índice par com os itens do índice ímpar que os seguem e vice-versa. Iremos, portanto, começar comparando o primeiro elemento com o segundo, o terceiro com o quarto, etc., então iremos comparar o segundo elemento com o terceiro, o quarto com o quinto etc. A operação é repetida até que a estrutura seja classificada.

Algoritmos lentos

Esses algoritmos têm uma complexidade assintótica e, portanto, são considerados lentos para entradas cujo tamanho é superior a algumas dezenas de elementos. O(não2){\ displaystyle O (n ^ {2})}

• Classificar por seleção - em todos os casos; no local; instável por padrão (pode se tornar estável, mas de preferência trabalhando em listas).T(não)=O(não2){\ displaystyle T (n) = O (n ^ {2})}

Algoritmos muito lentos

Esses algoritmos têm uma complexidade assintótica pior do que , que é a complexidade dos algoritmos mais intuitivos. O(não2){\ displaystyle O (n ^ {2})}

• Classificação Estúpida - Não termina no pior caso, na média e no melhor caso; instável, mas no lugar. T(não)=O(não!){\ displaystyle T (n) = O (n!)}T(não)=O(não){\ displaystyle T (n) = O (n)}A classificação estúpida consiste em verificar se os itens estão ordenados e se não estão, embaralhando-os aleatoriamente e, em seguida, repetindo a operação.
• Classificando fantoches ( tipo de fantoches ) - ou aproximadamente  ; instável e não no lugar . T(não)=O(nãoregistro⁡3registro⁡1,5){\ displaystyle T (n) = O (n ^ {\ frac {\ log 3} {\ log 1,5}})}O(não2,71){\ displaystyle O (n ^ {2.71})}Essa classificação consiste em trocar o primeiro e o último elemento, se necessário, em seguida, classificar recursivamente os primeiros dois terços, depois os dois últimos e, em seguida, os dois primeiros da matriz novamente.

Classifica usando a estrutura de dados

• Contando tipo ou triagem por contagem ( contagem espécie ): algoritmo linear, T (n) = O (n), estável, mas requer o uso de uma segunda lista do mesmo comprimento que a lista de ser resolvida. Seu uso depende da condição de que os valores a serem ordenados sejam números naturais dos quais conhecemos os extremos;
• Classificar por base ( classificação raiz ): também é uma classificação linear sob certas condições (menos restritiva do que para classificação por contagem), T (n) = O (n), estável, mas também requer o uso de uma segunda lista do mesmo comprimento como a lista a classificar;
• Classificação de pacotes ( classificação de balde ): Estável e linearmente complexa - assume que os dados a serem classificados são distribuídos uniformemente em um intervalo real .T(não)=O(não){\ displaystyle T (n) = O (n)}[no,b[{\ displaystyle [a, b [}

Classificações externas

Os algoritmos de classificação também devem ser adaptados de acordo com as configurações do computador em que são usados. Nos exemplos citados acima, assume-se que todos os dados estão presentes na memória principal (ou acessíveis na memória virtual). A situação se torna mais complexa se alguém deseja classificar volumes de dados maiores do que a memória principal disponível (ou se alguém busca melhorar a classificação otimizando o uso da hierarquia de memória).

Esses algoritmos são geralmente baseados em uma abordagem bastante semelhante à classificação por mesclagem . O princípio é o seguinte:

• dividir o volume de dados a serem classificados em subconjuntos de tamanho menor do que a memória rápida disponível;
• classificar cada subconjunto na memória principal para formar “monotonias” (subconjuntos classificados);
• interclasse de monotonias.

Escolha empírica de um algoritmo de classificação

Existem muitos algoritmos, mas alguns são usados ​​muito mais do que outros na prática. A classificação por inserção é freqüentemente elogiada para dados pequenos, enquanto algoritmos assintoticamente eficientes, como classificação por mesclagem , o heapsort ou quicksort serão usados ​​para dados maiores.

Existem implementações perfeitamente otimizadas, que geralmente são algoritmos híbridos . Timsort, portanto, usa os métodos de classificação por mesclagem e classificação por inserção , e é usado por Android , Java e Python, entre outros  ; O Introsort , que combina classificação rápida e classificação de heap , é usado em algumas implementações de classificação C ++ .

A comparação empírica de algoritmos não é fácil na medida em que muitos parâmetros são levados em consideração: tamanho dos dados, ordem dos dados, hardware usado, tamanho da RAM, etc. Por exemplo, os testes realizados em dados sorteados ao acaso não representam necessariamente com muita fidelidade os comportamentos obtidos com dados reais.

Acesso a RAM

Para comparar diferentes algoritmos, é importante levar em consideração o tamanho dos dados a serem classificados, bem como a quantidade de RAM disponível. Quando não há RAM suficiente para armazenar os dados, o computador recorre ao uso de memória externa, resultando em tempos de acesso significativamente mais longos.

Nessa situação, algoritmos que funcionam sucessivamente em partes menores da entrada (que serão, por exemplo, mescladas posteriormente) tenderão a funcionar melhor do que algoritmos como quicksort, que realizarão mais acesso à memória externa.

Também é possível evitar tais situações, por exemplo, associando os dados a serem classificados com chaves menores e classificando essas chaves diretamente na RAM. Quando o tamanho dos dados for muito grande, um algoritmo de ordenação externo será usado para minimizar o número de acessos à memória externa.

Assuntos relacionados

Entre os problemas próximos à ordenação, podemos citar a ordenação parcial  (in) , que consiste, para fixo, em ordenar os menores elementos, ou o problema de seleção , que consiste em encontrar o -ésimo menor elemento da entrada. Embora a classificação de toda a entrada possa resolver esses problemas, existem soluções mais sutis e menos dispendiosas. Esse é o caso, por exemplo, da seleção rápida , que tem semelhanças com a classificação rápida . k{\ displaystyle k}k{\ displaystyle k}k{\ displaystyle k}

Por outro lado, podemos tentar construir algoritmos que misturam aleatoriamente a entrada fornecida a eles; é o caso, por exemplo, da mistura Fisher-Yates .

Outro problema é classificar um array que já está quase classificado (este é o caso de big data, onde algoritmos convencionais são desqualificados). Isso pode reabilitar algoritmos como classificação de inserção .

História

A criação da primeira rotina de triagem é atribuída a Betty Holberton , durante a Segunda Guerra Mundial.

Apêndices

Notas e referências

1. http://www.site.uottawa.ca/~kiringa/courses10/csi3530/ch13_extsort_csi3530-10.ppt
2. http://www.umiacs.umd.edu/research/EXPAR/papers/3670.html
3. Podemos fazer a classificação por mesclagem uma classificação no local e sempre dentro , mas o algoritmo faz mais cópias e é mais complicado de programarO(nãoregistro⁡não){\ displaystyle O (n \ log n)}
4. Conheça os programadores da ENIAC, os pioneiros da indústria de software , intel.fr, junho de 2016

Bibliografia

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein ( trad.  Do inglês), Algorithms  : Lecture with Exercícios 957 e 158 problems , Dunod ,2010[ detalhe da edição ]
• Christine Froidevaux , Marie-Claude Gaudel e Michèle Soria , Tipos de dados e algoritmos , McGraw-Hill,1990, 577  p. ( ISBN  978-2-7042-1217-0 , aviso BnF n o  FRBNF35070753 , leitura online ) , cap.  16

links externos

• Dissertação de síntese sobre algoritmos de classificação
• Arquivo sobre algoritmos de classificação e sua complexidade (e implementação em várias linguagens)
• Ilustração dinâmica de vários tipos (requer Java)
• (pt) Ilustração dinâmica de vários tipos
• (pt) "  Classificando Algoritmos Visualizados  " , Visualização de diferentes tipos usando cores
• No site da Interstices, documente sobre algoritmos de classificação com um miniaplicativo Java

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">