Every Algorithm in CSC 4520

algorithm bogoSort
  Input: array of integers arr of size n
  Output: Sorted array, where each subsequent element is larger than the previous

  while arr is not sorted
    randomly shuffle the elements of arr
  return arr

algorithm twoSumSlow
  Input: list of integers Lst of size N, integer Target
  Output: integers i and j such that Lst[i]+Lst[j] = Target; -1, -1 otherwise

  for i = 0, 1, 2, ..., N-1
    for j = i + 1 to N-1
      if arr[i] + arr[j] = Target
        return i, j
  return -1 -1

algorithm maxOfList
  input: List of integers Lst
  output: largest integer within Lst
  maxSoFar = -infinity

  for each element el in Lst
    maxSoFar = max(maxSoFar, el)
  return maxSoFar

algorithm minOfList
  input: List of integers Lst
  output: smallest integer within Lst
  minSoFar = infinity

  for each element el in Lst
    minSoFar = min(minSoFar, el)
  return minSoFar

algorithm findSecondSmallest
  input: list of Integers Lst,
    where size of Lst > 1
  output: the second smallest
    element in Lst

  firstSmallest = infinity
  secondSmallest = infinity
  for each element el in Lst,
    if el < firstSmallest
       secondSmallest = firstSmallest
       firstSmallest = el
    else if el < secondSmallest
       secondSmallest = el
  return secondSmallest

algorithm addTwoLists
  input: two lists of integers L1 and L2, where
    the size of L1 and L2 are equal
  output: a list of integers L3, where
    L3[i] = L1[i] + L2[i] for all i
  L3 = list as big as L1 (or L2)
  for each index i in L1,
    L3[i] = L1[i] + L2[i]
  return L3

algorithm factorial
  input: integer n >= 0
  output: n!
  if n = 0:
    return 1
  else
    return n * factorial(n - 1)

algorithm fib
  input: integer n >= 0
  output: nth fibonacci number
  if n = 0:
    return 1
  if n = 1:
    return 1
  else
    return fib(n-1) + fib(n-2)

public static int fib(int n) {
  assert n >= 0 : "n is nonnegative";
  if (n < 2) {
    return n;
  }
  return fib(n-1) + fib(n-2);

algorithm findIndex
  Input: array of integers arr, integer target x
  Output: index of x within arr if it is in arr, -1 otherwise

  for each index i and corresponding element e in arr
	if e = x
  	  return i
  return -1

algorithm anotherFindIndex
  Input: array of integers arr, integer target x
  Output: index of x within arr if it is in arr, -1 otherwise

  result = -1
  for each index i and corresponding element e in arr
	if e = x
  	  result = i
  return result

algorithm selectionSort
  Input: list of integers lst of size N
  Output: lst such that its elements are in sorted order

  for index i = 0, 1, 2, ..., N-2
    min_index = i
    for j = i+1, i+2, ..., N-1
      if lst[j] < lst[min_index]
        min_index = j
    temp = lst[i]
    lst[i] = lst[min_index]
    lst[min_index] = temp

algorithm insertionSort
  Input: list of integers lst of size N
  Output: lst such that its elements are in sorted order
  for index i = 1, 2, ..., N-1
    next = lst[i]
    j = i-1
    while j >= 0 and lst[j] > next
      lst[j+1] = lst[j]
      j = j-1
    lst[j+1] = next

algorithm QuickSort
  Input: lists of integers lst of size N
  Output: new list with the elements of lst in sorted order

  if N < 2
    return lst
  pivot = lst[N-1]
  left = new empty list
  right = new empty list
  for index i = 0, 1, 2, ... N-2
    if lst[i] <= pivot
      left.add(lst[i])
    else
      right.add(lst[i])
  return QuickSort(left) + [pivot] + QuickSort(right)

algorithm heapSort
  Input: list of integers lst of size N
  Output: lst such that its elements are in sorted order

  heap = new max heap of size N
  result = new list of size N
  for index i = 0, 1, 2, ..., N-1
    heapAdd(heap, lst[i])
  while heap.size() > 0
    result.addFirst(heapExtractMax(heap))
  return result

algorithm mergeSort
  Input: list of integers lst of size N
  Output: lst such that its elements are in sorted order

  if N < 2
    return lst
  midpoint = floor(N/2)
  left = mergeSort(lst.subList(0, midpoint))
  right = mergeSort(lst.subList(midpoint, N))
  return merge(left, right)

algorithm merge
  Input: two lists of sorted L1 and L2
  Output: lst L3 that contains the elements of L1 and L2 in sorted order

  i = 0; j  = 0; L3 = empty list
  while i < L1.size() or j < L2.size()
    if i >= L1.size()
      L3.add(L2[j])
      j = j + 1
    else if j >= L2.size()
      L3.add(L1[i])
      i = i + 1
    else if L1[i] <= L2[j]
      L3.add(L1[i])
      i = i + 1
    else
      L3.add(L2[j])
      j = j + 1
  return L3

algorithm countingSort
  Input: array of integers arr, integer k where each element of arr is between [0, k]
  Output: array of integers in sorted order
  count = array of k+1 zeros
  for element el in arr
    count[el] += 1
  total = 0
  for i in 0, 1, ... k do
    count[i], total = total, count[i] + total // dual assignment
  output = array of the same length as arr
  for element el in arr:
    output[count[el]] = el
    count[el] += 1
  return output

algorithm radixSort
  Input: list of integers lst of size N
  Output: lst such that its elements are in sorted order

  d = the largest place value among all the numbers
  for i = 1, 2, ..., d
    use a stable sort to sort lst on digit i