Sorting Algorithms
Introduction
Sorting is a technique or method of rearranging the elements of a data structure into some specific order such as highest to lowest or lowest to highest or some alphabetical order.
Sorted data always makes it easier to search for a given data easily. Binary Search is one such efficient algorithm which searches for an element in log(n) time complexity whereas linear search takes log(n) time complexity.
Real Time Scenarios :
For example if we have a number of students who are identified by their id (1, 2, 3 etc) and we have student record files which are placed in a rack. Whenever required we need to pick the required student record from the set of records, once the work is over we need to put it back. If we have less number of files it is easier to check files one by one to get the required one. What about we have a large number of student files ? This is where we need to arrange the files in a manner such that we can pick the student record easily. So we can keep the files in sorted order by student id and whenever we need a particular student file randomly we look at the student id on file and accordingly we search further.
Suppose we want to open page number "x" of a book and it is obvious that page numbers are always in ascending order. We just open a random page which has page number "y", we do the following operations :
- If x = y – we found the required page
- If x > y – it means we try to search again right side of page y
- If x < y – it means we try to search again left side of page y
Similar to the above two cases, in real life we find many such use cases where sorting helps a lot and are listed below :
- Arranging students of as class in order of their height
- Students roll numbers usually assigned based on the alphabetical order of the student names.
- During election poll counting, we are mostly interested to know who is leading the party or the order of the parties (descending order of number of votes), and the ordering changes on a real time basis. This is called Online Sorting.
- In any e-commerce website we tend to sort items by price from lowest to highest or highest.
Sorting Algorithms
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
Comparison of Sorting Algorithms
| Algorithm | Best Case Time Complexity | Average Case Time Complexity | Worst Case Time Complexity | Space Complexity |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |