algoritmos de ordenação são formas de organizar uma matriz de itens de menor a maior. Estes algoritmos podem ser usados para organizar dados bagunçados e torná-lo mais fácil de usar. Além disso, ter uma compreensão desses algoritmos e como eles funcionam é fundamental para uma forte compreensão da ciência da computação que está se tornando cada vez mais crítica em um mundo de pacotes premade. Este blog foca na velocidade, usos, vantagens e desvantagens de algoritmos de ordenação específicos.,
embora exista uma grande variedade de algoritmos de ordenação, este blog explica inserção direta, Shell Sort, Bubble Sort, Quick Sort, Selection Sort, e Heap Sort. Os dois primeiros algoritmos (Straight Insertion e Shell Sort) ordenam arrays com inserção, que é quando os elementos são inseridos no lugar certo. Os próximos 2 (Bubble Sort e Quick Sort) ordenam arrays com troca, que é quando os elementos se movem em torno do array. O último é heap sort que ordena através da seleção onde os elementos certos são selecionados como o algoritmo corre para baixo da matriz.,
notação Big-O
antes deste blog ir mais longe, é essencial explicar os métodos que os profissionais usam para analisar e avaliar a complexidade e desempenho do algoritmo. O padrão atual é chamado ” notação O Grande “nomeado de acordo com sua notação que é um” O “seguido por uma função como” O(n).”
definição Formal
Big O é usado para denotar a complexidade de tempo de um algoritmo ou quanto espaço ele ocupa. Este blog se concentra principalmente na parte de complexidade de tempo desta Notação., A forma como as pessoas podem calcular isso é identificando o pior caso para o algoritmo alvo e formulando uma função de seu desempenho dado uma quantidade n de elementos. Por exemplo, se houvesse um algoritmo que buscasse o número 2 em um array, então o pior caso seria se o 2 estivesse no final do array. Portanto, a notação de O Grande seria O(n) Uma vez que teria que correr através de toda a matriz de elementos n Antes de encontrar o número 2.
para ajudá-lo, Encontre abaixo uma tabela com algoritmos e sua complexidade.,
Direto de Inserção Sort
Direto de inserção de classificação é uma das mais básicas algoritmos de ordenação que, essencialmente, insere um elemento na posição correta de uma lista ordenada. Ele é normalmente adicionado no final de uma nova matriz e se move para baixo até que ele encontra um elemento menor agradecer a si mesmo (a posição desejada). O processo se repete para todos os elementos da matriz não Triada. Considere o array {3,1,2,5,4}, nós começamos em 3, e como não há outros elementos no array ordenado, o array ordenado torna-se apenas {3}., Depois, inserimos 1, que é menor que 3, para que ele se movesse na frente de 3 Fazendo o array {1,3}. Este mesmo processo é repetido ao longo da linha até que tenhamos a matriz {1,2,3,4,5}.
As vantagens deste processo são que ele é simples e fácil de implementar. Além disso, é relativamente rápido quando há pequenas quantidades de elementos para classificar. Ele também pode se transformar em inserção binária, que é quando você compara em distâncias mais longas e reduzi-lo para o ponto certo em vez de comparar com cada elemento antes do lugar certo., No entanto, um tipo de inserção reta é geralmente lento sempre que a lista se torna grande.
Principais Características:
- tipo de Inserção da família
- Direto e simples
- Pior caso = O(n^2)
Python implementação:
> Shell Sort
classificação de Shell é a inserção de um tipo que, primeiro parcialmente classifica seus dados e, em seguida, termina o tipo executando a inserção de um algoritmo de ordenação em toda a matriz. Ele geralmente começa escolhendo pequenos subconjuntos do array e separando esses arrays., Depois disso, ele repete o mesmo processo com subconjuntos maiores até chegar a um ponto onde o subconjunto é a matriz, e toda a coisa se torna ordenada. A vantagem de fazer isso é que ter a matriz quase inteiramente ordenada ajuda a inserção final sort alcançar ou estar perto de seu cenário mais eficiente.
além disso, o aumento do tamanho dos subconjuntos é alcançado através de um termo incremental decrescente. O termo incremental essencialmente escolhe cada elemento kth para colocar no subconjunto., Ele começa grande, levando a grupos menores (mais espalhados), e torna-se menor até que se torna 1 (todo o array).
A principal vantagem deste algoritmo de ordenação é que ele é mais eficiente do que um tipo de inserção regular. Além disso, há uma variedade de algoritmos diferentes que procuram otimizar a shell sort alterando a forma como o incremento diminui, uma vez que a única restrição é que o último termo na sequência de incrementos é 1. O mais popular é geralmente o método de Knuth que usa a fórmula h=((3^k) -1) / 2 dando-nos uma sequência de intervalos de 1 (k=1), 4 (k=2), 13 (k=3), e assim por diante., Por outro lado, shell sort não é tão eficiente quanto outros algoritmos de ordenação, como quicksort e merge sort.
Principais Características:
- a Ordenação por inserção
- Pode otimizar o algoritmo alterando incrementos
- Usando Knuth método, o pior caso é O(n^(3/2))
Python implementação:
Bubble Sort
classificação de Bolha compara elementos adjacentes de uma matriz e organiza esses elementos. Seu nome vem do fato de que grandes números tendem a “flutuar” (bolha) para o topo., Ele faz loops através de um array e vê se o número em uma posição é maior do que o número na posição seguinte, o que resultaria no número se movendo para cima. Este ciclo se repete até que o algoritmo tenha passado pelo array sem ter que mudar a ordem. Este método é vantajoso porque é simples e funciona muito bem para a maioria das listas ordenadas. Como resultado, os programadores podem implementar rápida e facilmente este algoritmo de ordenação. Entretanto, o tradeoff é que este é um dos algoritmos de ordenação mais lentos.,
Principais Características:Exchange sortingEasy para implementWorst Caso = O(n^2)
Python implementação:
Quicksort
o Quicksort é um dos mais eficientes algoritmos de classificação, e isso faz dele um dos mais bem utilizado.A primeira coisa a fazer é selecionar um número pivô, este número irá separar os dados, em sua esquerda são os números menores do que ele e os números maiores da direita. Com isto, temos toda a sequência particionada.,Depois que os dados são particionados, podemos garantir que as partições são orientadas, sabemos que temos valores maiores à direita e valores menores à esquerda.O quicksort usa este algoritmo de dividir para conquistar com recursão. Então, agora que temos os dados divididos usamos recursão para chamar o mesmo método e passar a metade esquerda dos dados, e depois a metade direita para manter a separação e ordenação dos dados. No final da execução, teremos os dados todos ordenados.,
Principais características:
- a Partir de uma família de Troca de Algoritmos de Classificação
- Dividir e conquistar paradigma
- Pior caso, complexidade O(n2)
Python implementação:
Heapsort
o Heapsort é um algoritmo de classificação com base na estrutura de uma pilha. O heap é uma estrutura de dados especializada encontrada em uma árvore ou um vector.In a primeira etapa do algoritmo, uma árvore é criada com os valores a serem ordenados, começando da esquerda, nós criamos o nó raiz, com o primeiro valor., Agora criamos um nó-filho esquerdo e inserimos o próximo valor, neste momento avaliamos se o valor definido para o nó-filho é maior do que o valor no nó-raiz, se sim, alteramos os valores. Fazemos isto a toda a árvore. A idéia inicial é que os nós-mãe sempre têm valores maiores do que os nós-filhos.
no final do primeiro passo, Criamos um vetor começando com o valor raiz e caminhando da esquerda para a direita preenchendo o vetor.,
agora começamos a comparar os valores dos nós pai e filho procurando o maior valor entre eles, e quando o encontramos, mudamos de lugar reordenando os valores. No primeiro passo, comparamos o nó raiz com a última folha da árvore. Se o nó raiz é maior, então nós mudamos os valores e continuamos a repetir o processo até que a última folha seja o valor maior. Quando não há mais valores para reorganizar, adicionamos a última folha ao vetor e reiniciamos o processo. Podemos ver isso na imagem abaixo.,
As características principais do algoritmo são:
- a Partir de uma família de ordenação por seleção
- Comparações no pior caso = O(n log n)
- Não estável
Python implementação:
Referência: o Quão rápido eles são?
após o desenvolvimento dos algoritmos é bom para nós testar quão rápido eles podem ser. Nesta parte desenvolvemos um programa simples usando o código acima para gerar uma referência básica, apenas para ver quanto tempo eles podem usar para classificar uma lista de inteiros.,Observações importantes sobre o código:
- Python limite de chamada recursiva padrão é 1.000, neste teste estamos usando números grandes, então precisamos melhorar esse número para executar a referência sem erros. O limite foi fixado em 10.000.
- este código apenas mede o tempo de execução de cada algoritmo.foi realizado 20 testes com diferentes tamanhos de listas variando entre 2500 e 50000.
- os números foram gerados randomly variando de 1 a 10000.,Os resultados são os seguintes: Shell sort e Heap Sort algoritmos realizados bem, apesar do comprimento das listas, no outro lado nós descobrimos que inserção sort e Bubble sort algoritmos foram muito piores, aumentando em grande parte o tempo de computação. Veja os resultados no gráfico abaixo.
conclusão
neste post, mostramos 5 dos algoritmos de ordenação mais comuns usados hoje. Antes de usar qualquer um deles é extremamente importante saber quão rápido ele corre e quanto espaço vai usar. Então é a troca entre complexidade, velocidade e volume., Outra característica crítica dos algoritmos de ordenação que são importantes para saber é a sua estabilidade. A estabilidade significa que o algoritmo mantém a ordem dos elementos com valores-chave iguais. O melhor algoritmo muda para cada conjunto de dados diferentes e, como resultado, compreender os nossos dados desempenha um papel significativo no processo de escolha do algoritmo certo.
Como podemos ver, compreender os nossos dados desempenha um papel muito importante no processo de escolha do algoritmo certo.,
Se este post chamou a sua atenção, dê uma olhada no vídeo abaixo, ele lhe dará uma explicação concisa sobre 15 algoritmos de ordenação.
Big O Notation – https://en.wikipedia.org/wiki/Big_O_notation
Knuth, Donald Ervin, 1938 – A arte da programação de computadores / Donald Ervin Knuth. xiv, 782 p. 24 cm.,d=”a5b60f8536″>
Quicksort – https://commons.wikimedia.org/wiki/File:Quicksort.gif
Quicksort – http://interactivepython.org/courselib/static/pythonds/SortSearch/TheQuickSort.html
Heapsort Algorithm – https://en.wikipedia.org/wiki/Heapsort
Heapsort Algorithm – https://www.geeksforgeeks.org/heap-sort/
Bubble sort – http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html
Sedgewick, R.,, & Wayne, K. (2011). Algorithms, 4th Edition. (p. I–XII, 1-955). Addison-Wesley. – https://algs4.cs.princeton.edu/20sorting/
Sorting algorithms – https://brilliant.org/wiki/sorting-algorithms/
