Part 1: Sorting Algorithm

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1. The subarray is already sorted.
2. Remaining subarray which is unsorted. In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.

import sys
A = [55, 30, 15, 22, 9]
for i in range(len(A):
    min_idx = i
    for j in range(i+1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j

    A[i], A[min_idx] = A[min_idx], A[i]

print("Sorted Array")
for i in range(len(A))
    print("%d" %A[i])


# Output
Sorted array
9 15 22 30 55

Bubble Sort

Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they're in wrong order.

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [73, 34, 27, 12, 22, 10, 110]
bubbleSort(arr)
print("Sorted array")
for i in range(len(arr)):
    print("%d", %arr[i])


# Output
Sorted array
10 12 22 27 34 73 110

There is also a recursive version of Bubble Sort
How to implement recursive bubble sort?
Recursive bubble sort has no performance or implementation advantages, but can be a good question to check one's understanding of bubble sort and recursion.
Recursion Idea

1. Base Case: If the array size is 1, return.
2. Do One Pass of normal bubble sort. This pass fixes the last element of the current subarray.
3. Recur for all elements except last of the current subarray.

def bubble_sort(listx):
    for i, num in enumerate(listx):
        try:
            if listx[i+1] < num:
                listx[i] = listx[i+1]
                listx[i+1] = num
                bubble_sort(listx)
        except IndexError:
            pass
    return listx

listx = [60, 36, 25, 13, 23, 10, 99]
bubble_sort(listx)
print("Sorted array")
for i in range(0, len(listx)):
    print(listx[i], end=' ')


# Output
Sorted array
10 13 23 25 36 60 99

Quick Sort

Quick sort is a divide and conquers algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quick sort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot.
3. Pick a random element as pivot.
4. Pick median as pivot.

The key process in quick sort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements before x, and put all greater elements after x. All this should be done in linear time.

def partition(arr,low,high):
    i = (low-1)
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[j], arr[i+1]
    return (i+1)

def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr,low,pi-1)
        quickSort(arr,pi+1,high)

arr = [10, 8, 7, 5, 9, 1]
n = len(arr)
quickSort(arr,0,n-1)
print("Sorted array")
for i in range(n):
    print("%d" %arr[i])


# Output
Sorted array
1 5 7 8 9 10

The recursive quick sort implementation can be optimized in many ways.

1. The recursive quick sort implementation uses last index as pivot. This causes worst-case behaviour on already sorted arrays, which is a commonly occurring case. The problem can be solved by choosing either a random index for the pivot or choosing the middle index of the partition or choosing the median of the first, middle and last element of the partition for the pivot.
2. To reduce the recursion depth, recur first for the smaller half of the array, and use a tail call to recurse into the other.
3. Insertion sort works better for small subarrays. Insertion sort can be used for invocations on such small arrays.

Below is the typical recursive quick sort implementation.

def partition(arr,low,high):
    i = (low-1)
    pivot = arr[high]
    for j in range(low,high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)

def quickSort(arr,low,high):
    if low < high:
    pi = partition(arr,low,high)
    quickSort(arr,low,pi-1)
    quickSort(arr,pi+1,high)

if __name__ == '__main__':
    arr = [4, 2, 6, 9, 2]
    n = len(arr)
    quickSort(arr, 0, n-1)
    for i in range(n):
        print(arr[i], end=" ")

# Output
2 2 4 6 9

The below mentioned optimizations for recursive quick sort can also be applied to iterative version.

1. Partition process is same in both recursive and interactive. The same techniques to choose optimal pivot can also be applied to iterative version.
2. To reduce the stack size, first push the indexes of smaller half.
3. Use insertion sort when the size reduces below a experimentally calculated threshold.

def partition(arr,l,h):
    i = (l-1)
    x = arr[h]
    for j in range(l,h):
        if arr[j] <= x:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[h] = arr[h], arr[i+1]
    return (i+1)

def quickSortIterative(arr,l,h):
    size = h-l+1
    stack = [0]*(size)
    top = -1
    top = top+1
    stack[top] = 1
    top = top+1
    stack[top] = h
    while top >= 0:
        h = stack[top]
        top = top-1
        l = stack[top]
        top = top-1
        p = partition(arr,l,h)
        if p-1 > 1:
            top = top+1
            stack[top] = p+1
            top = top+1
            stack[top] = h

arr = [4, 3, 5, 2, 1, 3, 2, 3]
n = len(arr)
quickSortIterative(arr,0,n-1)
print("Sorted array")
for i in range(n):
    print("%d" %arr[i])


# Output
Sorted array
1 2 2 3 3 3 4 5

Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
    print("%d" %arr[i])


# Output
5 6 11 12 13

Example of Recursive Insertion Sort

How to implement insertion sort recursively?
Recursive insertion sort has no performance or implementation advantages, but can be a good question to check one's understanding of insertion sort and recursion. If we take a closer look at insertion sort algorithm, we keep processed elements sorted and insert new elements one by one in the inserted array.
Recursion Idea

1. Base Case: If array size is 1 or smaller, return.
2. Recursively sort first n-1 elements.
3. Insert last elements at its correct position in sorted array.

def insertionSortRecursive(arr,n):
    if n<=1:
        return
    insertionSortRecursive(arr,n-1)
    '''Insert last elements at its correct position in sorted array'''
    last = arr[n-1]
    j = n-2
    while (j>=0 and arr[j]>last):
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = last

def printArray(arr,n):
    for i in range(n):
        print arr[i],
arr = [12, 11, 13, 5, 6]
insertionSortRecursive(arr,n)
printArray(arr,n)

# Output
5 6 11 12 13

Don't forget to join my telegram community

P.S: There is going to be several parts of the Top 7 Algorithms series.