Föreläsning 7: Sortering

• Urvalssortering (Selection sort)
• Bubbelsortering (Bubble sort)
• Insättningssortering (Insertion sort)
• Damerna först
• Quicksort
• Samsortering (Mergesort)
• Söndra och härska
• Distributionsräkning (Distribution count)
• 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)
- - -

def urvalssortera(data):
    n=len(data)
    for i in range(n):
        min=i
        for j in range(i+1,n):
            if data[j]<data[min]:
                min=j
        temp=data[min]
        data[min]=data[i]
        data[i]=temp

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.

"Insättningssortering av vektorn a"

def insattnssortera(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

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.

def sattin(x, data, sista):
    i=sista
    if x>data[i]:
        data[i+1]=x
    else:
        while i>=0 and x<data[i]:
            data[i+1]=data[i]
            i-=1
        data[i+1] = x

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.

def swap(data, first, second):
    temp = data[first]
    data[first] = data[second]
    data[second] = temp

def quicksort(data):  # metoden som anropas utifrån
    qs(data, 0, len(data))

def qs(data, first, last):
    pivot = partition(data, first, last)
    swap(data, first, pivot)
    if first+1 < pivot:
        qs(data, first, pivot-1)
    if pivot+1 < last:
        qs(data, pivot+1, last)

def partition(data, first, last): # damerna först
    x=data[first]
    i=first
    j=last-1
    while True:
        while j>=first and data[j]>x:
            j=j-1
        while i<last and data[i]<=x:
            i=i+1
        if i<j:
            swap(data, i, j)
        else:
            return j

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):
    ms(a, 0, len(a))

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

def merge(a,left,center,right):
    b=len(a)*[None]
    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

Söndra och härska

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 sedan på samma sätt - rekursion!

Quicksort och mergesort är två väldigt tydliga exempel på divide-and-conquer-principen.

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.

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

Tentatal 000603: NIX-Telefon

För konsumenter som inte vill ha marknadsföringssamtal: Ring 020-27 70 00!

Föreningen för konsumentskydd vid marknadsföring per telefon har startat ett register dit den som inte vill bli uppringd av telefonförsäljare kan anmäla sig.

Till att börja kommer kontrollen att ske genom att företaget sänder sin telefonlista till nix och får tillbaka en lista där de nixade numren markerats. Vilka av följande metoder kan föreningen använda sig av? Vilken är bäst?

• Binärträd
• Bloomfilter
• Distributionsräkning
• Hashtabell
• Insättning
• Quicksort

Ett framtida mål är att kontroll också skall kunna ske över internet. Då måste kontrollen ske snabbt men man vill också försäkra sig om att ingen ska kunna få ut en lista över alla nixade telefonnummer.

Vilken metod passar bäst för internet-kontrollen?

Svar:

• Binärträd går snabbt att söka i men man måste se till att det inte blir obalanserat när nya telefonnummer läggs till.
• Bloomfilter är besvärligt att stoppa in nya nummer i, eftersom ...
• Distributionsräkning fungerar inte (telefonnumren är ju unika).
• Hashtabell se bloomfilter.
• Insättning är praktiskt när man vill stoppa in nya nummer (om man dessutom väljer att söka med binärsökning går det snabbt).
• Quicksort måste göras om för hela vektorn för varje nytt nummer.

Bloomfilter är det bästa alternativet för den framtida internet-kontrollen. Man kan räkna med att många har registrerat sig så snabb sökning är nödvändig. Dessutom har bloomfilter fördelen att ingen användare kan få ut telefonnummerlistan.