The Sorting Algorithms You Need To Know
Basically an algorithm is just fancy term for a set of instructions of what a program should do, and how it should do it. In other words: it’s nothing more than a manual for your code.
Why sort oneself out?
Before we get into different sorting algorithm techniques ,lets see what actually sorting is why it’s so important.
We all have to deal with sorting of items in our everyday lives. For example, I had bunch of papers and I was doing my assignment and tossing that papers in a hurry so that were really disorganized. And when it came time to review, everything was a total mess, and all the pages were disorganized, and it was pretty terrible. I had to sort them by page number manually for the process of reviewing. If you read enough about sorting algorithms, you’ll notice that sorting a deck of cards, sorting books, or sorting a collection of numbers and alphabets are all common examples of sorting algorithm implementations.
What are Sorting Algorithms & what’s there need?
Sorting Algorithms are ways to organize data in particular order, like the alphabets or decimals. We need to sort data in order to perform the search and other operations efficiently. Common Sorting Algorithms can be valuable to boost our performance in Problem Solving to a much extent.
When it comes to Computer Science, there are four main algorithms that you need to know. Bubble Sort, Selections Sort, Merge Sort, and Quick Sort.Data searching can be optimized to a high level, if data is stored in sorted manner.
1. Bubble Sort:
Description: Take a random list. Start at the beginning of the list and swap the first two elements if the first is greater than the second. Then, go to the next pair, making continuous sweeps of the list and so on until the list is sorted.
i. Time complexity
The easiest way to classify an algorithm is by time complexity, or by how much relative time it takes to run the algorithm given a different input size.So, in this sorting technique, the runtime is O(n²) average and worst case.
ii. Space complexity/ Memory Usage
Different algorithms requires a different amount of space, depending on their space complexity.In other words, it means How much memory will this algorithm need to run? So, in this sorting technique, the memory usage is O(1).
2. Selection Sort:
Description: Find the smallest element using a linear iteration and move it to the front (swapping and placing that to the front element). Then, find the second smallest and move it to the second position in the list, using once again a linear scan. Continue to do this by checking elements one by one until the list is sorted.
Time Complexity: O(n²) for average and worst case.
Space Complexity: O(1).
3. Merge Sort:
Description: Merge sort uses the divide and conquer method and is a recursive algorithm. Although it is more difficult to implement than other algorithms, it is very “time efficient”. It divides the list in half, sorts each of those halves, and then merges them back together. Each half has the same sorting algorithm applied to it. This splitting into halves continues until you are just merging two single element lists.
Time Complexity: O(n log(n)) average and worst case.
Space Complexity: O(n).
4. Quick Sort:
Description: Pick a random element as a pivot point (somewhat arbitrary element in the collection.) and partition the list around this element. All numbers that are less than the pivot element go to the left of the pivot point and all numbers that are greater than the pivot element go to the right of the pivot point. Recursively repeat the partitioning of the list and its sub-lists until the list is sorted. For this program, the initial leftIndex == 0 and the initial rightIndex == len(list)-1.
Time complexity: O(n log(n)) average case and O(n²) worst case complexity.
Space complexity: O(log(n)).
