Dropsort, navržený Davidem Morganem-Marem, je rychlý řadící algoritmus s jedním průchodem, vhodný pro různá nasazení.
Popis algoritmu
Dropsort se spouští na řazení seznamu čísel, které prozkoumává v sekvenci, počínaje druhým číslem ze seznamu. Pokud je číslo menší než předcházející, pak jej ze seznamu odstraní. V opačném případě je ve správném pořadí, takže jej ponechá. Pak se přesune na další číslo. Po jednom průchodu algoritmem obsahuje seznam pouze čísla, která jsou alespoň tak velká jako předchozí číslo v seznamu. Jinými slovy, seznam bude setříděn!
Analýza
Dropsort vyžaduje přesně n-1 porovnání k seřazení sezanmu o délce n, což z něj dělá algoritmus O(n), tedy lepší než typické algoritmy O(n logn), standardně používané pro seřazení.
Dropsort je algoritmus, známý jako ztrátový algoritmus. Vytváří rychlé výsledky, které jsou správné, ale s velkou pravděpodobností ztrácí vstupní data. I když se může zdát, že v počítačových vědách je ztrátový algoritmus nežádoucí, přesto jsou ztrátové algoritmy velmi přijatelnou částí počítačových věd. Příkladem může být populární kompresní obrazový formát JPEG, těšící se velké popularitě. Stejně tak si i dropsort nárokuje své místo na slunci v podobě třídění dat na poli finančnictví, záznamů dat pro vládu a výzkum vesmíru.
Zdroje
Jeremy Kent implementoval Dropsort! Tedy, ne zcela. Dle jeho vlastních slov:
Toto je implementace třídícího algoritmu s využitím DropSort. Volám Dropsort, ovšem nechávám si odstraněné hodnoty, pak seznam těchto hodnot převrátím a opět rekurzivně volám DropSort. (Protože cokoliv, co nebylo seřazeno od nejmenšího po největší musí být logicky seřazeno od největšího po nejmenší).
Jeremy KentNíže uvádíme jak Kentův kód v Pythonu, tak i nejkratší implemetace DropSortu v jiných jazycích.
Kód
## DropSort algorithm
## O(n log n) -- good constants for data with some ordering;
## bad for randomly-distributed data
##
## (c)2009 Jeremiah Kent
## ibiwan@gmail.com
##
## inspired by David Morgan-Mar's Dropsort algorithm,
## found at http://www.dangermouse.net/esoteric/dropsort.html
class stats:
def __init__(self):
self.comparisons = 0; self.copies = 0; self.merges = 0
def __str__(self):
return (str(self.comparisons) + " comparisons; " +
str(self.copies) + " copies; " +
str(self.merges) + " merges")
_ = "bookkeeping lines"
def merge(amy, ben, stats):
_ ;stats.merges += 1
Carrington = []; a = 0; b = 0 #init
lena = len(amy); lenb = len(ben) #memoize
while(a < lena and b < lenb): #merge
_ ;stats.comparisons += 1
if(amy[a] <= ben[b]):
_ ;stats.copies += 1
Carrington.append(amy[a]); a += 1
else:
_ ;stats.copies += 1
Carrington.append(ben[b]); b += 1
_ ;stats.copies += 1
#leftovers (O(1) with linked lists)
Carrington.extend(amy[a:lena])
Carrington.extend(ben[b:lenb])
return Carrington
def dropsort(lst, stats):
if(len(lst)<2): return lst #base case
up = []; dn = []; prev = None #init
for i in lst:
_ ;stats.comparisons += 1
if(prev is None or i >= prev):
_ ;stats.copies += 1
up.append(i); prev = i
else:
_ ;stats.copies += 1
#prepend (O(1) with linked lists)
dn.insert(0, i)
return merge(up, dropsort(dn, stats), stats)
#implemented for comparison
def mergesort(lst, stats):
if(len(lst)<2): return lst
mid = len(lst)/2
return merge(mergesort(lst[:mid], stats),
mergesort(lst[mid:], stats), stats)
#use drop sort for the first two recursion levels in case there's already ordered data, then merge remainder
def hybrid(lst, stats, stage = 0):
if(len(lst)<2): return lst #base case
if(stage > 1): return mergesort(lst, stats)
up = []; dn = []; prev = None #init
for i in lst:
_ ;stats.comparisons += 1
if(prev is None or i >= prev):
_ ;stats.copies += 1
up.append(i); prev = i
else:
_ ;stats.copies += 1
#prepend (O(1) with linked lists)
dn.insert(0, i)
return merge(up, hybrid(dn, stats, stage + 1), stats)
#assumes values in range [0, 1)
def printsort(lst, name = None):
if(not name is None): print name
for i in lst: print " "*int(i*80), i
print
Testovací příklad: Input Output 1 2 5 4 3 7 1 2 5 7 10 -1 12 10 12 -7 -8 -5 0 -1 1 -7 -5 0 1 9 8 7 6 5 9 10 13 17 21 10 13 17 21 10 10 10 9 10 10 10 10 10
f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))
//Abusing of the standard type conversion in javascript, array to number:
//
// array of just 1 number => that number
//
// any other array => NaN
//--------------------------------------------------------
d=l=>l.filter(v=>l>v?0:[l=v])
// TEST
console.log=x=>O.innerHTML+=x+'\n'
;[
[[1,2,5,4,3,7], [1,2,5,7]]
, [[10,-1,12], [10,12]]
, [[-7,-8,-5,0,-1,1], [-7,-5,0,1]]
, [[9,8,7,6,5], [9]]
, [[10,13,17,21], [10,13,17,21]]
, [[10,10,10,9,10], [10,10,10,10]]
].forEach(t=>( i=t[0],r=d(i),x=t[1],
console.log('Test '+i+' -> '+r+(r+''==x+''?' OK':' Fail (expected '+x+')')))
)
void f(int[]a){int m=a[0];for(int n:a){System.out.print(m>n?"":n+" ");m=n>m?n:m;}}
//Here's a simple output loop. It just keeps the max in m and compares each element.
$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge //If additional spaces are acceptable in the output, can be 31 bytes by removing and ?. Accepts a string (or number of newline separated) strings via STDIN: perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '-7 -8 -5 0 -1 1' -7 -5 0 1 perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '10 10 10 9 10' 10 10 10 10
int i,j;i=j=INT_MIN;while(scanf("%d",&j)!=EOF)if(j>=i)printf("%d",j),i=j;