Sorting Algorithms

Algorithms are sequenced steps of instructions proposing a generalized solution for a problem. Algorithms determine the efficiency of a coding solution. They are divided into different categories depending on their nature of implementation. In this blog, we will discuss Sorting Algorithms focusing on their description, the way they work, and some common implementations.

 

 

Sorting Algorithm:

As the name describes, the sorting algorithm is generally used to sort an array in a particular order. An array sorted in an ascending order means that every successor element in an array is greater than the previous one. A sorting algorithm takes an array as an input, performs sorting operations on it, and outputs a permutation of the array that is now sorted.

Array {a, b, c, d} is alphabetically sorted.

Array {1, 2, 3, 4} is sorted in ascending order.

Generally, sorting algorithms are divided into two types: Comparison Sort and Integer Sort.

 

Comparison Sort:

Comparison sort algorithms compare elements at each step to determine their position in the array. Such algorithms are easy to implement but are slower. They are bounded by O(nlogn), which means on average, comparison sorts cannot be faster than O(nlogn).

 

 

Integer Sort:

Integer sort algorithms are also known as counting algorithms. The integer sort algorithm checks for each element, say x, how many elements are smaller than x and places x at that location in an array. For element x, if 10 elements are less than x then the position of element x is at index 11. Such algorithms do not perform comparisons and are thus not bound by Ω (nlogn).

The efficiency of the selected sorting algorithm is determined by its run time complexity and space complexity.

 

Stability of a Sorting Algorithm:

A sorting algorithm is said to be stable if it preserves the order of the same or equal keys in the output array as it is in the input array.

Keys are the values based on which algorithm is sorting an array.

Below is an example of stable sorting,

Following is an unstable sorting as the order of equal keys is not preserved in the output.

Next, let’s discuss some commonly used sorting algorithms.

 

Insertion Sort:

This is a comparison-based algorithm. It takes one element, finds its place in the array, places it there, and in doing so sorts the whole array. For an array of size n, insertion sort considers the first element on the left as a sorted array and all the remaining n-1 elements on the right as an unsorted array. It then picks the first unsorted element (element number 2 of the array) and places it with a sorted element on the left moving elements if necessary. Now there are two arrays, a sorted array of size 2 and an unsorted of size n-2. The process continues until we get the whole array sorted, starting from the left. The best case of insertion sort is O(N) and the worst-case O(N^2).

 

 

Selection Sort:

Selection sort is quite an easy algorithm in terms of implementation. It selects the smallest element present in an array and replaces it with the first element. It again scans for the smallest element in the remaining n-1 array and replaces it with the second element or the first element of the unsorted (n-1) array. The process of selecting the smallest element and replacing it continues until the whole array is sorted. The selection sort algorithm has the best and worst-case of O(N^2).

 

 

Merge Sort:

Merge is a comparison-based algorithm that works on merging two sorted arrays. The technique used by the merge sort is divide and conquer. It divides the array into two subarrays, performs sorting on them separately, either recursively or iteratively, and then merges these two sorted subarrays. The result is a sorted array. Merge sort works in O(nlogn) run time.

 

 

Heap Sort:

The comparison-based heap sort algorithm uses a binary heap data structure for sorting an array. A max-heap is formed from an unsorted array. The largest element from the binary heap is selected. As it is max-heap, the root is the largest value. This maximum value is placed at the end of an array. The heap shrinks by 1 element and the array increases by 1 element. Again, the above process is applied to the remaining heap. That is, convert it into max-heap and then replace the root (maximum) element with the last element. The process is repeated till we get a sorted array and the heap is shrunk to 0 elements. The run time of heap sort is O(nlogn).

 

 

Quick Sort:

Quicksort works on the divide and conquer strategy. It selects a pivot element and forms two subarrays around this pivot. Suppose the pivot element is A[y]. Two subarrays are sorted as A[x,… y-1] and A[y+1,… z] such that all elements less than the pivot are in one subarray, and all elements greater than the pivot are in the second subarray. The subarrays can be sorted recursively or iteratively. The outcome is a sorted array. The average run time complexity of a quick sort is O(nlogn).

 

 

Bubble Sort:

This comparison-based sorting algorithm compares elements of an array in pairs. The algorithm ‘bubbles’ through the entire array from left to right, considering two elements at a time and swapping the greater element with the smaller element of the pair. For an array A, element A[0] is compared with element A[1]. If element A[0] > A[1], they are swapped. Next, elements A[1] and A[2] are compared and swapped if required. These two steps are repeated for an entire array. The average run time complexity of Bubble sort is O(n2) and is considered an inefficient algorithm.

 

 

Shell Sort:

Shell sort algorithm, in a way, works on insertion sort. It is considered faster than the insertion sort itself. It starts by sorting subsets of the entire array. Gradually the size of subarrays is increased till we get a complete sorted array as a result. In other words, shell sort partially sorts the array elements and then applies insertion sort on the entire array.

 

Shell sort is generally optimized using different methods to increase the size of subsets. The most commonly used method is Knuth’s method. The worst case of shell run time is O(n^(3/2) using Knuth’s method.

 

 

Distribution Sort Algorithms:

Sorting algorithms where input is distributed into substructure, sorted, and then combined at the output are distribution sort algorithms. Many merge sort algorithms are distribution sort algorithms. Radix sort is an example of distribution sorting.

Counting Sort:

Counting sort is an integer-based sorting algorithm instead of a comparison-based sorting algorithm. The algorithm works on the assumption that every element in the input list has a key value ranging from 0 to k, where k is an integer. For each element, the algorithm determines all the elements that are smaller than it, and in this way places that element at an appropriate location in the output list. For this, the algorithm maintains three lists – one as an input list, the second as a temporary list for key values, and the third as an output list.

Counting sort is considered as an efficient sorting algorithm with a run time of Θ(n) where the size of the input list, n, is not much smaller than the largest key value of the input list, k.

 

Radix Sort:

Radix sort works on the subarrays and uses the counting sort algorithm to sort them. It groups the individual keys that take the same place and value. It sorts from the least significant digit to the most significant digit. In base ten, radix sort will first sort digits in 1’s place, then at 10’s place, and so on. The sorting is done using the counting sort algorithm. Counting sort can sort elements in one place value. As an example, base 10, can sort from 0 to 9. For 2-digit numbers, it will have to deal with base 100. Radix sort, on the other hand, can handle multi-digit numbers without dealing with a large range of keys.

The list [46, 23, 51, 59] will be sorted as [51, 23, 46, 59] as for 1’s place value 1<3<6<9. Sorting of second place value will give [23, 46, 51, 58].

Another important property of the radix sort is its stability. It is a stable sorting algorithm. The runtime of radix sort is O(n) which means it takes a linear time for sorting.

 

Ending Note:

Sorting algorithms are quite important in computer science as they help in reducing the complexity of the problem. The sorting algorithms that we discussed above have useful applications in databases, search algorithms, data structure, and many other fields of computer science.

 

 

Get one step closer to your dream job!

Prepare for your interview by supplementing your technical knowledge. Our Job Interview Questions Book Series is designed for this very purpose, aiming to prepare you for HR questions you’ll most likely be asked. Check out the book here! panels.