Elementary Sorting

lecture notes

Hur gör man när man sorterar en lista/vektor med element, det är detta som den andra veckan i kursen handlar om.

Interface:

compareTo(a, b): -1 om b > a, 0 om a = b, 1 om a > b
    if a not comparable with b:
        throw exception
    if a > b:
        return 1
    elif a == b:
        return 0
    else:
        return -1

less(a, b):
    return compareTo(a, b) < 0

exch(data[], idx_a, idx_b): 
    if idx_a or idx_b out of range:
        throw exception

    tmp = data[idx_a]
    data[idx_a] = data[idx_b]
    data[idx_b] = tmp

 isSorted(data)
    for idx in range(1, data.length):
        if data[idx] < data[idx-1]:
            return False
    return True

In [1]:
import pandas
from bokeh.io import push_notebook, show, output_notebook
from bokeh.charts import Bar
from bokeh.plotting import figure, reset_output

import random
import time

In [2]:
def exch(data, idx_a, idx_b):
    # todo: fix checking...
    tmp = data[idx_a]
    data[idx_a] = data[idx_b]
    data[idx_b] = tmp
    
def compareTo(a, b):
    if a > b:
        return 1
    elif a == b:
        return 0
    else:
        return -1

def less(a, b):
    return compareTo(a, b) < 0

In [3]:
data = [random.randint(1,100) for c in range(80) ]

Selection sort:

Vi börjar med en naiv sorteringsalgoritm:

Ta det första elementet i listan, sök sedan efter det minsta elementet i resterande del av listan. Om ett sådant hittas så byter man plats på det första elementet och detta. Upprepa sedan proceduren för efterföljande element.

Denna sorteringsalgoritm har komplexitet: (N-1 + N-2... 1 + 0) == N * N/2... den skalar inte vidare bra.


In [31]:
def selection_sort(data):

    output_notebook()

    temp = data[:]

    p = figure(plot_width=400, plot_height=400, title='selection sort')
    vb = p.vbar(x=[c for c in range(len(temp))], width=0.5, bottom=0, top=temp, color="firebrick")
    init = p.vbar(x=[c for c in range(len(data))], width=0.5, bottom=0, top=data, color="gray", alpha=0.75)

    t = show(p, notebook_handle=True)

    for i in range(len(temp)):
        min_idx = i
        for j in range(i+1, len(temp)):
            if less(temp[j], temp[min_idx]):
                min_idx = j
        exch(temp, i, min_idx)
        push_notebook(handle=t)
        push_notebook()
        time.sleep(0.01)

    reset_output()
    
    return temp

In [32]:
items = selection_sort(data)


Loading BokehJS ...

Insertion sort:

Vi börjar från början, om efterföljande element mindre än nuvarande element, byt plats på dessa två... (samt fortsätt med jämförelse med tidigare element i listan).

Komplexiteten är för denna algoritm i bästa fall i storleksordningen N. Detta inträffar då listan är sorterad. Om listan å andra sidan är "inverterad" så har vi i värsta fall 1 + 2 + 3... + N-2 + N-1 == N * N/2


In [6]:
def insert_sort(data):
    exchanges = 0
    loops = 0
    temp = data[:]

    output_notebook()

    p = figure(plot_width=400, plot_height=400, title='insert sort')
    vb = p.vbar(x=[c for c in range(len(temp))], width=0.5, bottom=0, top=temp, color="firebrick")
    init = p.vbar(x=[c for c in range(len(data))], width=0.5, bottom=0, top=data, color="gray", alpha=0.75)

    t = show(p, notebook_handle=True)

    for i in range(len(temp)-1):
        loops += 1
        if less(temp[i+1], temp[i]):
            exch(temp, i, i+1)
            push_notebook(handle=t)

            for j in range(i, 0, -1):
                loops += 1
                if less(temp[j-1], temp[j]):
                    break
                exch(temp, j-1, j)
                push_notebook(handle=t)

    reset_output()

    return temp



#print(''.join(insert_sort(list('SORTEXAMPLE'))))
#print(''.join(insert_sort(list('ZYXWVUTSRQPONMLKJIHGFEDCBA'))))
#print(''.join(insert_sort(list('ABCDEFGHIJKLMNOPQRSTUVWXYZ'))))

In [12]:
items = insert_sort(data)


Loading BokehJS ...

Shellsort:

När det gäller shellsort så sorterar man på en större skala först och minskar efter hand intervallen:

Intervallen beräknas utifrån hur mycket data man har som skall sorteras. Algoritmen för att räkna ut "intervallen":

while h < N // 3:
    h = 3*h + 1

Detta ger en sekvens med "intervall" 1, 4, 13, 40, 121, 364, ... Sedan tittar vi på alla element "i" mellan h och N, jämför dessa med de element som finns på avståndet "h" mot början av vektorn. Om detta element är mindre än tidigare element (på avstånd h) så byter man plats på dessa, dvs de blir "h sorted"/"h sorterade". När man sedan minskar intervallet mellan elementen så blir sorteringen mer och mer finkorning.

Komplexiteten för denna algoritm är i "worst case" N^(3/2), dvs betydligt bättre än "insertion sort" eller "selection sort".


In [8]:
def shell_sort(data):
    N = len(data)
    temp = data[:]
    
    output_notebook()

    p = figure(plot_width=400, plot_height=400, title='shell sort')
    vb = p.vbar(x=[c for c in range(N)], width=0.5, bottom=0, top=temp, color="firebrick")
    init = p.vbar(x=[c for c in range(len(data))], width=0.5, bottom=0, top=data, color="gray", alpha=0.75)

    t = show(p, notebook_handle=True)

    h = 1;
    while h < N//3:
        h = 3*h + 1     # 1, 4, 13, 40, 121, 364, ...

    while h >= 1:
        for i in range(h, N):
            for j in range(i, h-1, -h):
                if not less(temp[j], temp[j-h]):
                    break

                exch(temp, j, j-h)
                push_notebook(handle=t)
                time.sleep(0.01)

        h = h // 3

    reset_output()

    return temp

#print(''.join(shell_sort(list('SORTEXAMPLE'))))
#print(''.join(shell_sort(list('ZYXWVUTSRQPONMLKJIHGFEDCBA'))))
#print(''.join(shell_sort(list('ABCDEFGHIJKLMNOPQRSTUVWXYZ'))))

In [13]:
items = shell_sort(data)


Loading BokehJS ...

In [23]:
%%bash
ls -l
if [ ! -d "reveal.js" ]; then
    git clone https://github.com/hakimel/reveal.js.git
fi
if [ -f "elementary-sorting.slides.html" ]; then
    rm elementary-sorting.slides.html
fi


total 2777
-rwxrwx---+ 1 perssonj Domänen-Benutzer   82688 May 30 13:16 elementary-sorting.ipynb
drwxrwx---+ 1 perssonj Domänen-Benutzer       0 May 30 12:19 images
-rwxrwx---+ 1 perssonj Domänen-Benutzer   35815 Mar 24 09:17 LICENSE
-rwxrwx---+ 1 perssonj Domänen-Benutzer   28336 Mar 24 09:17 merge-sort.ipynb
-rwxrwx---+ 1 perssonj Domänen-Benutzer   26527 May  4 07:09 quicksort.ipynb
-rwxrwx---+ 1 perssonj Domänen-Benutzer      14 Mar 24 09:17 README.md
drwxrwxr-x+ 1 perssonj Domänen-Benutzer       0 May 30 11:54 reveal.js
-rwxrwx---+ 1 perssonj Domänen-Benutzer 2654518 Mar 24 09:17 union-find.ipynb

In [24]:
%%bash
jupyter nbconvert --to slides elementary-sorting.ipynb --reveal-prefix=reveal.js #--post serve


[NbConvertApp] Converting notebook elementary-sorting.ipynb to slides
[NbConvertApp] Writing 336807 bytes to elementary-sorting.slides.html

Klicka här för slideshow.