Strand sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Strand sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso O(n^2)
complexidade caso médio O(n * sqrt(n))
complexidade melhor caso O(n)
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
  1. Analisar a lista não-ordenada uma vez, tirando quaisquer números ordenados de forma ascendente.
  2. A sublista ordenada é, para a primeira iteração, inserida na lista ordenada vazia.
  3. Analisar a lista não-ordenada novamente e novamente tirando números ordenados relativamente.
  4. Desde que a lista ordenada está agora populada, mesclar as sublistas na lista ordenada.
  5. 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;
}

Ligações externas[editar | editar código-fonte]