Data structures and algorithms

sorting_algos.md

Sorting Algorithms

Reference \

Straight Insertion

Description - From left to right, sort the numbers in groups starting from 1 to the length of the array
Time complexity - O(n^2)
Space complexity - O(1)

const insertionSort = (arr: number[]) => {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let curr = arr[i];
        let pos = i;

        while (pos > 0 && arr[pos - 1] > curr) {
            arr[pos] = arr[pos-1]
            pos--;
        }
        arr[pos] = curr;
    }
}

Shell Sort

Description - Partially sorts small subsets, then bigger subsets until the subset is the array, then finishes with an insertion algorithm
Time complexity - O(n(log(n)^2)
Space complexity - O(1)

// DOES NOT CURRENTLY WORK - TO BE FIXED
const shellSort = (arr: number[]) => {
    let sublistCount = Math.trunc(arr.length / 2);
    while (sublistCount > 1) {
        for (let start = 0; start < sublistCount; start++) {
            gapInsertionSort({ nArr: arr, start: start, gap: sublistCount });
        }
        sublistCount = Math.trunc(sublistCount / 2);
    }
}

const gapInsertionSort = ({ nArr, start, gap }: { nArr: number[], start: number, gap: number }) => {
    const n = nArr.length;
    for (let i = start + gap; i < n; i + gap) {
        let curr = nArr[i];
        let pos = i;

        while (pos >= gap && nArr[pos - gap] > curr) {
            nArr[pos] = nArr[pos - gap]
            pos -= gap;
        }
        nArr[pos] = curr;
    }
}

Bubble Sort

Description - Compares adjacent elements and keeps repeating until it doesn't need to change anything. Max outer loops is length of the array
Time complexity - O(n^2)
Space complexity - O(1)

const bubbleSort = (arr: number[]) => {
    const n = arr.length;
    for (let i = n - 1; i >= 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp
            }
        }
    }
}

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

Quicksort

Description -
Time complexity - Avg - O(n log(n)); Worst - O(n^2)
Space complexity - O(log(n))

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

Heapsort

Description - Add all numbers to a binary tree. Swap the numbers if the child is bigger than the root... then... [TO BE COMPLETED]
Time complexity - O(n log(n))
Space complexity - O(1)

# To heapify subtree rooted at index i. 
# n is size of heap 
def heapify(arr, n, i): 
	largest = i # Initialize largest as root 
	l = 2 * i + 1	 # left = 2*i + 1 
	r = 2 * i + 2	 # right = 2*i + 2 

	# See if left child of root exists and is 
	# greater than root 
	if l < n and arr[i] < arr[l]: 
		largest = l 

	# See if right child of root exists and is 
	# greater than root 
	if r < n and arr[largest] < arr[r]: 
		largest = r 

	# Change root, if needed 
	if largest != i: 
		arr[i],arr[largest] = arr[largest],arr[i] # swap 

		# Heapify the root. 
		heapify(arr, n, largest) 

# The main function to sort an array of given size 
def heapSort(arr): 
	n = len(arr) 

	# Build a maxheap. 
	for i in range(n, -1, -1): 
		heapify(arr, n, i) 

	# One by one extract elements 
	for i in range(n-1, 0, -1): 
		arr[i], arr[0] = arr[0], arr[i] # swap 
		heapify(arr, i, 0) 

heapSort(arr)