Strand sort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
← nova página: {{em tradução}} {{Info/Algoritmo |classe =Algoritmo de ordenação |imagem = |estrutura =Array, Listas ligadas |data ... |
|||
Linha 16:
O '''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 nome do algoritmo vem de "vertentes" de dados ordenados dentro da lista não-ordenada que são removidos um de cada vez. É um algoritmo de [[ordenação por comparação]] devido ao seu uso de comparações, quando remove vertentes e ao mesclar-los para o array ordenado.
<!--▼
▲<!--
The strand sort algorithm is [[Big-O notation|O]](''n'' sqrt ''n'') in the average case. In the best case (a list which is already sorted) the algorithm is linear, or O(''n'').
Linha 24:
Strand sort is most useful for data which is stored in a linked list, due to the frequent insertions and removals of data. Using another data structure, such as an array, would greatly increase the running time and complexity of the algorithm due to lengthy insertions and deletions. Strand sort is also useful for data which already has large amounts of sorted data, because such data can be removed in a single strand.
-->▼
== Exemplo ==
Linha 45 ⟶ 47:
|}
# Analisar a lista não-ordenada uma vez, tirando quaisquer números ordenados de forma ascendente.
# A sublista ordenada é, para a primeira iteração, inserida na lista ordenada vazia.
# Analisar a lista não-ordenada novamente e novamente tirando números ordenados relativamente.
# Desde que a lista ordenada está agora populada, mesclar as sublistas na lista ordenada.
# Repetir os passos 3-4 até que tanto a lista não-ordenada e as sublistas estejam vazias.
▲-->
== Algoritmo ==
| |||