Published on

The Fundamentals of Algorithms

Authors
The Fundamentals of Algorithms

Before discussing the fundamentals of algorithms, and their different types, we need to establish a clear understanding of what an algorithm truly is. An algorithm can be likened to a baker making muffins. Much like the baker, an algorithm follows a precise set of instructions to achieve a specific goal. These instructions dictate what ingredients are necessary, the precise quantities required, and the order in which they should be combined. Similarly, an algorithm operates on a predefined set of instructions to solve a particular problem or attain a desired outcome. This process may require input from the user such as what type of data is needed and how the data should be sorted, then it works through the steps necessary to arrive at a solution or provide an output based on the given parameters.

More practically, we use algorithms to solve problems, speed up computation, minimize errors, and improve the performance of our programs leading to faster and more reliable software.

In the next few sections of this article we’ll discuss the fundamentals of algorithms, including types, characteristics, and common operations.

Algorithm Types

Sorting

Sorting algorithms are used to arrange a list of elements in a particular order. Some of the most common sorting algorithms are:

Bubble Sort

  • The Bubble Sort compares each successive pair of elements in an unordered list and inverts the elements if they are not in order.
  • Simple to understand, but not very efficient for large data sets.
void **bubbleSort**(int T[], int N) {
    for (int i = 0; i < N-1; i++)
        for (int j = 0; j < N - i - 1; j++)
            if (T[j] > T[j+1])
                **swap**(T[j], T[j+1]);
}

Insertion Sort

  • Builds the final sorted array one item at a time. It takes each element from the list and places it in its correct position in the already sorted part.
  • Efficient for small data sets, but like Bubble Sort, it's less efficient for larger ones.
void **insertionSort**(int T[], int N) {
	for (int i = ; i < N; i++) {
		int tmp = T[i];
		int j = i - 1;
		while (tmp < T[j] && j >= 0) {
			T[j + 1] = T[j];
			j--;
		}
		T[j + 1] = tmp;
	}
}

Merge Sort

  • Merge Sort is a divide-and-conquer algorithm. It divides the input list of length N in half successively until there are n lists of size 1. Then, pairs of lists are merged together with the smaller first element among the pair of lists being added in each step. Through successive merging and through comparison of first elements, the sorted list is built.
Merge Sort
  • An efficient, divide-and-conquer algorithm, good for large data sets.
void **mergeSort**(int T[], int low, int high) {
	if(low < high){
		int mid = (low + high) / 2;
		// Divide and Conquer
		**mergeSort**(T, low, mid);
		**mergeSort**(T, mid + 1, high);
		// Combine
		**merge**(T, low, mid, high);
	}
}

void **merge**(int T[], int low, int mid, int high) {
	int i, j, k;
    int n1 = mid - low + 1;
    int n2 = high - mid;
		// Two temporary arrays to hold the two arrays to be merged
    int T1[n1], T2[n2];

    for (i = 0; i < n1; i++)
        T1[i] = T[low + i];
    for (j = 0; j < n2; j++)
        T2[j] = T[mid + 1 + j];

		// Process of combining two sorted arrays
    i = 0;
		j = 0;
		k = low;

    while (i < n1 && j < n2) {
        if (T1[i] <= T2[j])
            T[k++] = T1[i++];
        else
            T[k++] = T2[j++];
    }

    // Copy the remaining elements of T1, if there are any
    while (i < n1) {
        T[k++] = T1[i++];
    }

    // Copy the remaining elements of T2, if there are any
    while (j < n2) {
        T[k++] = T2[j++];
    }
}

Quick Sort

  • Quicksort is a sorting algorithm that picks an element ("the pivot") and reorders the array forming two partitions such that all elements less than the pivot come before it and all elements greater come after. The algorithm is then applied recursively to the partitions until the list is sorted.
  • Another divide-and-conquer algorithm, known for its high performance with large data sets.
void **quickSort**(int T[], int low, int high) {
	if(low < high){
		int pivot = **partition**(T, low, high);
		**quickSort**(T, low, pivot - 1);
		**quickSort**(T, pivot + 1, high);
	}
}

void **partition**(int T[], int low, int high) {
	int pivot = T[high];
	int i = (low - 1);
	for(int j = low; j < high; j++) {
		if(T[j] <= pivot) {
			i++;
			**swap**(T[i], T[j]);
		}
	}
	**swap**(T[i + 1], T[high]);
	return (i + 1);
}

Searching

Linear search is a simple algorithm. It loops through items until the query has been found, which makes it a linear algorithm

int **linearSearch**(int T[], int N, int x) {
	for(int i = 0; i < N; i++)
		if(T[i] == x)
			return i;
	return -1;
}
  • Binary Search is a Divide and Conquer search algorithm.
  • To use Binary Search, the search space must be ordered (sorted) in some way.
  • It divides the search space in half and checks if the target element is in the first half or the second half, then repeats the process until the target element is found.
int **binarySearch**(int T[], int x, int low, int high) {
	int mid = (low + high) / 2;

	if (x == T[mid]) {
			return (mid);
	} else {
			if (x < T[mid]) {
				**binarySearch**(T, x, low, mid - 1);
			} else {
				**binarySearch**(T, x, mid + 1, high);
			}
	}
	return -1;
}

Common Techniques

Iteration

  • Iteration involves repeating a set of instructions until a specific condition is met. In algorithms, this is commonly achieved using loops such as for, while, and do-while.
  • Iterative solutions usually involve simple steps repeated in a loop and are often easier on your computer's memory. This is because they don't require the extra memory that comes with calling a function multiple times, as seen in recursive solutions.

Recursion

  • Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. It's a natural fit for problems that can be divided into similar sub-problems.
  • The simplest way to think of recursion is a function that calls itself until the problem is solved. This usually involves what is referred to as a "base case." A base case is the point in which the problem is solved at.

Divide and conquer

  • This technique involves dividing a problem into smaller sub-problems, solving each sub-problem independently, and then combining their results to solve the original problem.
  • Merge Sort and Quick Sort are classic examples of divide and conquer, where the problem of sorting a list is broken down into sorting smaller lists.

Dynamic programming

  • Think of Dynamic Programming (DP) as a smart way to solve big, tricky problems by splitting them into smaller, easier parts. It works really well when these smaller parts overlap – that is, when solving one part can help you solve others.
  • With DP, we keep track of the answers to these small parts, usually in a table, so we don't have to solve the same thing over and over again. This way, we can solve the whole big problem quicker and more efficiently.

Key Takeaways

In practice, different algorithms have different use cases depending on the data size, problem complexity, and desired time and space complexity. Understanding each algorithm independently will help you select the appropriate algorithm for your problem.

Resources:

View on GitHub