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
Iz nesortiranog niza izdvajamo rastuće brojeve. U prvoj iteraciji sortirani podniz smeštamo u prazan sortiran niz. Iz nesortiranog niza ponovo izdvajamo relativno sortirane brojeve. Pošto je sortiran niz popunjen, spajamo podniz u sortiran niz. 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] < sortedBins[lowBin] ): 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.
Референце
Категорија:Алгоритми сортирања