As a programming beginner, implementing fundamental algorithms is one of the best ways to improve your coding abilities. Mastering algorithms helps you develop skills like analyzing performance tradeoffs, breaking down problems, and understanding common programming paradigms like recursion and data partitioning.
In this article, we cover 10 beginner-friendly algorithms that will boost your coding chops and set you up for tackling more complex algorithms. Each section provides a quick overview of an algorithm along with Java code examples.
1. Linear Search
Linear search is a simple search algorithm for finding a target value in an array by checking each element sequentially until it is found or the array ends.
Though not the most efficient search algorithm, implementing linear search will hone iteration abilities and conditional logic skills.
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
2. Binary Search
Binary search is an efficient divide-and-conquer algorithm that locates an element in a sorted array by cutting the search space in half each iteration. Asking whether the target is less than, equal to, or greater than the midpoint value eliminates half the remaining elements.
Binary search teaches recursion, space/time tradeoffs, and why sorting data can optimize searching.
int binarySearch(int[] sortedArr, int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (sortedArr[mid] == target) {
return mid;
}
if (target < sortedArr[mid]) {
return binarySearch(sortedArr, left, mid - 1, target);
}
return binarySearch(sortedArr, mid + 1, right, target);
}
return -1;
}
3. Bubble Sort
Bubble sort iteratively steps through a list, comparing adjacent elements and swapping them if they are out of order. Larger elements “bubble up” towards the end of the list.
Though inefficient compared to other sorts, bubble sort introduces comparison sorts with inner and outer loops.
void bubbleSort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
4. Insertion Sort
Insertion sort incrementally builds the final sorted array in place by comparing each element to those already sorted and inserting it into the correct position.
Implementing insertion sort helps reinforce skills in incrementally building solutions.
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int curr = arr[i];
int j = i - 1;
while (j >= 0 && curr < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = curr;
}
}
5. Merge Sort
Merge sort uses a classic divide and conquer approach – break down the data into individual pieces, solve the sub-problems over those pieces, then combine the solutions.
First it recursively splits the array in half until atomic individual elements. Then, efficient merging reconstructs the final fully sorted array from the base up by comparing/interleaving the sorted splits.
Implementing merge sort builds recursion skills and teaches combining solutions.
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr , mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int[] arr, int l, int m, int r) {
// Merges the two sorted subarrays
}
6. Quicksort
Quicksort picks a random pivot element and partitions the array into three sections – less than pivot, equal to pivot, and greater than pivot. It recursively operates on the less than and greater than partitions before concatenating the final sorted array from the three partitions.
Quicksort teaches randomness for efficiency and incrementally sorting arrays by partitioning data.
int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pIndex = partition(arr, low, high);
quickSort(arr, low, pIndex - 1);
quickSort(arr, pIndex + 1, high);
}
}
7. Breadth First Search
Breadth first search (BFS) is used to traverse or search graphs or trees efficiently. It explores all the nodes level-by-level from the starting position. BFS leverages a queue data structure to traverse iteratively.
Implementing BFS introduces graph algorithms, trees, traversal, and leveraging queues.
void bfs(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node curr = queue.poll();
// Do something with curr Node
for (Node child : curr.getChildren()) {
queue.add(child);
}
}
}
8. Depth First Search
Depth first search (DFS) also traverses trees or graphs, but goes deeper down one branch before backtracking rather than exploring level-by-level. DFS utilizes a stack to traverse recursively deeper immediately when possible.
DFS teaches advanced recursion, backtracking, and exploiting stacks.
void dfs(Node curr) {
if (curr == null) {
return;
}
// Do something with curr node
for (Node child : curr.getChildren()) {
dfs(child);
}
}
9. Greedy Algorithms
Greedy algorithms build up solutions piece-by-piece in a locally optimal way, without regard for global optimality. They make locally optimal choices to incrementally reach a sufficient solution.
Implementing greedy approaches teaches incremental optimization and sufficiency over perfection.
int activitySelection(Activity[] acts) {
Arrays.sort(acts, (a, b) -> a.end - b.end);
int count = 0;
int end = 0;
for (Activity act : acts) {
if (act.start >= end) {
count++;
end = act.end;
}
}
return count;
}
10. Dynamic Programming
Dynamic programming simplifies complex problems by breaking them down into simpler sub-problems, as with divide and conquer algorithms, but also caches/remembers solutions to avoid duplicate calculation.
DP introduces advanced memoization, optimization, and incrementally constructing solutions.
int fib(int n, Map<Integer,Integer> memo) {
if (n <= 1) {
return n;
}
if (!memo.containsKey(n)) {
memo.put(n, fib(n-1, memo) + fib(n-2, memo));
}
return memo.get(n);
}
Learning these fundamental algorithms helps beginners vastly improve their coding skills. Implementing them develops critical abilities like refining loops and conditionals, problem decomposition, applying common data structures like arrays, stacks, queues and graphs, recursion mastery, and analyzing time/space complexity tradeoffs.
