DanielAmah

# Heap Sorting Algorithm
# the root node of the heap is always the largest value
# build a sorted array by repeatedly removing the root node
# push to our new array
# heapify the max heap so that the new, largest value node is at the root.

def heap_sort(array)
  n = array.length - 1
  a = array

DanielAmah

# Implement Depth First Search using Binary Search Tree
# uses stack to perform the DFS.
# Precedure
#  1. Add root node to the stack.
#  2. Loop on the stack as long as it's not empty.
#    1. Get the node at the top of the stack(current), mark it as visited,
#    2. For every non-visited child of the current node, do the following:
#        1. Check if it's the destination node, If so, then return this child node.
#        2. Otherwise, push it to the stack.
#  3. If stack is empty, then destination node was not found!

DanielAmah

# We would use a binary tree to implement Breadth First Search(BFS)
# We could use a shift or push to add a remove from an array or
# we use queue to help implement BFS, we use "deq" to remove an node and "enq"
# to add node.
# 1. Add root node to the queue, and mark it as visited.
# 2. Loop on the queue as long as it's not empty.
#    1. Get and remove the node at the top of the queue(current).
#    2. For every non-visited child of the current node, do the following:
#       1. Mark it as visited.
#       2. Check if it's destination node, If so, then return it.

DanielAmah

def selection_sort(arr)
  n = arr.length - 1
  n.times do |i|
    min_index = i
    ((i + 1)..n).each do |j|
      min_index = j if arr[j] < arr[min_index]
    end
    arr[i], arr[min_index] = arr[min_index], arr[i] if min_index != i
  end
  arr

DanielAmah

# implementation of insertion sort
  # Pick an item from an array
  # compare all items in the sorted sub-list
  # shift all items in the sorted sub-list greater than the item to be sorted
  # insert the item
  # repeat until the list is sorted.

def insertion_sort(arr)
  a_length = arr.length
  a_length.times do |i|

DanielAmah

def bubble_sort(arr)
  arr_length = arr.length
  swapped = true
  while swapped
    swapped = false
    (arr_length - 1).times do |i|
      if arr[i] > arr[i + 1]
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
        swapped = true
      end