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 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 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 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 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: F merge_list(&a, &b) [Int] out L !a.empty & !b.empty I a < b 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++: #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: 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))));
Ligações externas Paul E. Black "Strand Sort" do Dictionary of Algorithms and Data Structures no NIST.
Categoria:Algoritmos de ordenação