Strand sort

Strand sort je algoritam za sortiranje koji radi tako što konstantno izvlači sortirane podnizove iz niza koji treba sortirati i spaja ih u rezultujući niz. Svaka iteracija kroz nesortirani niz izvlači elemente koji su već sortirani i spaja ih.

Ime algoritma potiče od lanaca sortiranih podataka u nizu koji treba sortirati i koji se izvlače iz niza jedan po jedan. Ovo je algoritam baziran na poređenjima, s obzirom na upotrebu poređenja prilikom izvlačenja lanaca i njihovog spajanja u sortiran niz.

Složenost algoritma je O(n²) u prosečnom slučaju. U najboljem slučaju (kada je niz već sortiran) složenost je linearna tj. O(n). U najgorem slučaju (kada je niz obrnuto sortiran) složenost je O(n²).

Strand sort je najkorisniji kod podataka koji se čuvaju u povezanoj listi, zbog čestih umetanja i izvlačenja podataka. Korišćenje drugačije strukture podataka, kao što je niz, dosta povećava vreme izvršavanja i složenost algoritma zbog dužine niza. Ovaj algoritam je koristan i u situacijama kada imamo veliku količinu već sortiranih podataka jer te podatke možemo da izvučemo u jedan lanac.

Primer

Nesortiran niz	Podniz	Sortiran niz
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. Iz nesortiranog niza izdvajamo rastuće brojeve.
2. U prvoj iteraciji sortirani podniz smeštamo u prazan sortiran niz.
3. Iz nesortiranog niza ponovo izdvajamo relativno sortirane brojeve.
4. Pošto je sortiran niz popunjen, spajamo podniz u sortiran niz.
5. Ponavljati korake 3-4 dok oba niza nisu prazna.

Algoritam

Pseudokod:

procedure strandSort(A : niz ) defined as:
  while length(A ) > 0
    clear podniz
    podniz[ 0 ] := A[ 0 ]
    remove A[ 0 ]
    for each i in 0 to length(A ) - 1 do:
      if A[ i ] > podniz[ last ] then
        append A[ i ] to podniz
        remove A[ i ]
      end if
    end for
    merge podniz into rezultat
  end while
  return rezultat
end procedure

Haskell implementacija

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)

PHP implementacija

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

Python implementacija

items = len(unsorted)
sortedBins = []
while(len(unsorted) > 0 ):
    highest = float("-inf")
    newBin = []
    i = 0
    while(i < len(unsorted) ):
        if(unsorted[i] >= highest ):
            highest = unsorted.pop(i)
            newBin.append(highest )
        else:
            i=i+1
    sortedBins.append(newBin)

sorted = []
while(len(sorted) < items ):
    lowBin = 0
    for j in range(0, len(sortedBins) ):
        if(sortedBins[j][0] < sortedBins[lowBin][0] ):
            lowBin = j
    sorted.append(sortedBins[lowBin].pop(0) )
    if(len(sortedBins[lowBin]) == 0 ):
        del sortedBins[lowBin]

Reference

• Paul E. Black "Strand Sort" from Dictionary of Algorithms and Data Structures at NIST.