In this article, we are going to discuss different sorting algorithms. We will walk you through the different sorting algorithms with every step that comes in implementation. The implementation part will be in Python. You can easily convert it into any language once you get the algorithm. That’s the matter of language syntax. We will see different algorithms from worst to best in this tutorial. So, don’t worry. Follow the article and implement them. Let’s dive into the sorting algorithms.
Insertion Sort
Insertion sort is one of the simple sorting algorithms. It’s easy to implement. And it will cost you more time to sort an array. It won’t be used in most of the cases for sorting for larger arrays. The insertion sort algorithm maintains sorted and unsorted sub-parts in the given array. The sorted sub-part contains only the first element at the beginning of the sorting process. We will take an element from the unsorted array and place them in the correct position in the sorted sub-array. Let’s see the visual illustrations of insertion sort step by step with an example.
Let’s see the steps to implement the insertion sort.
Initialize the array with dummy data (integers). Iterate over the given array from the second element. Take the current position and element in two variables. Write a loop that iterates until the first element of the array or the element occurs that is less than the current element. Update the current element with the previous element. Decrement of the current position. Here, the loop must reach either the start of the array or find a smaller element than the current element. Replace the current position element with the current element.
The time complexity of the insertion sort is O(n^2), and the space complexity if O(1). That’s it; we’ve sorted the given array. Let’s run the following code. I hope you have installed Python, if not check out the installation guide. Alternatively, you can use an online Python compiler.
Selection Sort
The selection sort is similar to the insertion sort with a slight difference. This algorithm also divides the array into sorted and unsorted sub-parts. And then, on each iteration, we will take the minimum element from the unsorted sub-part and place it in the last position of the sorted sub-part. Let’s illustrations of selection sort for better understanding.
Let’s see the steps to implement the selection sort.
Initialize the array with dummy data (integers). Iterate over the given array. Maintain the index of the minimum element. Write a loop that iterates from the current element to the last element. Check whether the current element is less than the minimum element or not. If the current element less than the minimum element, then replace the index. We have the minimum element index with us. Swap the current element with the minimum element using the indexes.
The time complexity of the selection sort is O(n^2), and the space complexity if O(1). Try to implement the algorithm as it is similar to the insertion sort. You can see the code below.
Bubble Sort
Bubble sort is a simple algorithm. It swaps the adjacent elements on each iteration repeatedly until the given array is sorted. It iterates over the array and moves the current element to the next position until it is less than the next element. Illustrations help us understand the bubble sort visually. Let’s see them.
Let’s see the steps to implement the bubble sort. The time complexity of the bubble sort is O(n^2), and the space complexity if O(1). You can easily implement the bubble sort by now. Let’s see the code.
Merge Sort
Merge sort is a recursive algorithm to sort the given array. It’s more efficient than the previously discussed algorithms in terms of time complexity. It follows the divide and conquers approach. The merge sort algorithm divides the array into two halves and sorts them separately. After sorting the two halves of the array, it merges them into a single sorted array. As it’s a recursive algorithm, it divides the array till the array becomes the simplest (array with one element) one to sort. It’s time for illustration. Let’s see it.
Let’s see the steps to implement the merge sort.
Initialize the array with dummy data (integers). Write a function called merge to merge sub-arrays into a single sorted array. It accepts the arguments array, left, mid, and right indexes. Get the lengths of left and right sub-arrays lengths using the given indexes. Copy the elements from the array into the respective left and right arrays. Iterate over the two sub-arrays. Compare the two sub-arrays elements. Replace the array element with the smaller element from the two sub-arrays for sorting. Check whether any elements are remaining in both the sub-arrays. Add them to the array. Write a function called merge_sort with parameters array, left and right indexes. If the left index is greater than or equal to the right index, then return. Find the middle point of the array to divide the array into two halves. Recursively call the merge_sort using the left, right, and mid indexes. After the recursive calls, merge the array with the merge function.
The time complexity of the merge sort is O(nlogn), and the space complexity if O(1). That’s it for the merge sort algorithm implementation. Check the code below.
Conclusion
There are many other sorting algorithms, but above are some of the frequently used. Hope you enjoyed learning the sorting. Next, find out about search algorithms. Happy Coding 🙂 👨💻
