Sorting techniques in data structures

Sorting techniques is the process to identify element according to the size of the data. In addition, Data Structure is the collection and organisation of data to provide logical relationship between data. Moreover, there are many applications of sorting. For instance, we use sorting in contact applications in our mobile applications.

Let us take a look at some of the sorting techniques.

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort
Shell Sort

Bubble Sort (First Sorting Technique)

Firstly, in bubble sort, each and every element compares itself with the next element starting from the first position. Secondly, this kind of sort applies to small amount of data. Moreover, in computer system, memory saving procedure uses bubble sort.

For instance, we have a data like 50, 40, 10, 15. Here 50 will be compared with 40 then 10 and lastly 15. And outcome will be 10, 15, 40 and 50 after some iterations.

Selection Sort

Firstly, in selection sort, we find the smallest key value and first element replaces itself with the smallest key. And second element with second smallest key and so on.

For instance, values are 45, 55, 75, 15, 65.

First Iteration: 15, 55, 75, 45, 65.
Second Iteration: 15, 45, 75, 55, 65.
Third Iteration: 15, 45, 55, 75, 65.
Fourth Iteration: 15, 45, 55, 65, 75.
Hence, result is: 15, 45, 55, 65, 75.

Insertion Sort

In Insertion Sort, we consider the first position as sorted and then compare every element with the sorted element.

For instance, data is 6, 5, 3, 1,8.

First Iteration: 5, 6, 3, 1, 8.
Second Iteration: 3, 5, 6, 1, 8
Third Iteration: 1, 3, 5, 6, 8.

Merge Sort

Merge Sort is useful when we have a large amount of data. This sorting technique uses divide and conquer strategy. Firstly, it divides the data, sorts the element and then combines the data.

Secondly, it is one of the efficient sorting algorithm.

Quick Sort

In quick sort, there is a pivot value along with i and j. For instance, we have an array of size 8, here the first value will be the pivot value. Moreover, Iteration of i starts from the beginning of array and iteration of j starts from the end of array.

Secondly, values for i and jth element is compared , if i<j then we exchange the values.

Time Complexity Table for Sorting techniques

Sorting Technique	Best Case	Average Case	Worst Case
Bubble Sort	O(n)	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)
Merge Sort	O(nlogn)	O( nlogn)	O( nlogn)
Quick Sort	nlogn	nlogn	O(n²)
Heap Sort	O( nlogn)	O(nlogn)	O(nlogn)

Summary

In conclusion, we have learnt about the different sorting techniques in data structures. Moreover, we have seen the time complexities of different sorts.