Sorting Algorithms

In today’s world, everyone has data, and we all want this data to look nice and organized. Besides our urge to see data in a well-ordered manner, a lot of the important algorithms are designed to work on sorted data. As you can imagine, it would be difficult to sort through data manually, and that’s why computers are used to perform these tasks. But sometimes, the data at hand can be enormous, and in these situations, even the most powerful computers can take a significant chunk of time to sort through data.

This is where the importance of the sorting algorithms comes to light. There are several sorting algorithms to choose from, each with its own benefits depending on the situation. With the right algorithm, you can sort data within a fraction of seconds which would have otherwise taken a considerable amount of time.

While choosing the algorithm, your data's initial condition comes into play as well; the array of elements could be random or reversed, it can be nearly sorted or sorted with a few unique values. When choosing an algorithm that most accurately fits your needs, you’ll have to become familiar with the different sorting algorithms used in practice.

Before we dive into the world of sorting algorithms, there are few mathematical notations you need to understand which are used for the asymptotic analysis of algorithms.

Taken from giphy.com

Don’t worry if you have heard this term for the first time. Soon we’ll see what exactly this means.

Prerequisites

Computing the exact runtime of an algorithm is a tedious task. It depends on knowing all kinds of fine details about how the program works and all kinds of fine details about how the computer works, how fast it is, what kind of system architecture it has. It’s a huge mess. We don’t want to go through this huge mess every single time we try to analyze an algorithm.

That’s why we use asymptotic analysis to measure the efficiency of an algorithm. This type of analysis helps us answer the question, how does our program’s runtime scale with the input size. 3 mathematical functions are used for calculating the asymptotic time complexity for an algorithm, Big O notation (worst case), Omega notation (best case), and Theta notation.

I’ll refrain from further discussing these topics here, as you are here to learn about sorting algorithms, and I don’t want to bore you with these mathematical functions.

Taken from giphy.com

As of now, we’ll only use Big O notation, which represents the upper bound of the runtime of an algorithm. If you want to explore this topic, click here.

There are few more points that you should know

So armed with the knowledge of asymptotic analysis, and appreciating a few other terms, let us begin our journey exploring the various sorting algorithms, starting with the bubble sort.

Bubble Sort

Selection Sort

Taken from Coding Connect

Until now, the algorithms that we discussed were pretty basic, and that’s why I did not show you any practical implementation. From now, I’ll also include a code snippet (written in CPP) showing the practical implementation of the algorithms that we discuss. Though, I won’t be explaining the code here.

Taken from giphy.com

I encourage you to look at the description and the code snippet, then connect the dots yourself. Believe me, you’ll feel ecstatic and joyous after deciphering the underlying ideas behind these algorithms.

Insertion Sort

Taken from Wikimedia Commons

I believe that’s enough algorithms for one day.

Taken from giphy.com

I hope you had a fun experience exploring these algorithms and enhanced your knowledge at the same time. If you wish to give feedback, feel free to contact me.

Resources

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store