This post describes some Sorting Algorithms that we use for sorting an unsorted array.

From top (the best) to bottom (bad).

Quick Sort

Code: 

def quickSort(arr):

    # the operation of comparing head, tail ele with pivot
    # swap ele on tail < pivot with ele on head > pivot
    # continue until head >= tail 
    # return head as the end position of left partion of the original array
    def partition (arr, head, tail, pivot):
        while (head <= tail):
            while(arr[head] < pivot): 
                head += 1 
            while(arr[tail] > pivot):
                tail -= 1
            
            if(head <= tail): 
                # if equal, still moving pointer one time 
                if(head != tail): 
                    swap(arr, head, tail) 
                head += 1 
                tail -= 1 
        return head 

    # recursively sorting 
    def sorting(arr,head,tail): 
        # if head == tail, only 1 element 
        # if head > tail, no way
        if (head < tail):
            pivot = arr[int((head + tail) / 2)]         # pick the middle element as pivot
            new_head = partition(arr,head,tail,pivot)
            sorting(arr,head,new_head-1)
            sorting(arr,new_head,tail)


    #--------------Begin---------------#
    sorting(arr, 0, len(arr)-1)
    return arr

Merge Sort

Code:

def mergeSort(arr):

    # Merge low array and high array
    # low and high array should be sorted for themself on the way from 2 elements 
    # - compare the head 2 elements from two arrays
    # - take the small one and append to new arrays
    # - repeat until the end of one array
    # - then append the rest of elements from the one that still have elements
    def merge(low, high):
        i = 0
        j = 0
        merged = []
        while i < len(low) and j < len(high):
            if low[i] < high[j]:
                merged.append(low[i])
                i += 1
            else:
                merged.append(high[j])
                j += 1

        # one of these two arrays will be empty (that's how we exited the loop)
        # so, it's always safe to just add the rest of the elements for both
        return merged + low[i:] + high[j:]
    

    #--------------Begin---------------# 

    length = len(arr)
    halfLength = int(length/2)

    # base case, if our list is 0, or 1 element, the its sorted
    if length <= 1:
        return arr

    # recursive case: split the list in half
    # sort the halves
    # merge the lists together
    low = mergeSort(arr[0:halfLength])
    high = mergeSort(arr[halfLength:length])
    arr = merge(low,high)

    return arr

Heap sort

Code:

###################################
#
#            11(0)
#           / \
#          /   \
#         10(1)  8(2)
#        / \     \
#       /   \     |
#      4(3) 9(4) 7(5)
#
#           ==> array = [11, 10, 8, 4, 9, 7]
#
###################################
def heapSort(arr):

    # Make a Max heap for the array
    # Not a completed heapify fnc !!!
    def heapify(arr, length, i):
        leftChild = 2*i +1
        rightChild = 2*i +2
        largest = i

        if (leftChild < length and arr[i] < arr[leftChild]):
            largest = leftChild

        if(rightChild < length and arr[largest] < arr[rightChild]):
            largest = rightChild

        if(largest != i): 
            swap(arr, i, largest) 
            heapify(arr, length, largest) # just swap the largest with the root 
                                          # root node now on previous largest 
                                          # position, continue pushing down 
                                          # the root node as needed 

    #--------------Begin---------------# 
    node = len(arr) 

    # start from last index of the array (last node) 
    # build Max heap from subtree 
    # so Maximum # can be pushed up to the top of tree 
    for i in range(node,-1,-1): # node, node-1, node-2, ..., 1, 0 
        heapify(arr,node,i) 

    while(node > 1):
        swap(arr, 0, node-1)    # 2
        node -= 1               # 3
        heapify(arr,node,0)     # 4

    return arr

Insertion sort

Code:

def insertionSort(arr):
    length = len(arr)

    # start by inserting 1st element, comparing with 0th element
    for i in range(1, length):
        while(i > 0) and (arr[i] < arr[i-1]): 
            swap(arr,i,i-1) i -= 1       # if new insered element > last element
                                         # no need to compare and swap

    return arr

# same algorithm, different operation
# here using a temp var to hold 
# new element to be inserted
# ----------------(Faster than above)------------------------- 
def insertionSort2(arr):
    for i in range(1,len(arr)):
        newElement = arr[i]     # new element to be inserted to sorted array
        j = i-1
        while j>=0 and arr[j]>newElement:   # if most right ele > new ele
            arr[j+1] = arr[j]               # swap to left
            j = j -1
        arr[j+1] = newElement
    
    return arr

Selection sort

Code:

def selectionSort(arr):

    # returns the index of the minimum element in an array
    # O(n)
    def minIndex(a, low, high):
        mIndex = low
        for i in range(low+1,high):     # low+1 ~ high-1
            if a[i] < a[mIndex]:
                mIndex = i
        return mIndex

    #--------------Begin---------------# 

    for i in range(len(arr)-1):     # 0 ~ (len - 2)
        swap(arr, i, minIndex(arr, i, len(arr)))
    return arr

Bubble sort

Code:

def bubbleSort(arr):
    length = len(arr)
    while length > 1:
        for i in range( length-1 ):
            if(arr[i] > arr[i+1]):
                swap(arr, i, i+1)
        length -= 1

    return arr

Counting sort

Code:

def countingSort(arr, maxKey, minKey):
    length = len(arr)
    key_range = maxKey - minKey

    # create a temp arr with size range
    # O (k)
    C = []
    for i in range(key_range):
        C.append(0)

    # counting how many duplicated same element 
    for i in range(0, len(arr)):
        C[arr[i] - minKey] += 1

    # counting target index of each element should be
    # in sorted version
    for i in range(0,key_range):
        C[i] = C[i] + C[i-1]

    # create a sorted array
    S = [None] * length
    for i in range(0, length):
        S[ C[ arr[i] - minKey ] ] = arr[i]
        C[ arr[i] - minKey ] -= 1

    return S

Bucket sort

Code:

def bucketSort(arr):
    length = len(arr)
    B = [None] * length

    # create array B
    for i in range(0, length):
        B[i] = []

    # create subarray of B
    for i in range(1, length):
        B[ length * arr[i]] = arr[i]

    # sort each subarray of B
    for i in range(0, length):
        insertionSort2( B[i] )      # O (i^2)

    # concat all subarray of B
    S = []
    for i in range(0, length):
        S += B[i]

    return S

Radix sort

Code:

def radixSort(arr, digit):          
    for i in range(digit):  # how many digit of a number
        # usea a stable sort to sort Array of number on digit i
        # counting sort is the best
        # since there are only 10 digits 0 ~ 9
        i = 0

    return arr