Sorting Algorithms



In [8]:

    
import numpy as np

Quicksort

Generally fastest sorting algorith. Uses a divide an conquere scheme.



In [71]:

    
def quicksort(arr,low,high):
    pivot = arr[low]  # pivot on the first value in the array
    j = low  # index of smaller element
    for i in range(low,high):
        if arr[i] <= pivot:
            print('swap')
            swap(arr,i,j)
            j = j+1
    if low < high:
        quicksort(arr,low,low-1)
        quicksort(arr,low+1,high)
    return arr



In [70]:

    
arr = np.array([0, 7, 2, 4, 6, 1, 0, 9, 3, 5])
print(quicksort(arr,0,len(arr)-1))









    



swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
[0 0 2 1 6 4 3 9 7 5]

Heapsort

Create a max heap with the input array and then swap the first and last element. Reduce sort space by 1 and continue until only one element is in the sort space.



In [ ]:



In [23]:

    
def heapify(arr, root, n):
    largest = root
    l = 2*root+1
    r = 2*root+2
    
    if l > len(arr)-1:
        return arr
    
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < len(arr)-1:
        if r < n and arr[r] > arr[largest]:
            largest = r
    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, root, n)

def swap(arr,i,j):
    arr[i], arr[j] = arr[j], arr[i]

def heapsort(arr):
    n = len(arr)
    while n > 1:
        for i in range(0,n):
            heapify(arr,i,n)
        swap(arr,0,n-1)
        n -= 1

    return arr