What is Sorting in Data Structure
Sorting algorithm in data structure refers to ordering data in both ascending and descending order to get a meaningful data which can be analyze easily. we formally define sorting problem as:
Input: A sequence of n numbers <$a_{1}.a_{2}…………….a_{n}$>
Output: A permutation (re-ordering) < $ a^{‘}_{1},a^{‘}_{2}…………………………..a^{‘}_{n}$>
Example of Sorting Problem:
Input < 5,1,6,9,2,1,4>
Output 1 1 2 4 5 6 9
In the world of computer algorithm sorting means to put into some well defined order sorting can also defined to arrange elements in non-decreasing order.
Classification of Sorting:
Internal Sort: A sort is called internal sort if the elements it is sorting are in main memory that is RAM.
External Sort: A Sort is called external if the elements it is sorting are in auxiliary storage.
Types of Sorting in Data Structure
Insertion Sort: Insertion Sort is a simple algorithm is a simple algorithm that place right element at right position in each step done as we do while sorting a playing cards.
Selection Sort: Selection Sort refers to find the largest ( or smallest ) element in an array repeatedly and move that element to its final position.
Quick Sort: Quick sort algorithm used in many process as it is not difficult to implement. It is based on divide and conquer approach.
Merge Sort: It a sort based on divide and conquer approach . In this the list is divide into half and then sorted after that is merged and finally sorted list is obtained,
Heap Sort: The heap sort is an array that can be viewed as a complete binary tree form structure.
Bubble Sort: Bubble Sort also known as exchange sort in which repeatedly list is sorted through comparing two items at a time and swapping them if they are wrong in order
Comparison Between Sorting Algorithms
| Algorithm | Insertion Sort | Selection Sort | Quick Sort | Merge Sort | Heap Sort | Bubble sort |
| Space complexity | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| Time complexity Best -case | $\Omega$(n) | $\Omega(n^{2})$ | $\Omega(n log n)$ | $\Omega(n log n)$ | $\Omega(n log n)$ | $\Omega$(n) |
| Time complexity Worst-case | $O(n^{2})$ | $O(n^{2})$ | O($n^{2}$) | O (n log n) | O (n log n) | $O(n^{2})$ |
| Time Complexity Average – case | $\theta(n^{2})$ | $\theta(n^{2})$ | $\theta(n log n)$ | $\theta(n log n)$ | $\theta(n log n)$ | $\theta(n^{2})$ |
| Real life Application | Tailor arrange shirt in closet | When an small data set need to be sorted | Sorting Papers | Sorting large Data set | Sim Card Store where there are many customers in line | Contact list on your phone is sorted in alphabetical order |