Link Search Menu Expand Document

Every Algorithm in CSC 4520

Table of Contents

  1. Basic Arrays and Numbers
    1. BogoSort
    2. TwoSumSlow
    3. MaxOfList
    4. MinOfList
    5. FindSecondSmallest
    6. AddTwoLists
    7. Factorial
    8. Fibonacci
    9. FindIndex
  2. Sorting
    1. Selection Sort
    2. Insertion Sort
    3. QuickSort
    4. HeapSort
    5. MergeSort
      1. Merge
    6. Counting Sort
    7. Radix Sort

Basic Arrays and Numbers

BogoSort

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

TwoSumSlow

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
public static int[] twoSumSlow(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = i+1; j < arr.length; j++) {
      if (arr[i] + arr[j] == target) {
        return new int[] {i, j};
      }
    }
  }
  return new int[] {-1, -1};
}

MaxOfList

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
public static int maxOfList(List<Integer> list) {
  int maxSoFar = Integer.MIN_VALUE;
  for(int i = 0; i < list.size(); i++) {
     maxSoFar = Math.max(maxSoFar, list.get(i));
  }
  return maxSoFar;
}

MinOfList

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
public static int minOfList(List<Integer> list) {
  int minSoFar = Integer.MAX_VALUE;
  for(int i = 0; i < list.size(); i++) {
    minSoFar = Math.min(minSoFar, list.get(i));
  }
  return minSoFar;
}

FindSecondSmallest

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
public static int secondSmallest(List<Integer> list) {
  assert list.size() > 1 : "list needs to have at least 2 elements";
  int firstSmallest = Integer.MAX_VALUE;
  int secondSmallest = Integer.MAX_VALUE;
  for (int i = 0; i < list.size(); i++) {
    int el = list.get(i);
    if (el < firstSmallest) {
      secondSmallest = firstSmallest;
      firstSmallest = el;
    } else if (el < secondSmallest) {
      secondSmallest = el;
    }
  }
  return secondSmallest;
}

AddTwoLists

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
public static List<Integer> addTwoLists(List<Integer> l1, List<Integer> l2) {
  assert l1.size() == l2.size() : "lists must have same size";
  List<Integer> result = new ArrayList();
  for (int i = 0; i < l1.size(); i++) {
    result.add(l1.get(i) + l2.get(i));
  }
  return result;
}

Factorial

algorithm factorial
  input: integer n >= 0
  output: n!
  if n = 0:
    return 1
  else
    return n * factorial(n - 1)
public static int factorial(int n) {
  assert n >= 0 : "n is nonnegative"
  if (n <= 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

Fibonacci

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);

FindIndex

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

Sorting

Selection Sort

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

Insertion Sort

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

QuickSort

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)

HeapSort

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

MergeSort

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)

Merge

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

Counting Sort

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

Radix Sort

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