Dropsort

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 Kent

Níž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

1.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

1.int i,j;i=j=INT_MIN;while(scanf("%d",&j)!=EOF)if(j>=i)printf("%d",j),i=j;

Popis algoritmu

Analýza

Zdroje

Kód

Doporučujeme