Algoritmo de ordenação

enquanto há um grande número de algoritmos de ordenação, em implementações práticas alguns algoritmos predominam. Insertion sort é amplamente usado para pequenos conjuntos de dados, enquanto para grandes conjuntos de dados um sort assintoticamente eficiente é usado, principalmente heap sort, merge sort, ou quicksort. Implementações eficientes geralmente usam um algoritmo híbrido, combinando um algoritmo assintoticamente eficiente para a ordenação geral com a ordenação de inserção para pequenas listas na parte inferior de uma recursão., Sintonizados implementações de uso mais sofisticado de variantes, tais como Timsort (merge sort, inserção de classificação, e lógica adicional), utilizado em Android, Java, e Python, e introsort (quicksort e heap de ordenação), em formas variantes) em alguns C++ classificar implementações e em .LÍQUIDA.

Para mais restrito de dados, tais como números em um intervalo fixo, tipo de distribuição, tais como a contagem de ordenação ou de base de classificação são amplamente utilizados. Bubble sort e variantes são raramente usados na prática, mas são comumente encontrados no ensino e discussões teóricas.,

Quando se seleccionam objectos fisicamente (tais como trabalhos alfabetizados, testes ou livros), as pessoas geralmente usam tipos de inserção para pequenos conjuntos. Para conjuntos maiores, as pessoas muitas vezes primeiro balde, como por letra inicial, e vários bucketing permite a triagem prática de conjuntos muito grandes. Muitas vezes o espaço é relativamente barato, como espalhando objetos no chão ou sobre uma grande área, mas as operações são caras, particularmente movendo um objeto uma grande distância – localidade de referência é importante., Merge sorts também são práticos para objetos físicos, particularmente como duas mãos podem ser usadas, uma para cada lista para mesclar, enquanto outros algoritmos, como heap sort ou quick sort, são inadequados para uso humano. Outros algoritmos, como o library sort, uma variante do insertion sort que deixa espaços, também são práticos para uso físico.

sortsEdit simples

dois dos tipos mais simples são o tipo de inserção e o tipo de seleção, ambos os quais são eficientes em pequenos dados, devido à baixa sobrecarga, mas não eficientes em grandes dados., Insertion sort é geralmente mais rápido do que selection sort na prática, devido a menos comparações e bom desempenho em dados quase ordenados, e assim é preferido na prática, mas selection sort usa menos escritas, e assim é usado quando o desempenho de escrita é um fator limitante.

Inserção sortEdit

ver artigo Principal: Inserção de classificação

Inserção sort é um algoritmo de classificação simples que é relativamente eficiente para pequenas listas e, principalmente, listas ordenadas, e é usado normalmente como parte de algoritmos mais sofisticados., Ele funciona pegando elementos da lista um a um e inserindo-os em sua posição correta em uma nova lista ordenada semelhante à forma como colocamos dinheiro em nossa carteira. Em arrays, a nova lista e os restantes elementos podem compartilhar o espaço da array, mas a inserção é cara, requerendo mudar todos os seguintes elementos por um. Shellsort (veja abaixo) é uma variante de insertion sort que é mais eficiente para listas maiores.

sortEdit de selecção

artigo principal: Selection sort

Selection sort is an in-place comparison sort., Tem complexidade O (n2), tornando-o ineficiente em grandes listas, e geralmente executa pior do que o tipo de inserção similar. Selection sort é conhecido por sua simplicidade, e também tem vantagens de desempenho sobre algoritmos mais complicados em certas situações.

o algoritmo encontra o valor mínimo, troca-o com o valor na primeira posição, e repete estes passos para o resto da lista. Ele não faz mais do que n swaps, e, portanto, é útil onde troca é muito caro.,

sortsEdit eficiente

algoritmos práticos de ordenação geral são quase sempre baseados em um algoritmo com complexidade de tempo médio (e geralmente complexidade de pior caso) O(n log n), dos quais os mais comuns são heap sort, merge sort, e quicksort. Cada um tem vantagens e desvantagens, com o mais significativo sendo que a simples implementação do merge sort usa o(n) espaço adicional, e a simples implementação do quicksort tem a complexidade do pior caso(n2). Estes problemas podem ser resolvidos ou melhorados ao custo de um algoritmo mais complexo.,

embora estes algoritmos sejam assintoticamente eficientes em dados aleatórios, para a eficiência prática em dados do mundo real várias modificações são usadas. Primeiro, a sobrecarga destes algoritmos torna-se significativa em dados menores, então muitas vezes um algoritmo híbrido é usado, comumente mudando para a ordenação de inserção uma vez que os dados são pequenos o suficiente. Em segundo lugar, os algoritmos frequentemente executam mal em dados já ordenados ou quase ordenados – estes são comuns em dados do mundo real, e podem ser ordenados em tempo O(n) por algoritmos apropriados., Finalmente, eles também podem ser instáveis, e a estabilidade é muitas vezes uma propriedade desejável em uma espécie. Assim, algoritmos mais sofisticados são frequentemente empregados, como Timsort (baseado no merge sort) ou introsort (baseado no quicksort, caindo de volta para heap sort).

Merge sortEdit

artigo principal: Merge sort

Merge sort tira partido da facilidade de junção de listas já ordenadas numa nova lista ordenada. Ele começa por comparar cada dois elementos (ou seja, 1 com 2, Depois 3 com 4…) e trocá-los se o primeiro deve vir após o segundo., Ele então mescla cada uma das listas resultantes de duas em listas de quatro, então mescla essas listas de quatro, e assim por diante; até que finalmente duas listas são mescladas na lista ordenada final. Dos algoritmos descritos aqui, este é o primeiro que escala bem para listas muito grandes, porque seu pior caso de tempo de execução é O(n log n). Ele também é facilmente aplicado a listas, não apenas arrays, pois só requer acesso sequencial, Não acesso aleatório. No entanto, tem complexidade de espaço o(n) adicional, e envolve um grande número de cópias em implementações simples.,

Merge sort tem visto um aumento relativamente recente na popularidade para implementações práticas, devido ao seu uso no sofisticado algoritmo Timsort, que é usado para a rotina padrão sort nas linguagens de programação Python e Java (a partir de JDK7). Merge sort em si é a rotina padrão em Perl, entre outros, e tem sido usado em Java pelo menos desde 2000 em JDK1.3.

HeapsortEdit

artigo principal: Heapsort

Heapsort é uma versão muito mais eficiente do tipo de selecção., Ele também funciona ao determinar o maior (ou o menor) elemento da lista, colocando que no final (ou início) da lista e, em seguida, continuar com o resto da lista, mas realiza esta tarefa de forma eficiente usando uma estrutura de dados chamada de uma pilha, um tipo especial de árvore binária. Uma vez que a lista de dados foi feita em um heap, o nó raiz é garantido para ser o maior (ou menor) elemento. Quando ele é removido e colocado no final da lista, o heap é rearranjado de modo que o maior elemento restante se move para a raiz., Usando o heap, encontrar o próximo maior elemento leva O (log n) Tempo, em vez de O(n) para uma varredura linear como em uma simples ordenação de seleção. Isto permite que o Heapsort seja executado em tempo O (n log n), e esta também é a pior complexidade do caso.

QuicksortEdit

artigo principal: Quicksort

Quicksort é um algoritmo de divisão e conquista que depende de uma operação de partição: para partição de uma matriz, um elemento chamado pivô é selecionado. Todos os elementos menores que o pivô são movidos antes dele e todos os elementos maiores são movidos depois dele. Isto pode ser feito de forma eficiente em tempo linear e no local., As sublistas menores e maiores são então ordenadas recursivamente. Isto produz uma complexidade média de tempo de O (n log n), com baixa sobrecarga, e assim este é um algoritmo popular. Implementações eficientes de quicksort (com particionamento in-place) são tipicamente tipos instáveis e um pouco complexos, mas estão entre os algoritmos de ordenação mais rápidos na prática. Juntamente com seu modesto uso de espaço o(log n), quicksort é um dos algoritmos de ordenação mais populares e está disponível em muitas bibliotecas de programação padrão.,

a importante advertência sobre quicksort é que seu pior desempenho é O (n2); enquanto isso é raro, em implementações ingênuas (escolhendo o primeiro ou último elemento como pivô) isso ocorre para dados ordenados, que é um caso comum. A questão mais complexa no quicksort é, portanto, escolher um bom elemento pivô, uma vez que escolhas consistentemente pobres de pivots podem resultar em um desempenho o(n2) drasticamente mais lento, mas uma boa escolha de pivô produz o(n log n) Desempenho, que é assintoticamente ótimo. Por exemplo, se em cada passo a mediana é escolhida como o pivô, então o algoritmo funciona em O(n log n)., Encontrar a mediana, tal como pela mediana do algoritmo de seleção de medians é, no entanto, uma operação O(n) em listas não triadas e, portanto, exige sobrecarga significativa com a ordenação. Na prática, escolher um pivô Aleatório quase certamente produz O (n log n) Desempenho.

ShellsortEdit

um Shell sort, diferente do bubble sort na medida em que move elementos para várias posições de troca.

rtigo principal: Shell sort

Shellsort foi inventado por Donald Shell em 1959., Melhora com a ordenação de inserção, deslocando-se de elementos de ordem mais de uma posição de cada vez. O conceito por trás do Shellsort é que o insertion sort executa no tempo o ( k n ) {\displaystyle o(kn)}, onde k é a maior distância entre dois elementos fora de lugar. Isto significa que geralmente, eles executam em o (n2), mas para os dados que são ordenados principalmente, com apenas alguns elementos fora do lugar, eles executam mais rápido. Então, pela primeira triagem de elementos longe, e progressivamente diminuindo a diferença entre os elementos para classificar, a ordenação final computa muito mais rápido., Uma implementação pode ser descrita como organizando a sequência de dados em um array bidimensional e, em seguida, ordenando as colunas do array usando sort de inserção.

o pior caso de complexidade de tempo de Shellsort é um problema aberto e depende da sequência de gap usada, com complexidades conhecidas que variam de O(n2) A O(n4/3) e Θ (n log2 n)., Isso, combinado com o fato de que o Shellsort está no lugar, só precisa de uma quantidade relativamente pequena de código, e não requer o uso da pilha de chamadas, torna-o útil em situações em que a memória está em um prêmio, como em sistemas embarcados e núcleos de Sistema Operacional.

Bubble sort e variantsEdit

esta secção não cita quaisquer fontes. Por favor, ajude a melhorar esta seção adicionando citações a fontes confiáveis. O material não recolhido pode ser desafiado e removido., (May 2019) (Learn how and when to remove this template message)

Bubble sort, and variants such as the shell sort and cocktail sort, are simple, highly ineficient sorting algorithms. Eles são frequentemente vistos em textos introdutórios devido à facilidade de análise, mas eles são raramente utilizados na prática.

Bubble sortEdit

um bubble sort, um algoritmo de ordenação que passa continuamente através de uma lista, trocando itens até que eles aparecem na ordem correta.,

artigo principal: Bubble sort

Bubble sort é um algoritmo de ordenação simples. O algoritmo começa no início do conjunto de dados. Compara os dois primeiros elementos e, se o primeiro for maior que o segundo, troca-os. Ele continua fazendo isso para cada par de elementos adjacentes até o final do conjunto de dados. Em seguida, começa novamente com os dois primeiros elementos, repetindo até que não tenham ocorrido trocas no último passe. O tempo médio e o pior desempenho deste algoritmo é O (n2), por isso raramente é usado para ordenar conjuntos de dados grandes e não ordenados., Bubble sort pode ser usado para classificar um pequeno número de itens (onde sua ineficiência assintótica não é uma penalidade alta). Bubble sort também pode ser usado eficientemente em uma lista de qualquer comprimento que é quase ordenado (ou seja, os elementos não estão significativamente fora do lugar). Por exemplo, se qualquer número de elementos estão fora de lugar por apenas uma posição (por exemplo, 0123546789 e 1032547698), a troca de bubble sort irá colocá-los em ordem na primeira passagem, a segunda passagem irá encontrar todos os elementos em ordem, de modo que o sort levará apenas 2n tempo.,

Comb sortEdit

artigo principal: Comb sort

Comb sort é um algoritmo de ordenação relativamente simples baseado no bubble sort e originalmente projetado por Włodzimierz Dobosiewicz em 1980. Mais tarde foi redescoberto e popularizado por Stephen Lacey e Richard Box com um artigo da revista Byte publicado em abril de 1991. A idéia básica é eliminar tartarugas, ou pequenos valores perto do final da lista, uma vez que em uma bolha Ordenar estes retardam a classificação tremendamente., (Coelhos, grandes valores em torno do início da lista, não representam um problema no bubble sort) ele consegue isso, inicialmente trocando elementos que são uma certa distância um do outro na matriz, em vez de apenas trocar elementos se eles são adjacentes um ao outro, e, em seguida, encolhendo a distância escolhida até que ele está operando como uma bolha normal sort. Assim, se Shellsort pode ser pensado como uma versão generalizada de insertion sort que troca elementos espaçados a uma certa distância um do outro, comb sort pode ser pensado como a mesma generalização aplicada ao bubble sort.,

distribuição sortEdit

Ver também: ordenação externa

distribuição sort refere-se a qualquer algoritmo de ordenação onde os dados são distribuídos a partir da sua entrada para múltiplas estruturas intermediárias que são então recolhidas e colocadas na saída. Por exemplo, tanto o bucket sort quanto o flashsort são algoritmos de ordenação baseados na distribuição. Algoritmos de ordenação de distribuição podem ser usados em um único processador, ou eles podem ser um algoritmo distribuído, onde subconjuntos individuais são separados em diferentes processadores, então combinados., Isso permite a triagem externa de dados muito grande para caber na memória de um único computador.

Contagem sortEdit

artigo principal: Contagem ordenação

Contagem ordenação é aplicável quando se sabe que cada entrada pertence a um determinado conjunto, S, de possibilidades. O algoritmo roda em tempo O (|S| + n) e memória o (|s/), onde n é o comprimento da entrada. Ele funciona criando um array inteiro de tamanho / S| e usando a ith bin para contar as ocorrências do ith membro de S na entrada. Cada entrada é então contabilizada aumentando o valor da sua caixa correspondente., Depois disso, o array de contagem é looped através para organizar todas as entradas em ordem. Este algoritmo de ordenação muitas vezes não pode ser usado porque S precisa ser razoavelmente pequeno para que o algoritmo seja eficiente, mas é extremamente rápido e demonstra um grande comportamento assintótico como n aumenta. Ele também pode ser modificado para fornecer um comportamento estável.

Bucket sortEdit

artigo principal: Bucket sort

Bucket sort é um algoritmo de ordenação de divisão e conquista que generaliza a contagem ordenando uma matriz em um número finito de buckets., Cada balde é então ordenado individualmente, usando um algoritmo de ordenação diferente,ou aplicando recursivamente o algoritmo de ordenação de balde.um balde de sorte funciona melhor quando os elementos do conjunto de dados são distribuídos uniformemente em todos os baldes.

radix sortEdit

artigo principal: Radix sort

Radix sort é um algoritmo que ordena números por processamento de dígitos individuais. n números que consistem em K dígitos cada um são ordenados em o (n · k) tempo., O radix sort pode processar dígitos de cada número, começando a partir do dígito menos significativo (LSD) ou começando a partir do dígito mais significativo (MSD). O algoritmo LSD primeiro ordena a lista pelo dígito menos significativo, preservando sua ordem relativa usando uma ordenação estável. Em seguida, classifica-os pelo dígito seguinte, e assim por diante, do menos significativo para o mais significativo, terminando com uma lista ordenada. Enquanto a ordenação do LSD radix requer o uso de uma ordenação estável, o algoritmo de ordenação do MSD radix não (a menos que a ordenação estável seja desejada). O radix sort in-place não é estável., É comum que o algoritmo de ordenação de contagem seja usado internamente pelo tipo radix. Uma abordagem de triagem híbrida, como o uso do insertion sort para pequenos contentores, melhora significativamente o desempenho do radix sort.

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *