# Every Algorithm in CSC 4520

## 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
``````