Types of Sorting Techniques

What is sorting?

Sorting is a process that organizes a collection of numerical or alphabetical data into ascending or descending order. Sorting process arranges the data into meaningful order so that you can analyse it more effectively. Efficient sorting is important for optimizing the efficiency of other algorithms that require input data to be in sorted lists.

Why sorting is required?

In our day-to-day life we keep our necessary things at particular place, in a particular way to get it easily whenever needed. We sort them in various aspects as per the requirement for their easy handling. This sorting mechanism saves our time in finding that thing too.

In the similar manner, if we think about the huge data structures made in order to save large amount of data, there we require such sorting algorithm. In several applications where huge amount of data is stored, there is a need of sorting that data in a particular order to access it efficiently.

To overcome above mentioned needs, sorting of data in particular order is required. This sorting can be done by different techniques and algorithms using a computer program.

Stable and Not Stable Sorting

If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear, it is called stable sorting.
If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which they appear, it is called unstable sorting.

Sorting techniques:

We have many sorting techniques to carry out the sorting in efficient manner. These sorting techniques mainly differ in their algorithm or pattern of sorting data.

1. Quick Sort:

Quick sort is a highly efficient sorting algorithm which is based on partitioning of array of data into smaller arrays. In quick sort, a large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets.

Complexity	Best Case	Average Case	Worst Case
Time Complexity	O(n) for 3 way partition or O(n log n) simple partition	O(n log n)	O(n²)
Space Complexity			O(log n)

2. Bubble Sort:

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

Scenario	Complexity
Space	O(1)
Worst case running time	O(n²)
Average case running time	O(n)
Best case running time	O(n²)

3. Merge Sort:

Merge sort is a sorting technique based on divide and conquer technique. In merge sort array is divided and all elements are considered separately. Then group of 2 elements is made. This procedure is done for all elements of array and each group is sorted. After that, two arrays are merged into single array. And these greater arrays are sorted. This process is done for every two small array. Such process is continued until we get sorted array in ascending/descending order.

Complexity	Best case	Average Case	Worst Case
Time Complexity	O(n log n)	O(n log n)	O(n log n)
Space Complexity			O(n)

4. Insertion Sort:

In insertion sort, in each iteration, sorting algorithm picks one element from the input data, finds the exact location for that element within the sorted array, and inserts it there.

Hence, named as “insertion sort”. It repeats this insertion procedure until no element is left. It takes one array element (except 1st element of array) and compare it with one prior (previous) element. If prior element is smaller, then u can say that array element is on proper place. If prior element is greater, move it one step forward in array and compare array element with another prior element. Continue this process until you get smaller element. When you get smaller element, stop shifting and insert array element on that correct position. This entire procedure is called “one pass” which places one element at its exact location. Continue this procedure for all elements and at last you will get sorted array.

Complexity	Best Case	Average Case	Worst Case
Time	Ω(n)	θ(n²)	o(n²)
Space			o(1)

5. Selection Sort:

Selection sort finds the smallest element of the array and exchange it with the element on the first position. Then Find the second smallest element and exchange it with the element on the second position. Continue this process until the entire array is sorted.

Complexity	Best Case	Average Case	Worst Case
Time	Ω(n)	θ(n²)	o(n²)
Space			o(1)

6. Heap Sort:

Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. The heap can be represented by a binary tree or array.

Complexity	Best Case	Average Case	Worst case
Time Complexity	Ω(n log (n))	θ(n log (n))	O(n log (n))
Space Complexity			O(1)

7. Radix Sort:

Radix sort is an integer sorting algorithm that sorts data with integer keys by grouping the keys by individual digits that share the same significant position and value (place value). Radix sort uses counting sort as a subroutine to sort an array of numbers.

Complexity	Best Case	Average Case	Worst Case
Time Complexity	Ω(n+k)	θ(nk)	O(nk)
Space Complexity			O(n+k)

8. Bucket Sort:

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

Algorithm	Complexity
Space	O(1)
Worst Case	O(n²)
Best Case	Ω(n+k)
Average Case	θ(n+k)

Types of Sorting Techniques

Thursday, December 24, 2020