Strand sort – Wikipédia, a enciclopédia livre
Strand sort | |
---|---|
classe | Algoritmo de ordenação |
estrutura de dados | Array, Listas ligadas |
complexidade pior caso | |
complexidade caso médio | |
complexidade melhor caso | |
otimo | ? |
Algoritmos | |
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.
O algoritmo de ordenação strand é O(n sqrt n) no caso médio. No melhor caso (a lista que já está classificado), o algoritmo é linear, ou O(n). Na pior das hipóteses (a lista que está ordenada em ordem inversa), o algoritmo é O (n2).
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. Usando uma outra estrutura de dados, como um array, se aumentaa consideravelmente o tempo de execução e a complexidade do algoritmo, devido às longas inserções e deleções. O Strand sort também é útil para dados que já possuem grandes quantidades de dados ordenados, pois esses dados podem ser removidos em uma única vertente.
Exemplo
[editar | editar código-fonte]Lista não-ordenada | Sublista | Lista ordenada |
---|---|---|
3 1 5 4 2 | ||
1 4 2 | 3 5 | |
1 4 2 | 3 5 | |
2 | 1 4 | 3 5 |
2 | 1 3 4 5 | |
2 | 1 3 4 5 | |
1 2 3 4 5 |
- 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
[editar | editar código-fonte]Uma maneira simples de expressar o strand sort, em pseudocódigo é como se segue:
procedure strandSort( A : list of sortable items ) defined as: while length( A ) > 0 clear sublist sublist[ 0 ] := A[ 0 ] remove A[ 0 ] for each i in 0 to length( A ) do: if A[ i ] > sublist[ last ] then append A[ i ] to sublist remove A[ i ] end if end for merge sublist into results end while return results end procedure
Implementação em Haskell
[editar | editar código-fonte]merge [] l = l merge l [] = l merge l1@(x1:r1) l2@(x2:r2) = if x1 < x2 then x1:(merge r1 l2) else x2:(merge l1 r2) ssort [] = [] ssort l = merge strand (ssort rest) where (strand, rest) = foldr extend ([],[]) l extend x ([],r) = ([x],r) extend x (s:ss,r) = if x <= s then (x:s:ss,r) else (s:ss,x:r)
Implementação em PHP
[editar | editar código-fonte]function strandsort(array $arr) { $result = array(); while (count($arr)) { $sublist = array(); $sublist[] = array_shift($arr); $last = count($sublist)-1; foreach ($arr as $i => $val) { if ($val > $sublist[$last]) { $sublist[] = $val; unset($arr[$i]); $last++; } } if (!empty($result)) { foreach ($sublist as $val) { $spliced = false; foreach ($result as $i => $rval) { if ($val < $rval) { array_splice($result, $i, 0, $val); $spliced = true; break; } } if (!$spliced) { $result[] = $val; } } } else { $result = $sublist; } } return $result; }
Implementação em Python:
[editar | editar código-fonte]F merge_list(&a, &b) [Int] out L !a.empty & !b.empty I a[0] < b[0] out.append(a.pop(0)) E out.append(b.pop(0)) out [+]= a out [+]= b R out F strand(&a) V i = 0 V s = [a.pop(0)] L i < a.len I a[i] > s.last s.append(a.pop(i)) E i++ R s F strand_sort(&a) V out = strand(&a) L !a.empty out = merge_list(&out, &strand(&a)) R out print(strand_sort(&[1, 6, 3, 2, 1, 7, 5, 3]))
Implementação em C++:
[editar | editar código-fonte]#include <list> template <typename T> std::list<T> strandSort(std::list<T> lst) { if (lst.size() <= 1) return lst; std::list<T> result; std::list<T> sorted; while (!lst.empty()) { sorted.push_back(lst.front()); lst.pop_front(); for (typename std::list<T>::iterator it = lst.begin(); it != lst.end(); ) { if (sorted.back() <= *it) { sorted.push_back(*it); it = lst.erase(it); } else it++; } result.merge(sorted); } return result; }
Implementação em Java:
[editar | editar código-fonte]import java.util.Arrays; import java.util.LinkedList; public class Strand{ // note: the input list is destroyed public static <E extends Comparable<? super E>> LinkedList<E> strandSort(LinkedList<E> list){ if(list.size() <= 1) return list; LinkedList<E> result = new LinkedList<E>(); while(list.size() > 0){ LinkedList<E> sorted = new LinkedList<E>(); sorted.add(list.removeFirst()); //same as remove() or remove(0) for(Iterator<E> it = list.iterator(); it.hasNext(); ){ E elem = it.next(); if(sorted.peekLast().compareTo(elem) <= 0){ sorted.addLast(elem); //same as add(elem) or add(0, elem) it.remove(); } } result = merge(sorted, result); } return result; } private static <E extends Comparable<? super E>> LinkedList<E> merge(LinkedList<E> left, LinkedList<E> right){ LinkedList<E> result = new LinkedList<E>(); while(!left.isEmpty() && !right.isEmpty()){ //change the direction of this comparison to change the direction of the sort if(left.peek().compareTo(right.peek()) <= 0) result.add(left.remove()); else result.add(right.remove()); } result.addAll(left); result.addAll(right); return result; } public static void main(String[] args){ System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,1,2,4,5)))); System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,3,1,2,4,5)))); System.out.println(strandSort(new LinkedList<Integer>(Arrays.asList(3,3,1,2,4,3,5,6)))); } }
Referências
- ↑ a b c «Sorting algorithms/Strand sort - Rosetta Code». rosettacode.org. Consultado em 24 de setembro de 2021
Ligações externas
[editar | editar código-fonte]- Paul E. Black "Strand Sort" do Dictionary of Algorithms and Data Structures no NIST.