Helper Functions

1. Swap

def swap(array, index1, index2):
  temp = array[index1]
  array[index1] = array[index2]
  array[index2] = temp

1. Bubble Sort: (compare adjacent elements)

• Comparison based. O(n²) - worst case. O(n) best case
• Compare all adjacent element, and keep pushing larger one toward right.
• For 5 elements, 4 comparisons needed.
• After first iteration, last element will be sorted (largest).
• Now second iteration will apply on remaining left unsorted subarray (array exclusing last sorted element).
• After second iteration, second last element will be sorted (second largest element).
• keep repeating upto n-1 times, as when n-1 elements will be sorted, remaining one will automatically be sorted.

def bubble_sort(array, start_index, end_index):
  for i in range(end_index - start_index):
    is_swapped = False
    for j in range(start_index, end_index-i):
      if array[j] > array[j+1]:
        swap(array, j, j+1)
        is_swapped = True
    if not is_swapped:
      break
  return array

nums_b = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(bubble_sort(nums_b, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

2. Selection Sort: (find minimum)

• Comparison based. O(n²) worst and best case
• Find minimum element from array, place it at start.
• Now find minimum element from right subarray (array excluding first sorted element), and place it at 2nd place.
• Keep repeating upto n-1 times, as when n-1 elements will be sorted, the remaining will automatically be sorted.

def selection_sort(array, start_index, end_index):
  for i in range(start_index, end_index):
    min_index = i
    for j in range(i+1, end_index+1):
      if array[j] < array[min_index]:
        min_index = j
    swap(array, i, min_index)
  return array

nums_s = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(selection_sort(nums_s, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

3. Insertion Sort: (make place then insert)

• Comparison based. O(n²) worst case. O(n) best case.
• Let first element already sorted.
• Compare 2nd element of array (first element of right unsorted subarray) with all previous elements of left sorted subarray, until you found previous element smaller than that 2nd element of array.
• Keep that 2nd element of array next to that smaller previous element.
• Keep repeating for upto last index.

def insertion_sort(array, start_index, end_index):
  for i in range(start_index+1, end_index+1):
    key = array[i]
    j = i - 1
    while j >= start_index and key < array[j]:
      array[j+1] = array[j]
      j -= 1
    array[j+1] = key
  return array

nums_i = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(insertion_sort(nums_i, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

4. Merge Sort: (divide and merge sortingly)

• Comparison based. O(n log n) worst and best case
• Divinding array until each subarray has one element
• now merging arrays sotingly (two, left and right at a time)
• comparing first element of left and first element of right, updating array at k with smaller one and incrementing index of left (i if smaller was in left) and also incrementing original array index (k - starting from start_index)
• keep repeating until length of one subarray touches.
• After that, adding remaing element of one subarray (that probably would be larger than the other - adding as it is as single array is always being sorted as we moving up (merging)).

def merge_sort(array, start_index, end_index):
  if start_index < end_index:
    mid_index = (start_index + end_index) // 2
    merge_sort(array, start_index, mid_index)
    merge_sort(array, mid_index+1, end_index)

    left = array[start_index:mid_index+1]
    right = array[mid_index+1:end_index+1]
    i = 0
    j = 0
    k = start_index
    while i < len(left) and j < len(right):
      if left[i] < right[j]:
        array[k] = left[i]
        i += 1
      else:
        array[k] = right[j]
        j += 1
      k += 1
    while i < len(left):
      array[k] = left[i]
      i += 1
      k += 1
    while j < len(right):
      array[k] = right[j]
      j += 1
      k += 1
  return array

nums_m = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(merge_sort(nums_m, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

5. Quick Sort: (pivot base, divide and conquer)

• Comparsion based. O(n²) worst case. O(n log n) best case.
• Choose a pivot element.
• Rearrange elements in such a way that all the elements smaller than pivot goes to the left of pivot and all the elemnts greater than the pivot goes to the right side of pivot.

Lomuto Partitioning:

• First choose last element as pivot. make boundary initially at start_index-1, and j as pointer = start_index.
• Now compare the pointer value with pivot. If pointer value is less than or equal to pivot, move i by one and swap i and j. Else do nothing. Now move j by one and do same until you reach before pivot.
• Now move i by one and swap ith element with pivot. Now this pivot has found its correct position.
• Apply the same logic to left and right partitions (excluding pivot) until the list is completely sorted.

def quick_sort_lomuto(array, start_index, end_index):
  if start_index < end_index:
    pivot = end_index
    pivot_value = array[end_index]
    boundary = start_index - 1
    for pointer in range(start_index, end_index):
      if array[pointer] <= pivot_value:
        boundary += 1
        swap(array, boundary, pointer)
    boundary += 1
    swap(array, boundary, pivot)
    quick_sort_lomuto(array, start_index, boundary-1)
    quick_sort_lomuto(array, boundary+1, end_index)
  return array

nums_q = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(quick_sort_lomuto(nums_q, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

Hoare Partitioning:

• Choose first element as pivot.
• Initialize two pointers i (pointer1) at start and j (boundary) at end.
• Move i to the right until an element greater than or equal to pivot found, and move j to the left until an element less than or equal to pivot found, then swap ith and jth values.
• Repeat i and j moving toward eachother until until they meet or cross.
• When the pointers cross, partitioning is complete, based on j (boundary) divide list into two sublists.
• The pivot doesn't land in its final sorted position at the end of a pass. So pivot is not excluded from future steps.
• Apply the same logic to two sublists until the list is completely sorted.

def quick_sort_hoare(array, start_index, end_index):
  if start_index < end_index:
    pivot_value = array[start_index]
    i = start_index
    j = end_index
    while True:
      while array[i] < pivot_value:
        i += 1
      while array[j] > pivot_value:
        j -= 1
      if i < j:
        swap(array, i, j)
        i += 1
        j -= 1
      else:
        break
    quick_sort_hoare(array, start_index, j)
    quick_sort_hoare(array, j+1, end_index)
  return array

nums_q2 = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(quick_sort_hoare(nums_q2, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

• If want to use last element or random element as pivot in Hoare, swap that with first element first before applying already written algorithm.

   1. swap(array, start_index, end_index)

   1. rand_index = random.randint(start_index, end_index)
   2. swap(array, start_index, rand_index)

• If want to use first element or random element as pivot in lomuto, swap that with last element first before applying already written algorithm.

-- Median of Three (start, mid, end)

• If want to use median (first sort the three, then choose the middle one) as pivot, swap that with first or last accordingly before applying already written algorithms.

   1. mid_index = (start_index + end_index) // 2
   2. # sorting the three elements
   3. if array[mid_index] < array[start_index]:
   4.     swap(array, start_index, mid_index)
   5. if array[end_index] < array[start_index]:
   6.     swap(array, start_index, end_index)
   7. if array[end_index] < array[mid_index]:
   8.     swap(array, mid_index, end_index)
   9. swap(array, start_index, mid_index)

6. Counting Sort

• Non comparison based. O(n+k). Linear
• Find the maximum element in array.
• Make other array of length max+1 with initial values of 0. (count array)
• Get count of first element (suppose 5) of array. Place that count (suppose 1) at element index in count array (means place 1 at index of 5 in count array). Do this for all elements of array.
• For doing above step, we just increment value at element index in count array, each time we find that while traversing the array.
• Now update count array by prefix sum, like at 2 index value becomes count[2]+count[1]. Do upto end.
• Now make other final array of len(array).
• Get element (suppose 2) from array, find value at count[element], -1 from c_value, and place element(2) at final[c_value]. Do for all (iterate in reverse for stability)

def counting_sort(array, start_index, end_index):
  subarray = array[start_index:end_index+1]
  length = len(subarray)
  if length < 2:
    return array
  maximum = max(subarray)
  count_array = [0] * (maximum+1)
  # Frequency Count
  for i in subarray:
    count_array[i] += 1
  # Prefix Sum
  for i in range(1, maximum+1):
    count_array[i] += count_array[i-1]
  # Output array
  final_array = [0] * length
  for i in range(length-1, -1, -1):
    value = subarray[i]
    count_array[value] -= 1
    final_array[count_array[value]] = value
  # Putting in original
  for i in range(length):
    array[start_index+i] = final_array[i]
  return array

nums_c = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(counting_sort(nums_c, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

7. Radix Sort

• Non comparison based. O(d*(n+b)). Linear
• find maximum value in array.
• counting sort first according to unit digit, then tens digit, then 100s digit , upto maximum value digits places.
• in counting sort, now we will make 10 digit count_array, as it is on digit level now (only ten possibilities 0-9).

def counting_sort_digit(array, start_index, end_index, place):
  subarray = array[start_index:end_index+1]
  length = len(subarray)
  if length < 2:
    return array
  maximum = max(subarray)
  count_array = [0] * 10
  # Frequency Count
  for i in subarray:
    digit = (i // place) % 10
    count_array[digit] += 1
  # Prefix Sum
  for i in range(1, 10):
    count_array[i] += count_array[i-1]
  # Output array
  final_array = [0] * length
  for i in range(length-1, -1, -1):
    digit = (subarray[i] // place) % 10
    count_array[digit] -= 1
    final_array[count_array[digit]] = subarray[i]
  # Putting in original
  for i in range(length):
    array[start_index+i] = final_array[i]

def radix_sort(array, start_index, end_index):
  subarray = array[start_index:end_index+1]
  length = len(subarray)
  if length < 2:
    return array
  maximum = max(subarray)
  place = 1
  while maximum // place > 0:
    counting_sort_digit(array, start_index, end_index, place)
    place *= 10
  return array

nums_r = [5, 3, 0, 1, 8, 2, 4, 8, 24, 3, 2, 7, 4, 9, 12]
print(radix_sort(nums_r, 0, 14))

[0, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 8, 9, 12, 24]

8. Bucket Sort

• Non comparison based. O(n+k) best case, O(n²) worst. Linear
• Works on floating point number range 0.0 to 1.0.
• Create n empty buckets (n empty lists in a list).
• Iterate array, multiply array[i]*n (int), and put that value array[i] into bucket[array[i]*n].
• Sort all buckets (mostly insertion sort).
• Concatenate all buckets orderly.

def bucket_sort(array, start_index, end_index):
  subarray = array[start_index:end_index+1]
  length = len(subarray)
  buckets = [[] for _ in range(length)]
  for i in subarray:
    buckets[int(i * length)].append(i)
  for bucket in buckets:
    insertion_sort(bucket, 0, len(bucket)-1)
  i = 0
  for bucket in buckets:
    for num in bucket:
      array[start_index+i] = num
      i += 1
  return array

nums_bk = [.5, .3, 0, .1, .8, .2, .4, .8, .24, .3, .2, .7, .4, .9, .12]
print(bucket_sort(nums_bk, 0, 14))

[0, 0.1, 0.12, 0.2, 0.2, 0.24, 0.3, 0.3, 0.4, 0.4, 0.5, 0.7, 0.8, 0.8, 0.9]