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) ]
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)
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)
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)
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
In [24]:
%%bash
jupyter nbconvert --to slides elementary-sorting.ipynb --reveal-prefix=reveal.js #--post serve
Klicka här för slideshow.