Strand sort

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 (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

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

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[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++:

#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.