|
def urvalssortera(data):
n = len(data)
for i in range(n):
minst = i
for j in range(i+1,n):
if data[j] < data[minst]:
minst = j
data[minst],data[i] = data[i], data[minst]
|
Urvalssorteringsanimation från Hong Kongs universitet.
Bubbelsortanimation från universitetet i Oldenburg.
Komplexiteten är i allmänhet O(N2) men den är lite snabbare än urvalssortering i praktiken eftersom en flytt är snabbare än ett byte. För att sortera in ett nytt värde i en redan sorterad lista är insättning bäst.
|
def insattningssortera(data):
n = len(data)
for i in range(1, n):
varde = data[i]
plats = i
while plats > 0 and data[plats-1] > varde:
data[plats] = data[plats-1]
plats = plats - 1
data[plats] = varde
|
Animation av insättningssortering från Indian Institute of Technology i Kanpur.
def quicksort(data):
sista = len(data) - 1
qsort(data, 0, sista)
def qsort(data, i, j):
pivotindex = (i+j)/2
data[pivotindex], data[j] = data[j], data[pivotindex]
k = partitionera(data, i-1, j, data[j])
data[k], data[j] = data[j], data[k]
if k-i > 1:
qsort(data, i, k-1)
if j-k > 1:
qsort(data, k+1, j)
def partitionera(data, v, h, pivot):
while True:
v = v + 1
while data[v] < pivot:
v = v + 1
h = h -1
while h != 0 and data[h] > pivot:
h = h -1
data[v], data[h] = data[h], data[v]
if v >= h: break
data[v], data[h] = data[h], data[v]
return v
Komplexiteten blir i allmänhet O(N log N). Det beror på att man kan dela listan på mitten log N gånger. Exakt hur snabb den är beror på hur man avgör vilka värden som ska vara damer. Om man tar det första värdet i listan och utnämner det och alla mindre värden till damer, så blir Quicksort mycket långsam för redan nästan sorterade listor! Det bästa är att ta ut tre värden - det första, det sista och något i mitten - och låta det mellersta värdet bestämma vad som är damer. Det kallas median-of-three. Man kan visa att komplexiteten då blir 1.4 N log N i genomsnitt.
Quicksortanimation från Aucklands universitet.
def mergesort(data):
if len(data) > 1:
mitten = len(data)/2
vensterHalva = data[:mitten]
hogerHalva = data[mitten:]
mergesort(vensterHalva)
mergesort(hogerHalva)
i, j, k = 0, 0, 0
while i < len(vensterHalva) and j < len(hogerHalva):
if vensterHalva[i] < hogerHalva[j]:
data[k] = vensterHalva[i]
i = i + 1
else:
data[k] = hogerHalva[j]
j = j + 1
k = k + 1
while i < len(vensterHalva):
data[k] = vensterHalva[i]
i = i + 1
k = k + 1
while j < len(hogerHalva):
data[k] = hogerHalva[j]
j = j + 1
k = k + 1
Mergesortanimation från North Carolina State University.
Inom datalogi används detta uttryck för att beskriva en lösningsmetod där man delar upp ett problem i två eller flera delproblem och löser dessa var för sig. Delproblemen löses enklast med rekursion!
Quicksort och mergesort är två exempel på divide-and-conquer-principen.
| 3 | 4 | 3 | 3 | 5 | 3 | 5 | 3 | 5 | 4 | 5 | 3 | 4 |
| 3 | 3 | 3 | 4 |
I en prioritetskö stämplas en prioritet på varje objekt som stoppas in och vid uthämtning får man objektet med högst prioritet.
En abstrakt prioritetskö kan ha föjande anrop.
put(p,x)
x = get()
isEmpty()
put(x).
Hur den då skiljer sej från en stack och
från en vanlig kö ser man av följande exempel.
pq.put(1)
pq.put(3)
pq.put(2)
x = pq.get() # x blir 3
En kö hade skickat tillbaka det först instoppade talet 1;
en stack hade skickat tillbaka det senast instoppade talet, 2;
prioritetskön skickar tillbaka det bästa talet, 3.
I denna prioritetskö betraktar vi största talet som bäst - vi har en så
kallad maxprioritetskö. Det finns förstås också minprioritetsköer, där
det minsta talet betraktas som bäst.
Prioritetsköer har många användningar. Man kan tänka sej en auktion där
budgivarna stoppar in sina bud i en maxprioritetskö och auktionsförrättaren efter
"första, andra, tredje" gör pq.get() för att få reda på det
vinnande budet.
För att han ska veta vem som lagt detta bud behövs förstås båda
parametrarna i pq.put(p,x).
pq.put(bud,person) #person är ett objekt med budgivarens namn och bud
winner = pq.get() #budgivaren med högst bud
tab tolkad som binärträd.
Roten är tab[1] (vi använder inte tab[0], dess båda barn är
tab[2] och tab[3] osv. Allmänt
gäller att tab[i] har barnen
tab[2*i] och tab[2*i+1].
Trappvillkoret är att föräldern är bäst, dvs varje tal ligger
på två sämre tal.
Ett nytt tal läggs alltid in sist i trappan. Om trappvillkoret inte blir
uppfyllt, dvs om det är större än sin förälder,
byter förälder och barn plats och
så fortgår det tills villkoret uppfyllts. Det här kallas
upptrappning och kan i värsta fall föra det nya talet
hela vägen upp till toppen, alltså tab[1].
Man plockar alltid ut det översta talet ur trappan och fyller igen tomrummet med det sista talet i trappan. Då är inte trappvillkoret uppfyllt, så man får byta talet och dess största barn. Denna nedtrappning upprepas tills villkoret åter gäller.
Både put och get har komplexitet log N
om trappan har N element. Nackdelen med trappan är man måste
bestämma listans storlek från början.
Här följer en rudimentär implementation av en max-heap:
class HeapNode:
def __init__(self, data, priority):
"""data är det objekt vi vill lagra
priority är nyckelvärdet som används för att jämföra objekten"""
self.data = data
self.priority = priority
class Heap:
# En max-heap
def __init__(self, maxsize):
"""Skapar en lista där vi använder element 1..maxsize"""
self.maxsize = maxsize
self.tab = (maxsize+1)*[None]
self.size = 0
def isEmpty(self):
"""Returnerar True om heapen är tom, False annars"""
return self.size == 0
def isFull(self):
"""Returnerar True om heapen är full, False annars"""
return self.size == self.maxsize
def put(self, data, priority):
"""Lägger in nya data med nyckeln priority i heapen"""
if not self.isFull():
self.size += 1
self.tab[self.size] = HeapNode(data, priority)
i = self.size
while i > 1 and self.tab[i//2].priority < self.tab[i].priority:
self.tab[i//2], self.tab[i] = self.tab[i], self.tab[i//2]
i = i//2
def get(self):
"""Hämtar det största (översta) objektet ur heapen"""
if not self.isEmpty():
data = self.tab[1]
self.tab[1] = self.tab[self.size]
self.size -= 1
i = 1
while i <= self.size//2:
maxi = self.maxindex(i)
if self.tab[i].priority < self.tab[maxi].priority:
self.tab[i],self.tab[maxi] = self.tab[maxi], self.tab[i]
i = maxi
return data.data
else:
return None
def maxindex(self, i):
"""Returnerar index för det största barnet"""
if 2*i+1 > self.size:
return 2*i
if self.tab[2*i].priority > self.tab[2*i+1].priority:
return 2*i
else:
return 2*i+1
heap = Heap(16)
for word in open("folksagor.txt").read().split():
heap.put(word, word)
while not heap.isempty():
print heap.get()
Heapsortanimation från Aucklands universitet.
Det här är exempel på en girig algoritm, där man i varje steg väljer den väg som verkar bäst för stunden, utan att reflektera över vad konsekvenserna blir i längden. Ofta ger giriga algoritmer inte den bästa lösningen, men i just det här fallet fungerar det faktiskt! Algoritmen kallas Dijkstra's algoritm (efter den holländske datalogen Edsger W. Dijkstra) och att den fungerar bevisas i fortsättningskursen DD1352 Algoritmer, datastrukturer och komplexitet.
Exempel 1: Sök billigaste transport från Teknis till
Honolulu. All världens resprislistor finns tillgängliga.
Problemträdets objekt innehåller en plats, ett pris och en
förälderpekare. Överst i trädet står Teknis med priset noll. Barnen
är alla platser man kan komma till med en transport och priset, till exempel
T-centralen, 20.00. Man söker en Honoluluobjekt i problemträdet.
Med breddenförstsökning får man den resa som har så få transportsteg som
möjligt.
Med bästaförstsökning får man den billigaste resan.
Exempel 2: Sök effektivaste processen för att framställa
en önskad substans från en given substans. All världens kemiska
reaktioner finns tillgängliga med uppgift om utbytet i procent.
Problemträdets objekt innehåller substansnamn och procenttal. Överst i
trädet står utgångssubstansen med procenttalet 100. Barnen är alla
substanser man kan framställa med en reaktion och utbytet, till
exempel C2H5OH, 96%.
Med en max-prioritetskö får man fram den effektivaste process som leder till målet.