algorithms.py

from numpy import random
from array import array as array_type

n = 100
numbers = array_type('i', random.randint(n, size = n))
print(numbers)

# Quicksort

def partition(array, i, n):
    l = i
    r = n - 1
    pivot = random.randint(i, n)
    
    while( l < r ):
        while( array[l] <= array[pivot] and l < r):
            l = l + 1
        while( array[r] >= array[pivot] and l < r):
            r = r - 1
        
        if l < r:
            array[l], array[r] = array[r], array[l]
    
    if array[r] < array[pivot]:
        array[r], array[pivot] = array[pivot], array[r]
    
    return array, r

def quicksort(array):
    n = len(array)
    
    if n <= 1:
        return array
    
    array, pivot = partition(array, 0, n)
    
    left = quicksort(array[:pivot])
    right = quicksort(array[pivot:])

    return left + right

result = quicksort(numbers)

if list(result) == sorted(list(result)):
    print("Quicksort works!")
else:
    print("Quicksort bug!")

# Mergesort

def merge(array1, array2):
    if not array1:
        return array2
    elif not array2:
        return array1
    
    i = 0
    j = 0
    
    result = array_type('i')
    
    while(i < len(array1) and j < len(array2)):
        if array1[i] < array2[j]:
            result.append(array1[i])
            i = i + 1
        else:
            result.append(array2[j])
            j = j + 1
            
    while(i < len(array1)):
        result.append(array1[i])
        i = i + 1
            
    while(j < len(array2)):
        result.append(array2[j])
        j = j + 1
    
    return result

def mergesort(array):
    if len(array) == 0 or len(array) == 1:
        return array
    
    if len(array) == 2:
        if array[0] > array[1]:
            array[0], array[1] = array[1], array[0]
        return array
    else:
        middle = round(len(array)/2)
        left = mergesort(array[:middle])
        right = mergesort(array[middle:])
        
        return merge(left, right)

result = mergesort(numbers)

if list(result) == sorted(list(result)):
    print("Mergesort works!")
else:
    print("Mergesort bug!")


# K-smallest
## Random pivot

def partition(array, i, n):
    l = i
    r = n - 1
    pivot = random.randint(i, n)
    
    while( l < r ):
        while( array[l] <= array[pivot] and l < r):
            l = l + 1
        while( array[r] >= array[pivot] and l < r):
            r = r - 1
        
        if l < r:
            array[l], array[r] = array[r], array[l]
    
    if array[r] < array[pivot]:
        array[r], array[pivot] = array[pivot], array[r]
    
    return array, r

def selectk(array, k, first, last):
    if first >= last-1:
        return array[first]
    else:
        array, middle = partition(array, first, last)
        if middle - first >= k:
            return selectk(array, k, first, middle)
        else:
            return selectk(array, k-(middle-first), middle, last)
        
def ksmallest_rand(array, k):
    return selectk(array, k+1, 0, len(numbers))
    
if ksmallest_rand(numbers, 10) == sorted(numbers)[10]:
    print("K-smallest random pivot works!")
else:
    print("K-smallest random pivot bug!")
    
## Median of medians
def median_partition(array, m):
    array1 = []
    array2 = []
    array3 = []
    
    for i in array:
        if i < m:
            array1.append(i)
        elif i == m:
            array2.append(i)
        else:
            array3.append(i)
    
    return array1, array2, array3

def ksmallest_mm(array, k):
    length = len(array)
    
    if length <= 5:
        array = sorted(array)
        return array[k]
    
    medians = []
    for i in range(length//5):
        x = []
        for j in range(5):
            if i*5+j < length:
                x.append(array[i*5+j])
        medians.append(ksmallest_mm(x, 2))
        
    median_of_medians = ksmallest_mm(medians, length//10)
    
    l1, l2, l3 = median_partition(array, median_of_medians)
    
    if k < len(l1):
        return ksmallest_mm(l1, k)
    elif k > len(l1)+len(l2):
        return ksmallest_mm(l3, k - len(l1)-len(l2))
    else:
        return median_of_medians
    
if ksmallest_mm(numbers, 10) == sorted(numbers)[10]:
    print("K-smallest median of medians works!")
else:
    print("K-smallest median of medians bug!")