Föreläsning 8: Sortering

• Urvalssortering (Selection sort)
• Bubbelsortering (Bubble sort)
• Insättningssortering (Insertion sort)
• Shellsort (uppfunnen av Donald Shell)
• Damerna först
• Quicksort
• Samsortering (Mergesort)
• Distributionsräkning (Distribution count)
• Trappsortering (Heapsort)
• Radixsortering

Urvalssortering (Selection sort)

• Sök igenom vektorn efter minsta talet. (N-1 jämförelser)
• Flytta det till första positionen. (Ett byte)
• Sök efter näst minsta talet. (N-2 jämförelser)
• Flytta det till andra positionen. (Ett byte) - - -

Bubbelsortering (Bubble sort)

• Byt första och andra om dom står i fel ordning. (En jämförelse, ett byte)
• Byt andra och tredje om dom står i fel ordning. (En jämförelse, ett byte) - - -
• Bubbla igenom vektorn gång på gång tills inga byten sker.

Insättningssortering (Insertion sort)

• Jämför nya talet med sista talet i vektor.
• Om nya är större, lägg det sist i vektorn.
• Annars, putta ner sista talet ett pinnhål och jämför igen.
• Putta ner så många tal som behövs för att sätta in nya talet på rätt plats.
• Upprepa för varje nytt tal.

Komplexiteten är i allmänhet O(N²) men för att sortera in ett nytt värde i en redan sorterad vektor är insättning den snabbaste algoritmen.

"Insättningssortering av vektorn a"

# Först finns bara a[0], sedan insätts a[1], sedan a[2] osv.
# Om a[j] som sätts in bör ligga på plats a[i] måste alla
# mellanliggande element a[i]...a[j-1] puttas ett steg.

for j in range(1,len(a)):
    aj=a[j]
    i=j
    while i>0 and aj<a[i-1]:
        a[i]=a[i-1]
        i=i-1
    a[i]=aj

Shellsort

Idén är att man sorterar vart h:te element för en serie minskande h-värden (som måste avslutas med h=1).

"Shellsort av vektorn a"

# Jämför med insättningssortering!
h = len(a)//2 
while h>0: 
    for j in range(h,len(a)):
        aj = a[j]
        i = j
        while i>0 and aj<a[i-h]:
            a[i] = a[i-h]
            i=i-h
        a[i]=aj
    if h==2: h=1
    else: h=int(h/2.2)

Damerna först

1. Sätt ett pekfinger i var ände av arrayen!
2. Rör fingrarna mot varandra tills vänstra fingret fastnat på en herre och högra fingret på en dam!
3. Låt damen och herren byta plats!
4. Upprepa från 2 tills fingrarna korsats!

Quicksort

• Bestäm vilka värden som ska kallas damer.
• Partitionera vektorn så att damerna kommer först.
• Sortera varje segment för sej.

Komplexiteten blir i allmänhet O(N log N). Det beror på att man kan dela vektorn på mitten log N gånger. Exakt hur snabb den är beror på hur man avgör vilka värden som ska vara damer. Ofta tar man det första talet i vektorn och utnämner det och alla mindre tal till damer. Då blir Quicksort mycket långsam för redan nästan sorterade vektorer! Det bästa är att ta ut tre tal - 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.

Samsortering (Mergesort)

• Dela vektorn i två hälften så långa vektorer.
• Sortera varje halva för sej.
• Samsortera till ursprungliga vektorn.

def mergesort(a,left,right):
    if left+1<right:
        center = (left + right)//2
        mergesort(a,left,center)
        mergesort(a,center,right)
        merge(a,left,center,right)

def merge(a,left,center,right):
    b[left:right]=a[left:right]
    i=left
    j=center
    k=left
    while i<center and j<right:
        if b[i]<b[j]:
            a[k]=b[i]
            i=i+1
        else:
            a[k]=b[j]
            j=j+1
        k=k+1
    if i==center:
        while j<right:
            a[k]=b[j]
            j=j+1
            k=k+1
    else:
        while i<center:
            a[k]=b[i]
            i=i+1
            k=k+1

Distributionsräkning (Distribution count)

• Läs igenom filen och räkna hur många det finns av varje nyckelvärde.
• Dela in vektorn i lagom stora segment för denna distribution.
• Läs filen igen och lägg in varje värde i sitt segment.

Heapsort

"Heapsort av orden på en fil"

  heap = Heap(16)               
  for ord in open("bibel.txt").read().split():
      heap.put(ord,ord)
  while not heap.isempty():
      print heap.get()   

Radixsortering

Nu är det ju inte frågan om hålkortsbuntar längre utan snarare om vektorer i minnet. Sorteringen kan då göras med distributionsräkning, eftersom det i varje sortering bara finns tio olika nyckelvärden.

Det går lika bra att sortera strängar, enda skillnaden är att det finns tjugonio nyckelvärden i varje sortering. En sträng kan ju uppfattas som ett tal skrivet med basen 29 och siffrorna A-Ö. Radix betyder just bas i ett talsystem.

Sortering av större mängder data