What is an algorithm? Simply put, it is a set of instructions for completing a task. This includes everything from the simplest tasks like sorting your sock drawer to more complicated ones like finding the shortest route between two points on a map. Data structures are just some of the ways that we store information in computers and algorithms are what we use to manipulate our data. In this article, you will learn about different types of algorithms and their applications as well as common data structures used by programmers today!
Analysis of Algorithms
To analyse algorithms we look at their run time speed or simply put how many steps the algorithm takes to solve the problem. We often use Big O notation as a simple way to describe the speed or approximate run time of an algorithm. Big O is an algorithm classification system. It tells you how the complexity of an algorithm changes with input size. Big O does not tell you the time it takes to execute an algorithm, instead we use it as a tool to compare algorithms to each other (i.e., one might be fast for small inputs but slow for large inputs).
The simplest definition of a recursive algorithm is an algorithm that calls itself. We use recursive algorithms when the input data is self-referential. The algorithm can perform a sub-task from within its own body, without having to return control to the calling function or procedure. Recursive functions are well suited for problem solving that requires iteration over an array structure and allows us to avoid loops in our code.
A badly constructed recursive algorithm can call itself infinitely. To avoid infinite recursion, one condition we must meet is having at least one base case in our recursive algorithm. When we make the recursive call, we have to provide an input argument and with every recursive call, that input argument must get closer to the base case. In that way, we ensure that we are going to reach the base case at some point and thus stop the recursion.
Search algorithms look to retrieve information that is stored in some type of data structure and they fall into three broad categories — linear search, binary search, and hashing.
Linear search is the simplest of these, where we simply look at all the elements in a list until we find what we’re looking for. This algorithm has an average runtime complexity that depends on how many items are in our list. It has a time complexity of O(n) or linear run time.
Binary Search applied on sorted data is more efficient than linear search and involves repeatedly dividing the search space in half. This search algorithm has an average runtime complexity that depends on how many items are in our list. Binary Search has a worst case time complexity of O(log n) or logarithmic time complexity.
Hashing is a data structure that allows for us to search for an element in a dataset by storing the data as key-value pairs. We can use hashing to find those values quickly and efficiently with a worst case time complexity of constant time.
Ordering and sorting data is one of the most common problems in computer science. Comparison sorting algorithms sort data by comparing two adjacent elements. When the first element is greater than the second, it swaps them around in order to maintain a sorted list.Sorting algorithms include; bubble sort, selection sort, insertion sort, merge sort and quick sort.
Quick sort has the best performance for the average case, while Merge sort has the best performance for the worst case. Merge sort works using a divide and conquer technique, splitting the list into smaller and smaller parts until they are sorted. Quick sort also uses the divide and conquer approach and starts by selecting a pivot and splitting the array into sub arrays.
Non comparison algorithms are less straight forward than comparison sorting algorithms but they allow for linear time sorting in the worst case. They include counting sort, radix sort and bucket sort.
I’m going to cover some of the most commonly used data structures that are found in almost every programming language out there.
A Linked List is a linear data structure that can be used to store a list of related objects in non-contiguous memory locations in a computers memory. Data is stored in a series of nodes. Each node can hold a link to the next node or to another data item, as well as some other data related to it in some way.
A Stack Data Structure stores objects that are logically arranged in LIFO order (last-in first-out). A stack is a linear data structure and so can be implemented using other linear data structures such as arrays or linked lists.
A Queue is a linear data structure that is very much like a real-life queue, it operates on a FIFO order (first-in first-out). A queue is typically implemented as either an array or linked list.
A Tree structure is a hierarchical data structure. It is a common abstract data type that consists of root nodes, parent and children nodes. Trees can also be used to perform binary search, the binary search algorithm provides for efficient searches for an element.
A Graph data structure consists of vertices (also called nodes) and edges, which are connections between pairs of vertices. Graphs can be used for modelling relationships among different concepts from various domains such as algebra, geometry, spreadsheets, maps or social networks.
Tips for Learning Algorithms
Don’t get discouraged when you cannot easily memorise a certain algorithm — an understanding will come with time and practice! Remember that algorithms are typically used in programming, so it is important to be able to understand how they function as well as utilise them correctly if you plan on becoming a programmer. To learn more about different types of data structures and what they entail, read this article here:
Stay curious! Be prepared to challenge yourself by researching these topics outside of your comfort zone or taking classes at university.
Thanks for reading! If you have any questions about this post, please don’t hesitate to leave a comment below.