sorts.py

# -*- coding: utf-8 -*-
"""sorts

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1M6Rw33CbJqWZBwpTai3tJkBX9BMMQGv4
"""

#sorts.py module

"""
sorting algorithms used:
- bubble sort:

"""
import random

#optimized bubble sort algorithm
def bubble_sort(array, comparison_function_used):
  swaps = 0
  sorted = False
  while not sorted:
    sorted = True
    for idx in range(len(array) - 1):
      if comparison_function_used(array[idx], array[idx + 1]): #if left > right
        sorted = False
        array[idx], array[idx + 1] = array[idx + 1], array[idx] #swap function
        swaps += 1
  print("Bubble Sort: There were {0} swaps in the operation".format(swaps))
  return array

#random pivoted point quick sort algorithm
def quick_sort(list, start, end, comparison_function_used):
  if start >= end:
    return
  pivot_index = random.randrange(start, end + 1)
  pivot_element = list[pivot_index]
  list[end], list[pivot_index] = list[pivot_index], list[end]
  less_than_pointer = start
  for i in range (start, end):
    if comparison_function_used(pivot_element, list[i]):
      list[i], list[less_than_pointer] = list[less_than_pointer], list[i]
      less_than_pointer += 1
  list[end], list[less_than_pointer] = list[less_than_pointer], list[i]
  quick_sort(list, start, less_than_pointer - 1, comparison_function_used)
  quick_sort(list, less_than_pointer + 1, end, comparison_function_used)

#basic merge sort
def merge_sort(array):
  if len(array) > 1:

    r = len(array)//2
    L = array[:r]
    M = array[r:]

    merge_sort(L)
    merge_sort(M)

    i = j = k = 0

    while i < len(L) and j < len(M):
      if L[i] < M[j]:
        array[k] = L[i]
        i += 1
      else:
        array[k] = M[j]
        j += 1
      k += 1

    while i < len(L):
      array[k] = L[i]
      i += 1
      k += 1

    while j < len(M):
      array[k] = M[j]
      j += 1
      k += 1

#selection sort algorithm (might be in reverse by default?)
def selection_sort(array, size, comparison_function_used):
  for step in range(size):
    min_index = step

    for i in range(step + 1, siz):
      if comparison_function_used(array[min_index], array[i]):
        min_index = i

    array[step], array[min_index] = array[min_index], array[step]

#insertion sort algorithm
def insertion_sort(array, comparison_function_used):
  for step in range(1, len(array)):
    key = array[step]
    j = step - 1

  while j>=0 and comparison_function_used(array[j], key):
    array[j + 1] = array[j]
    j = j - 1

  array[j+1] = key

#heap sorting algorithm
def heapify(array, n, i, comparison_function_used):
  largest = i
  l = 2 * i + 1
  r = 2 * i + 2

  if l < n and comparison_function_used(array[i], array[l]):
    largest = l

  if r < n and comparison_function_used(array[largest], array[r]):
    largest = r
  
  if largest != i:
    array[i], array[largest] = array[largest], array[i]
    heapify(array, n, largest, comparison_function_used)

def heap_sort(array, comparison_function_used):
  n = len(arr)

  for i in range(n//2, -1, -1):
    heapify(array, n, i, comparison_function_used)

  for i in range (n-1, 0, -1):
    array[i], array[0] = array[0], array[i]
    heapify(array, i, 0, comparison_function_used)