Visualizing EPL 2018/19 Title Race

Bucket Sort

Algorithm:

• Create Buckets of same size as of the array
• Distribute element of array into buckets
• Sort each bucket(using any sorting algorithm) and add them back together

When to use:

• When the elements in the array is uniformly distributed.

Time Complexity:

• Best/Average: O(n+k) -takes n times to distribute each element to k buckets and k times to add them back together.
• Worst: O(n2)- when all the elements fall into single bucket

Space Complexity:

• O(n) - usually no extra space is required

In-place: yes
Stable:no

Python Implementation:
def bucket_sort(arr):
   n = len(arr)
   buckets = [[] for _ in range(n)]
   for i in range(n):
        b_index = arr[i]*n
        buckets[b_index] = arr[i]
    result = []
    for bucket in buckets:
          result = result+insertion_sort(bucket)
    return result

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

Quick Sort

Algorithm:

• Select a pivot element in the array
• Move the selected pivot to its correct location in array such that all elements on its left is less than it and all elements on the right are greater than it.

Time Complexity:

• Best/Average: O(nlogn) -list is divided into two halves and it takes linear time to merge the list back.
• Worst: O(n2)- when either largest or smallest element is selected as pivot. Also, when the list is already sorted.

Space Complexity:

• O(1) - usually no extra space is required

In-place: yes
Stable:no

Python Implementation

arr = [1,2,5,4,9]
low = 0
high = len(arr)-1

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

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

         

Merge Sort

Algorithm:

• Iteratively Divide the list to two halves
• Sort and Merge the divided list until one list remains recursively

Time Complexity:

• Best/Worst/Average: O(nlogn) -list is divided into two halves and it takes linear time to merge the list back.

Space Complexity:

• O(n) - usually no extra space is required

In-place: yes
Stable: yes

Python Implementation

def merge_sort(arr):
    m = len(arr)/2
    L = arr[:m]
    R = arr[m:]
    merge_sort(L)
    merge_sort(R)
    i = j = k = 0
   while i < len(L) and j < len(R):
       if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
       else:
             arr[k] = R[j]
             j += 1
       k += 1
     
    while i < len(L):
           arr[k] = L[i]
           i += 1
           k += 1
    while j< len[R]:
           arr[k] = R[j]
           j += 1
           k += 1
         

Insertion Sort

In insertion sort, the sorting task is similar to that of sorting a deck of cards.

Algorithm:

1. Start at the beginning
2. Find the next element and bring it to its sorted position

 Time Complexity:

• Best: O(n) - when the list is already sorted
• Worst: O(n2) - when required to reverse the entire list

Space Complexity:

• O(1) - usually no extra space is required 

In-place: yes
Stable: yes

Python Implementation
def insertion_sort(arr):
    n = len(arr)
    for i in range(n):
        j = i
        while j > 0 and arr[j-1] > arr[j]:
            arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1

Selection Sort

Algorithm:

• Find smallest element with linear scan
• Move it to the front
• Continue until all elements are in place

Time Complexity:

• Best: O(n2) - when the list is already sorted (https://stackoverflow.com/questions/43298396/best-case-time-complexity-for-selection-sort)
• Worst: O(n2) - when required to reverse the list

Space Complexity:

• O(1) - usually no extra space is required 

In-place: yes
Stable: yes

Python Implementation:
def selection_sort(arr):
    n = len(arr)
    for i range(n):
        min_index = i
        for j in range(i+1, n):
            if a[min_index] > a[j]:
                 min_index = j
    a[i], a[min_index] = a[min_index], a[i]

Bubble Sort

Algorithm:

• Start at the beginning
• Swap first two element if first is greater than second
• Continue to next pair
• Repeat until sorted

Time Complexity:

• Best: O(n) - when the list is already sorted
• Worst: O(n2) - when required to reverse the list

Space Complexity:

• O(1) - usually no extra space is required

In-place: yes
Stable: yes

Python Implementation

def bubble_sort(array):
    n = len(array)
    for j in range(n):
        for i in range(n-1-j):
            if a[i] > a[i+1]:
                a[i+1], a[i] = a[i], a[i+1]