Странд сорт

Странд сорт је алгоритам за сортирање који ради тако што константно извлачи сортиране поднизове из низа који треба сортирати и спаја их у резултујући низ. Свака итерација кроз несортирани низ извлачи елементе који су већ сортирани и спаја их.

Име алгоритма потиче од ланаца сортираних података у низу који треба сортирати и који се извлаче из низа један по један. Ово је алгоритам базиран на поређењима, с обзиром на употребу поређења приликом извлачења ланаца и њиховог спајања у сортиран низ.

Сложеност алгоритма је О(н²) у просечном случају. У најбољем случају (када је низ већ сортиран) сложеност је линеарна тј. О(н). У најгорем случају (када је низ обрнуто сортиран) сложеност је О(н²).

Странд сорт је најкориснији код података који се чувају у повезаној листи, због честих уметања и извлачења података. Коришћење другачије структуре података, као што је низ, доста повећава време извршавања и сложеност алгоритма због дужине низа. Овај алгоритам је користан и у ситуацијама када имамо велику количину већ сортираних података јер те податке можемо да извучемо у један ланац.

Пример

Несортиран низ	Подниз	Сортиран низ
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. Из несортираног низа издвајамо растуће бројеве.
2. У првој итерацији сортирани подниз смештамо у празан сортиран низ.
3. Из несортираног низа поново издвајамо релативно сортиране бројеве.
4. Пошто је сортиран низ попуњен, спајамо подниз у сортиран низ.
5. Понављати кораке 3-4 док оба низа нису празна.

Алгоритам

Псеудокод:

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

Хаскелл имплементација

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)

ПХП имплементација

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

Пyтхон имплементација

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]

Референце

• Паул Е. Блацк "Странд Сорт" фром Дицтионарy оф Алгоритхмс анд Дата Струцтурес ат НИСТ.