Merge sort

Plan:

dela upp mängden i två delar
sortera rekursivt de två delarna
slå ihop de två delarna

Merge: vi ska slå ihop två delar av en vektor

kopiera delarna mellan "lo" och "hi" till en "aux-vektor"
för varje element i vektorn (inom intervallet "lo" -> "hi"
- if "low counter > mid"... plocka från "hi interval"
- elif "hi counter > hi"... plocka från "lo interval"
- elif less(a[low_counter], a[hi_counter], plocka från "lo interval"
- else plocka från "hi interval"



In [6]:

    
import pandas
from bokeh.io import push_notebook, show, output_notebook, reset_output
from bokeh.charts import Bar
from bokeh.plotting import figure

import random
import time



In [7]:

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



In [8]:

    
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 [9]:

    
def merge(a, aux, lo, mid, hi, handle=None):
    # todo: kolla att a[lo:mid] är sorterad
    # todo: kolla att a[mid+1:hi] är sorterad
    for k in range(lo, hi+1):
        aux[k] = a[k]
    
    i = lo
    j = mid+1
    for k in range(lo, hi+1):
        if i > mid:
            a[k] = aux[j]
            j += 1
        elif j > hi:
            a[k] = aux[i]
            i += 1
        elif less(aux[i], aux[j]):
            a[k] = aux[i]
            i += 1
        else:
            a[k] = aux[j]
            j += 1

        if handle is not None:
            push_notebook(handle=handle)
            time.sleep(0.01)


def sort(a, aux, lo, hi, handle=None):
    if hi <= lo:
        return
    
    mid = lo + (hi -lo) // 2
    sort(a, aux, lo, mid, handle=handle)
    sort(a, aux, mid+1, hi, handle=handle)
    merge(a, aux, lo, mid, hi, handle=handle)

def merge_sort(data):
    a = data [:]
    aux = a[:]
    
    output_notebook()

    p = figure(plot_width=400, plot_height=400, title='merge sort')
    vb = p.vbar(x=[c for c in range(len(a))], width=0.5, bottom=0, top=a, 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)

    sort(a, aux, 0, len(a)-1, handle=t)

    reset_output()
    
    return a



In [10]:

    
items = merge_sort(data)









    





    
        
        Loading BokehJS ...



In [ ]: