Strand sort

Из Википедије, слободне енциклопедије
Jump to navigation Jump to search

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(n2) 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(n2).

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[уреди]

Референце[уреди]