Algoritmos de ordenação são uma estranha combinação de fundamentalmente necessário, e profundamente controversa. De novos engenheiros que procuram impressionar em uma entrevista para engenheiros mais velhos procurando uma solução para um banco de dados de escala rápida, há uma miríade de fatores a levar em consideração. Qual é a velocidade de comparação entre dois objetos? Qual é a hora da troca? Qual é o tamanho da base de dados? Que tipo de objectos contém? Já está semi-organizado? Os resultados precisam ser estáveis?

cada uma destas questões pode extrair argumentos a favor de um algoritmo ou outro. Os dados de origem são grandes e complexos? A maioria das linguagens padrão para o padrão, Ordenação rápida com a sua complexidade de tempo O( n log n). É mais pequeno? O Insertion Sort faz maravilhas nisso. Quase tudo resolvido? Bolas, o Bubble Sort pode quase funcionar para isso. Se você quiser ler/visualizar os méritos de cada um, Confira esta comparação por toptal.com.

um algoritmo de ordenação que você não encontrará nesse site, ou quase qualquer outro, é o Tim Sort. Este tipo obscuro é atualmente exclusivo do Python, e é usado como seu algoritmo de ordenação padrão. Call array.sort in Python, and Tim Sort is what gets executed. Apesar disso, é raro encontrar engenheiros que conheçam e entendam Tim Sort. Então: o que é?

Tim Sort foi implementado pela primeira vez em 2002 por Tim Peters para uso em Python. Ele supostamente veio do entendimento de que a maioria dos algoritmos de ordenação nascem em salas de aula, e não foram projetados para uso prático em dados do mundo real. Tim Sort tira vantagem de padrões comuns em dados, e utiliza uma combinação de Merge Sort e Insertion Sort junto com alguma lógica interna para otimizar a manipulação de dados em larga escala.

Por Tim Classificação?olhando para a figura 2, podemos ver imediatamente algo interessante. No seu melhor, o Tim Sport outperforms Merge Sort e Quick Sort. Na pior das hipóteses, ele corre a velocidade comparável Merge Sort e na verdade supera o Quick Sort. Por outras palavras, é inesperadamente rápido.

em termos de espaço, o Tim Sort está na extremidade pior do espectro, mas a consideração de espaço para a maioria dos algoritmos de ordenação é muito escassa. O (n) não é muito áspero na maioria dos casos; vale a pena notar como uma possível deficiência, e o único lugar onde o Quick Sort supera o Tim Sort.

O item final em que algoritmos de ordenação são muitas vezes julgados é a estabilidade. Estabilidade é o conceito de que, quando ordenados, objetos de igual valor mantêm sua ordem original. Deves estar a perguntar-te porque nos preocupamos com isso. Os itens são de igual valor-por que nos importamos como eles são encomendados?

A resposta simples é que a estabilidade importa para os tipos empilhados. Ou seja, primeiro ordenamos com base num critério, depois num segundo. Se você fizer isso em um algoritmo instável, você perde instantaneamente qualquer confiabilidade de seu primeiro tipo quando você executa o segundo. Para referência, O Quick Sort é instável, e o Merge Sort é estável.

TIM Sort também é estável, para não mencionar rápido se ligeiramente pesado(em comparação com o Quick Sort apenas). Enquanto algoritmos de ordenação podem (e devem) ser julgados em outras considerações, estes são os três grandes.

a implementação em três etapas

a ordenação Tim é complexa, mesmo por padrões algorítmicos. A melhor forma de proceder é dividindo a execução em partes.

busca binária

a primeira coisa que você precisa para implementar uma ordenação de Tim é um método de busca binária. Isto é apenas usado para implementar o seu tipo de inserção mais tarde.

para referência: algoritmos de pesquisa binários

Insertion Sort Merge Sort

Em segundo lugar, é necessário codificar a ordenação de inserção e a ordenação de junção. Estes são algoritmos familiares, e devem estar no bolso de trás da maioria dos engenheiros, mas vamos rever os fundamentos de como eles funcionam e porque eles são valiosos para nós aqui.

Inserção de Classificação é um algoritmo de classificação. Ele corre através do array, e sempre que ele encontra um item que está fora de ordem (estritamente menos/mais do que o item antes dele), ele o move para a posição apropriada no array já ordenado. Insertion Sort é conhecido por trabalhar muito rapidamente em arrays já ordenados, bem como arrays menores. Na verdade, podemos ver da Fig. 2 que o Insertion Sort tem um impressionante tempo de execução de melhor caso de O (n). Tenha em mente seguir em frente com o Tim Sort: o melhor caso para o Insertion Sort é um array já ordenado. Pode parecer tolice, mas isso será relevante.

Merge Sort, por outro lado, opera por um princípio básico: é extremamente fácil de mesclar já matrizes classificadas. Então, ele divide um array de partida em duas vezes, até que ele não é nada além de elementos únicos. Então ele lentamente reconstrói a matriz principal, fundindo esses elementos novamente em ordem ordenada. Como começamos a partir de blocos de construção do tamanho 1, foi muito fácil construir matrizes ordenadas iniciais. Então, é fácil fundi-los. No final, gastamos O (n log n) Tempo, e (importante) fazemos isso de uma maneira que é garantida para ser estável.

Por exemplo, implementações, ver:

Merge Sort: https://www.geeksforgeeks.org/merge-sort/

Inserção de Classificação: https://www.geeksforgeeks.org/insertion-sort/

Implementar Tim Sort

a chave para A compreensão Tim Tipo de implementação é a compreensão de seu uso é executado. O Tim Sort alavanca os dados pré-selecionados naturalmente para sua vantagem. Por presortados, queremos simplesmente dizer que os elementos sequenciais estão todos a aumentar ou a diminuir (não nos importa qual).

primeiro definimos um minrun tamanho. O que queremos dizer com isto é que queremos garantir que todos os nossos percursos sejam, pelo menos, um certo comprimento. Por favor, note que não estamos garantindo que vamos encontrar corridas deste tamanho — vamos entrar nisto mais tarde. Estamos apenas a dizer que uma corrida deve ter pelo menos um certo comprimento.quando encontramos uma corrida, colocamo-la de lado. Quando encontramos a execução mais longa dentro de um intervalo minrun. Agora temos uma estrutura de dados familiar: uma pequena matriz ordenada. Se for pelo menos minrun em comprimento, então huzzah! Estamos prontos para seguir em frente. Se não for, colocamos a inserção em jogo.

pode lembrar-se de cima que a ordenação de inserção é especialmente eficaz em dois tipos de matrizes: pequenas e já ordenadas. O que acabamos de fazer é uma pequena e ordenada matriz. Se não for pelo menos minrun em comprimento, chegamos à frente e pegamos o suficiente de outros elementos para completar a execução, em seguida, usar o Insertion Sort para empurrá-los para o nosso array ordenado, rápido e fácil. Obviamente, se uma corrida encontrar o fim da matriz você pode deixá-lo um pouco curto.

Depois de ter criado todas as suas corridas (isto é, subarrays ordenados), utiliza o seu Merge Sort para juntá-las. Em um melhor cenário, a matriz inteira já está ordenada e Tim Sort é inteligente o suficiente para saber que não precisa fazer mais nada. Outras vezes, tende a ser extremamente eficiente. Como um benefício adicionado, tanto a ordenação de inserção e a ordenação de junção são estáveis, então a matriz resultante é estável.

para aqueles que preferem balas:

1. Estabelecer um minrun tamanho é uma potência de 2 (normalmente 32, nunca mais do que 64 ou sua Inserção Classificar vai perder eficiência)
2. Encontrar em primeira minrun de dados.
3. Se a execução não for pelo menos minrun em comprimento, use Insertion Sort para pegar itens subsequentes ou anteriores e inseri-los na execução até que seja o tamanho mínimo correto.
4. Repeat until the entire array is divided into tried subsections.
5. Use a última metade do Merge Sort para se juntar às arrays ordenadas.

conclusão

TIM Sort é poderoso. É rápido e estável, mas talvez mais importante que ele tira vantagem dos padrões do mundo real e utiliza-os para construir um produto final. É para todas as situações? Provavelmente não. Boa sorte programá-lo em um quadro branco durante uma entrevista, e se você só precisa de um algoritmo de ordenação simples rápido em uma pitada você provavelmente não quer se preocupar em implementar algo deste complexo. No entanto, para os cientistas de dados que acumulam números é mais do que vale a pena olhar.

para os curiosos, você pode verificar todo o código de ordenação Tim no github.obrigado a todos os meus leitores. Agradeço o seu tempo, e espero sinceramente que tenha achado o conteúdo informativo. Se você tiver alguma pergunta ou resposta sinta-se livre para deixar um abaixo.