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
	Esta caixa: ver; discutir;

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 (n²).

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]))

^[1]

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; }

^[1]

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)))); 	} }

^[1]

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.

[:0-1] «Sorting algorithms/Strand sort - Rosetta Code». rosettacode.org. Consultado em 24 de setembro de 2021

[1]