In [8]:

    

import random
import sys
from copy import copy

def swap(s, i, j):
    if i != j:
        temp = s[i]
        s[i] = s[j]
        s[j] = temp
        
s = list(range(30))
random.shuffle(s)
print(s)


    

    




[8, 28, 16, 3, 26, 6, 1, 22, 17, 18, 7, 4, 12, 15, 27, 24, 2, 14, 20, 25, 19, 13, 10, 9, 21, 11, 29, 5, 0, 23]

In [10]:

    

def selection_sort(s):
    for i in range(len(s)):
        minidx = i
        for j in range(i + 1, len(s)):
            if s[j] < s[minidx]:
                minidx = j
        swap(s, i, minidx)
    return s

print(selection_sort(copy(s)))


    

    




[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

In [12]:

    

def insertion_sort(s):
    for i in range(1, len(s)):
        cur = i
        while cur > 0 and s[cur - 1] > s[cur]:
            swap(s, cur - 1, cur)
            cur = cur - 1

    return s

print(insertion_sort(copy(s)))


    

    




[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

In [13]:

    

def partition(s, l, h):
    pivot = h

    first = l

    for i in range(l, h):
        if s[i] < s[pivot]:
            swap(s, i, first)
            first += 1

    swap(s, first, pivot)
    pivot = first
    
    return pivot

def quick_sort(s, l, h):
    if h > l:
        pivot = partition(s, l, h)
        quick_sort(s, l, pivot - 1)
        quick_sort(s, pivot + 1, h)

    return s

print(quick_sort(copy(s), 0, len(s) - 1))


    

    




[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

In [16]:

    

def bubble_sort(seq):
    for i in range(0, len(seq)):
        for j in range(len(seq) - 1, i, -1):
            if seq[j] < seq[j-1]:
                swap(seq, j, j - 1)
        #print(seq)
    return seq
    
    
print(s)
#print(bubble_sort([55, 7, 78, 12, 42]))
print(bubble_sort(copy(s)))


    

    




[8, 28, 16, 3, 26, 6, 1, 22, 17, 18, 7, 4, 12, 15, 27, 24, 2, 14, 20, 25, 19, 13, 10, 9, 21, 11, 29, 5, 0, 23]
[0, 8, 28, 16, 3, 26, 6, 1, 22, 17, 18, 7, 4, 12, 15, 27, 24, 2, 14, 20, 25, 19, 13, 10, 9, 21, 11, 29, 5, 23]
[0, 1, 8, 28, 16, 3, 26, 6, 2, 22, 17, 18, 7, 4, 12, 15, 27, 24, 5, 14, 20, 25, 19, 13, 10, 9, 21, 11, 29, 23]
[0, 1, 2, 8, 28, 16, 3, 26, 6, 4, 22, 17, 18, 7, 5, 12, 15, 27, 24, 9, 14, 20, 25, 19, 13, 10, 11, 21, 23, 29]
[0, 1, 2, 3, 8, 28, 16, 4, 26, 6, 5, 22, 17, 18, 7, 9, 12, 15, 27, 24, 10, 14, 20, 25, 19, 13, 11, 21, 23, 29]
[0, 1, 2, 3, 4, 8, 28, 16, 5, 26, 6, 7, 22, 17, 18, 9, 10, 12, 15, 27, 24, 11, 14, 20, 25, 19, 13, 21, 23, 29]
[0, 1, 2, 3, 4, 5, 8, 28, 16, 6, 26, 7, 9, 22, 17, 18, 10, 11, 12, 15, 27, 24, 13, 14, 20, 25, 19, 21, 23, 29]
[0, 1, 2, 3, 4, 5, 6, 8, 28, 16, 7, 26, 9, 10, 22, 17, 18, 11, 12, 13, 15, 27, 24, 14, 19, 20, 25, 21, 23, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 28, 16, 9, 26, 10, 11, 22, 17, 18, 12, 13, 14, 15, 27, 24, 19, 20, 21, 25, 23, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 28, 16, 10, 26, 11, 12, 22, 17, 18, 13, 14, 15, 19, 27, 24, 20, 21, 23, 25, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 28, 16, 11, 26, 12, 13, 22, 17, 18, 14, 15, 19, 20, 27, 24, 21, 23, 25, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 28, 16, 12, 26, 13, 14, 22, 17, 18, 15, 19, 20, 21, 27, 24, 23, 25, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 28, 16, 13, 26, 14, 15, 22, 17, 18, 19, 20, 21, 23, 27, 24, 25, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 28, 16, 14, 26, 15, 17, 22, 18, 19, 20, 21, 23, 24, 27, 25, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 28, 16, 15, 26, 17, 18, 22, 19, 20, 21, 23, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 28, 16, 17, 26, 18, 19, 22, 20, 21, 23, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 28, 17, 18, 26, 19, 20, 22, 21, 23, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 28, 18, 19, 26, 20, 21, 22, 23, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 28, 19, 20, 26, 21, 22, 23, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 28, 20, 21, 26, 22, 23, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 28, 21, 22, 26, 23, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 28, 22, 23, 26, 24, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 28, 23, 24, 26, 25, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 28, 24, 25, 26, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 28, 25, 26, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 28, 26, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 27, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

In [25]:

    

def merge(l, r):
    ret = []
    lsize = len(l)
    rsize = len(r)
    l.append(sys.maxsize)
    r.append(sys.maxsize)
    
    curl = 0
    curr = 0
    for i in range(0, lsize + rsize):
        if l[curl] <= r[curr]:
            ret.append(l[curl])
            curl += 1
        else:
            ret.append(r[curr])
            curr += 1
    return ret

def merge_sort(seq):
    if len(seq) > 1:
        q = len(seq)//2
        l = merge_sort(seq[:q])
        r = merge_sort(seq[q:])
        return merge(l, r)
    else:
        return seq
        
print(s)
#print(bubble_sort([55, 7, 78, 12, 42]))
print(merge_sort(copy(s)))


    

    




[8, 28, 16, 3, 26, 6, 1, 22, 17, 18, 7, 4, 12, 15, 27, 24, 2, 14, 20, 25, 19, 13, 10, 9, 21, 11, 29, 5, 0, 23]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

In [54]:

    

def max_heapify(seq, size, i):
    left = 2*i + 1
    right = 2*i + 2
    
    largest = i
    if left < size and seq[left] > seq[i]:
        largest = left
    
    if right < size and seq[right] > seq[largest]:
        largest = right
        
    if largest != i:
        swap(seq, i, largest)
        max_heapify(seq, size, largest)

def build_max_heap(seq):
    for i in range(len(seq)//2 - 1,  -1 , -1):
        max_heapify(seq, len(seq), i)
        
def heap_sort(seq):
    build_max_heap(seq)
    print(seq)
    
    for i in range(len(seq) - 1):
        last = (len(seq) - 1) - i
        swap(seq, 0, last)
        #print(i, seq)
        max_heapify(seq, len(seq) - i - 1, 0)
        #print(i, seq)
    return seq

print(s)
print(heap_sort([55, 7, 78, 12, 42]))
print(heap_sort(copy(s)))


    

    




[8, 28, 16, 3, 26, 6, 1, 22, 17, 18, 7, 4, 12, 15, 27, 24, 2, 14, 20, 25, 19, 13, 10, 9, 21, 11, 29, 5, 0, 23]
[78, 42, 55, 12, 7]
[7, 12, 42, 55, 78]
[29, 28, 27, 24, 26, 21, 23, 22, 20, 25, 13, 16, 12, 15, 8, 3, 2, 14, 17, 18, 19, 7, 10, 9, 4, 11, 6, 5, 0, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

In [ ]: