Light Mode

Ir para o conteudo

Strand sort

Origem: Wikipedia, a enciclopedia livre.
Strand sort
ClasseAlgoritmo de ordenacao
Estrutura de dadosArray, Listas ligadas
Complexidade pior caso O ( n 2 ) {\displaystyle O(n^{2})}
Complexidade caso medio O ( n * s q r t ( n ) ) {\displaystyle O(n*sqrt(n))}
Complexidade melhor caso O ( n ) {\displaystyle O(n)}
Otimo?

O Strand sort e um algoritmo de ordenacao. Ele trabalha por repetidas vezes extraindo sublistas ordenadas da lista a ser classificada e mesclando-as com um array resultado. Cada iteracao atraves da lista nao-ordenada extrai uma serie de elementos que ja estavam ordenados, e mescla as series juntas.

O nome do algoritmo vem de "vertentes" de dados ordenados dentro da lista nao-ordenada que sao removidos um de cada vez. E um algoritmo de ordenacao por comparacao devido ao seu uso de comparacoes, quando remove vertentes e ao mesclar-los para o array ordenado.

O algoritmo de ordenacao strand e O(n sqrt n) no caso medio. No melhor caso (a lista que ja esta classificado), o algoritmo e linear, ou O(n). Na pior das hipoteses (a lista que esta ordenada em ordem inversa), o algoritmo e O (n2).

O Strand sort e mais util para dados que sao armazenados em uma lista vinculada, devido as frequentes insercoes e remocoes de dados. Usando uma outra estrutura de dados, como um array, se aumentaa consideravelmente o tempo de execucao e a complexidade do algoritmo, devido as longas insercoes e delecoes. O Strand sort tambem e util para dados que ja possuem grandes quantidades de dados ordenados, pois esses dados podem ser removidos em uma unica vertente.

Lista nao-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
  1. Analisar a lista nao-ordenada uma vez, tirando quaisquer numeros ordenados de forma ascendente.
  2. A sublista ordenada e, para a primeira iteracao, inserida na lista ordenada vazia.
  3. Analisar a lista nao-ordenada novamente e novamente tirando numeros ordenados relativamente.
  4. Desde que a lista ordenada esta agora populada, mesclar as sublistas na lista ordenada.
  5. Repetir os passos 3-4 ate que tanto a lista nao-ordenada e as sublistas estejam vazias.

Algoritmo

[editar | editar codigo]

Uma maneira simples de expressar o strand sort, em pseudocodigo e 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

Implementacao em Haskell

[editar | editar codigo]
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)

Implementacao em PHP

[editar | editar codigo]
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;
}

Implementacao em Python:

[editar | editar codigo]
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]

Implementacao em C++:

[editar | editar codigo]
#include

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]

Implementacao em Java:

[editar | editar codigo]
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]

Referencias

  1. | a b c <>. rosettacode.org. Consultado em 24 de setembro de 2021

Ligacoes externas

[editar | editar codigo]