Various kind of sorting algorithm and their utility

A sorting algorithm is an algorithm that puts elements of a list in a certain order. Efficient sorting is important for optimizing the use of other algorithms such as search and merge algorithms, which require input data to be in sorted lists; it is also often useful for canonicalizing data and for producing human-readable output.

The term sorting came into the picture, as humans realized the importance of searching quickly. All would have been a mess if the data was kept unordered and unsorted, but fortunately, the concept of sorting came into existence, making it easier for everyone to arrange data in an order, hence making it easier to search.

This means a smallest data element can be searched from a huge data repository if the data is stored in a sorted manner.

There are various sorting methods and techniques that are not only used for sorting algorithms but are also used for analyzing the performance of other algorithms. In this post, you will find a brief description of the different types of sorting algorithms.

So, here are the types of sorting algorithms -

Insertion Sort

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists and is often used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one.

Bubble Sort

Bubble Sort is probably one of the oldest, easiest, straight-forward, inefficient sorting algorithms. It works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is "bubbled" to the end of the list whereas the smaller values sink to the bottom.

Shell Sort

Shell Sort was invented by Donald Shell in 1959. It improves upon insertion sort by moving out of order elements more than one position at a time. The concept behind Shellsort is that insertion sort performs in O(kn) time, where k is the greatest distance between two out-of-place elements. This means that generally, they perform in O(n2), but for data that is mostly sorted, with only a few elements out of place, they perform faster.

Selection Sort

This algorithm is based on the idea of finding the minimum or maximum element in the unsorted array and then putting it in its correct position for a sorted array. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.

Bucket Sort

Bucket sort is mainly useful when an input is uniformly distributed over a range. Bucket sort is a divide and conquers sorting algorithm that generalizes counting sort by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or by recursively applying the bucket sorting algorithm.

Merge Sort

Merge sort algorithm compare two elements of the list and then swaps them in the order required (ascending or descending). It applies the divide and rule concept. Merge sort works on sequential access and can work on large lists.

Heap Sort

Heap Sort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree. Once the data list has been made into a heap, the root node is guaranteed to be the largest (or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.

Quick Sort

Quick Sort is also based on the concept of Divide and Conquer, just like merge sort. But in quicksort, all the heavy lifting(major work) is done while dividing the array into subarrays, while in case of merge sort, all the real work happens during merging the subarrays. In the case of quicksort, the combining step does absolutely nothing.

Comb Sort

Comb sort is a relatively simple sorting algorithm based on bubble sort and originally designed by Wlodzimierz Dobosiewicz in 1980. It was later rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. The basic idea is to eliminate turtles or small values near the end of the list since in a bubble sort these slow the sorting down tremendously. It accomplishes this by initially swapping elements that are a certain distance from one another in the array, rather than only swapping elements if they are adjacent to one another, and then shrinking the chosen distance until it is operating as a normal bubble sort.

Radix Sort

Radix Sort is an algorithm that sorts numbers by processing individual digits. Radix sort can process digits of each number either starting from the least significant digit (LSD) or starting from the most significant digit (MSD). The LSD algorithm first sorts the list by the least significant digit while preserving their relative order using a stable sort. Then it sorts them by the next digit, and so on from the least significant to the most significant, ending up with a sorted list.

Counting sort

In this sort, we count the frequencies of distinct elements of an array and store them in an auxiliary array, by mapping its value as an index of the auxiliary array and then place each element in its proper position in the output array.

 

 

There are many more sorting algorithms and they can be combined for large data sets that exceed system memory and time. Hope you have got an idea of the various types of sorting algorithms which can be used as a part of bigger programs.

You can share your experiences with us in the comment section. Thank you!