Mind map
Algoritmos para Ordenação

Mapa mental: Algoritmos para Ordenação
Map content
Algoritmos para Ordenação
Os dados devem ser armazenados obedecendo uma determinada ordem. Alguns algoritmos podem explorar a ordenação dos dados para operar de maneira mais eficiente, do ponto de vista de desempenho computacional. Para obtermos os dados ordenados, temos basicamente duas alternativas: ou inserimos os elementos na estrutura de dados respeitando a ordenação (dizemos que a ordenação é garantida por construção), ou, a partir de um conjunto de dados já criado, aplicamos um algoritmo para ordenar seus elementos.
DISTRIBUIÇÃO: Radix Sort
- É um algoritmo de ordenação rápido e estável que pode ser usado para ordenar itens que estão identificados por chaves únicas. Cada chave é uma cadeia de caracteres ou número, e o radix sort ordena estas chaves numa qualquer ordem relacionada com a lexicografia.
- Classificações
- radix sort LSD (Least significant digit/Dígito menos significativo)
- Começa do dígito menos significativo até o mais significativo, ordenando tipicamente da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Isso coincide com a ordem normal de representação dos inteiros, como a seqüência "1, 2, 3, 4, 5, 6, 7, 8, 9, 10".
- radix sort MSD (Most significant digit/Dígito mais significativo)
- Trabalha no sentido contrário, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo. A seqüência "b, c, d, e, f, g, h, i, j, ba" será ordenada lexicograficamente como "b, ba, c, d, e, f, g, h, i, j". Se essa ordenação for usada para ordenar representações de inteiros com tamanho variável, então a representação dos números inteiros de 1 a 10 terá a saída "1, 10, 2, 3, 4, 5, 6, 7, 8, 9".
- radix sort LSD (Least significant digit/Dígito menos significativo)
SELEÇÃO / SELECTION SORTS
- Selection sort
- É um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os n-1 elementos restantes, até os últimos dois elementos.
- Heapsort
- É um algoritmo de ordenação generalista.Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Não é um algoritmo de ordenação estável. Porém, é possível adaptar a estrutura a ser ordenada de forma a tornar a ordenação estável. Utiliza uma estrutura de dados chamada heap, para ordenar os elementos à medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, lembrando-se sempre de manter a propriedade de max-heap. A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais) ou como um vetor.
- Smoothsort
- É um algoritmo de ordenação de ordenação por comparação. É uma variação do heapsort. O array a ser ordenado é dividido em uma string de heaps, cada heap com um tamanho igual a um dos números de Leonardo L(n). O processo de divisão é simples - os nós mais à esquerda do array são feitos no maior heap possível, e o restante é dividido igualmente.
- Cartesian tree sort
- Tournament sort
- Introsort
- Selection sort
TROCA / EXCHANGE SORTS
- Bubble sort
- Ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, e a cada passagem fazer flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
- Cocktail sort
- Também conhecido como Shaker Sort, bubble sort bidirecional (que também pode se referir a uma variante do selection sort), ripple sort, shuttle sort ou happy hour sort, é uma variação do bubble sort que é tanto um algoritmo de ordenação estável quanto uma ordenação por comparação. O algoritmo difere do bubble sort pelo fato de ordenar em ambas as direções em cada passagem através da lista. Este algoritmo de ordenação é apenas ligeiramente mais difícil de implementar do que o bubble sort, e resolve o problema com os chamados coelhos e tartarugas no bubble sort.
- Odd-even sort
- É um algoritmo de ordenação relativamente simples. É um algoritmo de ordenação por comparação baseado no bubble sort com o qual compartilha muitas características. Ele funciona através da comparação de todos os pares indexados (ímpar, par) de elementos adjacentes na lista e, se um par está na ordem errada (o primeiro é maior do que o segundo), os elementos são trocados. O próximo passo repete isso para os pares indexados (par, ímpar) (de elementos adjacentes). Em seguida, ele alterna entre etapas de (ímpar, par) e (par, ímpar) até que a lista é ordenada. Pode ser pensado como a utilização de processadores paralelos, cada qual usando um BubbleSort, mas a partir de diferentes pontos na lista (todos os índices ímpares para a primeira etapa). Este algoritmo de ordenação é apenas ligeiramente mais difícil do que o bubble sort para implementar.
- Comb sort
- Ou Combo sort ou ainda algoritmo do pente é um algoritmo de ordenação relativamente simples. O Comb sort melhora o Bubble sort, e rivaliza com algoritmos como o Quicksort. A ideia básica é eliminar as tartarugas ou pequenos valores próximos do final da lista, já que em um bubble sort estes retardam a classificação tremendamente. (Coelhos, grandes valores em torno do início da lista, não representam um problema no bubble sort). O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente.
- Gnome sort
- Algoritmo similiar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma seqüencia grande de trocas assim como o Bubble sort. O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.
- Quicksort
- É um método de ordenação muito rápido e eficiente. Adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.
- Shake-sort
- Ou método da coqueteleira Melhoramento do bubble-sort
- Bubble sort
MISTURA ou INTERCALAÇÃO / MERGE SORTS
- Merge sort
- É um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar. Sua ideia básica consiste em Dividir (o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar (após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas). Como o algoritmo Merge Sort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas.
- Strand sort
- É um algoritmo de ordenação. Ele trabalha por repetidas vezes extraindo sublistas ordenadas da lista a ser classificada e mesclando-as com um array resultado. Cada iteração através da lista não-ordenada extrai uma série de elementos que já estavam ordenados, e mescla as séries juntas. O Strand sort é mais útil para dados que são armazenados em uma lista vinculada, devido às freqüentes inserções e remoções de dados.
- Timsort
- É um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do mundo real. Exige muito menos do que log²(n!), porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação Python, e tem sido o algoritmo de ordenação padrão de Python desde a versão 2.3. Ele atualmente é usado para ordenar arrays em Java SE 7.
- In-place Merge sort
- Merge sort
INSERÇÃO / INSERTION SORTS
- Insertion Sort
- É o algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação.
- Shell sort
- É o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção.
- Binary Tree sort
- Utiliza uma árvore binária de busca: Todo nó à esquerda é menor do que o nó pai; Todo nó à direita é maior do que o nó pai. O pior caso pode ser evitado se a árvore estiver balanceada.
- Library sort
- Patience sorting
- Cycle Sort
- Insertion Sort
OUTROS
- Topological sorting
- Sorting network
- Bitonic sorter
- Batcher odd-even mergesort
- Pancake sorting
- Bucket-sort
- Ou método do balde.
SORTE/LUCKY (INEFICIENTES / HUMORÍSTICOS)
- Bogosort
- Também conhecido como CaseSort ou Estou com Sort, é um algoritmo de ordenação extremamente ineficiente. É baseado na reordenação aleatória dos elementos. Não é utilizado na prática, mas pode ser usado no ensino de algorítmos mais eficientes. Esse algoritmo é probabilístico por natureza. Se todos os elementos a serem ordenados são distintos, a complexidade esperada é O(n x n!). O tempo exato de execução esperado depende do quantos diferentes valores de elementos ocorrem, e quantas vezes cada um deles ocorre, mas para casos não-triviais o tempo esperado de execução é exponencial ou super-exponencial a n. Ele termina pela mesma razão do teorema do macaco infinito; existe alguma probabilidade de que aconteça a permutação correta, dado que em um infinito número de tentativas fatalmente a encontrará.
- Stooge sort
- Ou ordenação "fantoche", é um algoritmo de ordenação que se faz do uso das técnicas de divisão e conquista, ou seja, recursivamente o algoritmo realiza partições virtuais da entrada e transforma o problema maior em pequenos subproblemas até que a ordenação seja mínima. Comparado a outros algoritmos de ordenação mais conhecidos, como o Insertion Sort e o Bubble Sort, ele chega a ser mais lento. Devido à sua ineficiência, recomenda-se que não seja usado na ordenação de grandes volumes de dados. O nome do algoritmo faz referência a uma comédia norte-americana chamada The Three Stooges (em português, Os Três Patetas), em que Moe batia repetidamente nos outros dois patetas, assim como o Stooge Sort repetidamente ordena 2/3 do array.
- Bogosort
PARTICIONAMENTO / Partitioning
Operação realizada sobre registros.
Objetivo: Organizar os registros sob determinada ordem.
Information
- Description
- Base Computacional Mind Map on Algoritmos para Ordenação, created by Marina Micas Jardim on 04/09/2017.
- Created by
- Marina Micas Jardim
- Views
- 0
- History
-
- Created by Marina Micas Jardim · Aug 18, 2017
- Copied by Marina Micas Jardim · Aug 28, 2017
- Copied by Marina Micas Jardim · Sep 4, 2017
- Rating
More on Algoritmos de ordenação