Please enable JavaScript.
Coggle requires JavaScript to display documents.
Gustavo Bottega Falcão - Coggle Diagram
Gustavo Bottega Falcão
SmoothSort
Criado por Edsger Dijkstra em 1981. E foi feito para ser eficiente e simples, garantindo uma classificação estável. Seu nome vem da sua habilidade de suavizar a lista enquanto a ordena
utiliza uma estrutura especial chamada Heap, que é uma árvore binária. Cada nó da árvore possui um valor maior ou igual aos valores dos seus nós filhos
permite que o Smoothsort organize os elementos de forma eficiente, sem a necessidade de comparações diretas entre eles
Durante a construção do Heap, os elementos são inseridos na estrutura em qualquer ordem. No entanto, a propriedade do Heap garante que o maior elemento esteja sempre no topo da árvore, que é o nó raiz
Heap Property
algoritmo usa um procedimento chamado "downheap" (descida). Esse procedimento compara o valor de um nó com o valor dos seus filhos e, se necessário, troca os elementos de posição para manter a propriedade do Heap
A descida ocorre recursivamente em direção aos nós folhas do Heap até que toda a estrutura esteja corretamente ordenada
é especialmente útil quando a lista já está um pouco organizada ou quando é importante manter a ordem dos elementos estável
Aplicações
Processamento de dados científicos
1 more item...
Algoritmos de busca
1 more item...
Bancos de dados
1 more item...
Aplicações que exigem estabilidade
1 more item...
Smoothsort:
https://en.wikipedia.org/wiki/Smoothsort
Introduction to Smooth Sort:
https://www.geeksforgeeks.org/introduction-to-smooth-sort/
Pacience Sorting
utiliza uma estrutura de dados que são chamados pilhas de paciência. No começo, todas as cartas são colocadas em uma pilha vazia. Em seguida, as cartas são percorridas uma a uma e colocadas na pilha onde formarão uma subsequência ordenada. Se uma carta não se encaixar em nenhuma pilha existente, uma nova pilha é criada. Após todas as cartas serem colocadas nas pilhas, elas são combinadas de forma a obter a sequência final ordenada.
Aplicação
:fire:
Possui um desempenho eficiente onde a sequência a ser ordenada contém sub-sequências ordenadas longas. Porém, seu desempenho pode ser prejudicado em sequências com muitas sub-sequências pequenas ou desordenadas.
não é amplamente utilizado em linguagens de programação ou sistemas de gerenciamento de banco de dados (SGBDs) populares. Isso ocorre porque existem outros algoritmos de ordenação mais eficientes em termos de tempo de execução, como o Quicksort e o Mergesort
Utilizado em jogos de cartas, onde é necessário ordenar as cartas nas mãos dos jogadores
<-- Teste de mesa: Ele separa a sequencia de números digitadas em subsequências quando os números já estão meio ordenados. Depois ao final, ele junta as subsequências, assim criando a sequencia final ordenada
Digite as cartas separadas por vírgula: 1,2,3,5,8,6,9,5,6,7,8
Cartas ordenadas:
[1, 2, 3, 5, 5, 6, 6, 7, 8, 8, 9]
Subsequências:
[1, 2, 3]
[5]
[5, 6]
[6, 7, 8]
[8, 9]
RSNarayanan, P. "Patience Sorting." GeeksforGeeks. (
https://www.geeksforgeeks.org/patience-sorting/
:)
https://en.wikipedia.org/wiki/Patience_sorting
