Sorting: Sorting is a technique used to sort a given data(array) in either ascending or descending order.
Hence, There are different such Algorithms present –
- Bubble sort.
- Selection sort.
- Merge sort.
- Quicksort.
Why analysis of different sorting Algorithm is important ?
There are many sorting algorithms. All of them have different time and space complexity, each Algorithm has its advantages and disadvantages. So comparative study is helpful to understand which sorting Algorithm suits to sort data in a given constraint.
So, This analysis is based on time complexity, size of input data, space complexity, advantage, disadvantages, application, and efficiency of sorting Algorithms.
1. Bubble sort
- Based on – Comparison of 2 adjacent elements of an array.
- Best case complexity – O(n).
- Worst-case complexity – O(n^2).
- Space – O(1).
- Input data – suitable for small data.
- Efficiency – inefficient.
- Speed – slow.
- Stability – yes.
Pseudocode :-
Application –
- As bubble sort is simple. This Algorithm can be used to teach the basics of sorting.
- Use to sort data.
Advantage –
- it can sort data in ascending order.
- It’s suitable when the array is already sorted.
Disadvantages –
- it’s only suitable for small data.
- It’s suitable for large data only when it’s nearly sorted.
2. Selection sort
- Based on – Division of an array in 2 sub-array. 1 sorted and other unsorted sub-array.
- Best case complexity – O(n^2).
- Worst-case complexity – O(n^2).
- Space – O(1).
- Input data – suitable for small data.
- Efficiency – efficient than bubble sort.
- Speed – Faster than bubble sort.
- Stability – no.
Pseudocode:-
Application –
- It Can sort a small list of arrays.
Advantage –
- It is also Used to sort small data.
Disadvantages –
- The cost of swapping elements of an array is high.
3. Merge sort
- Based on – Divide and conquer.
- Best case complexity – O(nlog(n)).
- Worst case complexity – O(nlog(n)).
- Space – O(n).
- Input data – It is suitable for large input data.
- Efficiency – efficient than bubble and selection sort. More efficient Than Quicksort for large input.
- Speed – Same speed for all data length.
- Stability – yes stable.
Pseudocode –
Application –
- This sorting is used to sort a linked list in O(N log N) time.
- Through this sorting, the linked list takes no extra space for sorting.
- Use in online sorting.
Advantage –
- Can use large input data.
- Also, Take no extra space.
Disadvantages –
- Read the whole array if the array is already sorted.
4. Quicksort
- Based on – Divide and conquer.
- Best case complexity – O(nlog(n)).
- Worst-case complexity – O(n^2).
- Input data – suitable for large input data.
- Efficiency – efficient, More systematic than merge sort for small input data.
- Speed – Faster than other sorting algorithms.
- Stability – not stable.
Pseudocode :-
Application –
- Use in commercial applications.
- Use in game development.
Advantage –
- One of the Fastest Sorting Algorithms.
- Easy performance.
Disadvantages –
- It’s the worst case is the average case of a bubble, selection sort.
Tabular comparison :
| characteristics | Bubble sort | Selection sort | merge sort | Quicksort |
| Suitable for | Small data | Small/large already sorted | Large data | Large data |
| Efficiency | Not more efficient | More efficient than bubble sort | More efficientThen Quicksort for large input. | More efficient than merge sort for small input data. |
| Complexity | O(n) | O(n^2) | O(nlogn) | O(nlogn) |
| Stability | yes | no | yes | no |
| Speed | slow | Faster than bubble sort | Same speed for all data length. | Faster than other sorting algorithms. |
CONCLUSION on sorting:-
If input data is small then use bubble sort, selection sort.
If input data is large nearly sorted, we can still use bubble selection sort. Selection sort is more efficient than bubble sort. So, For a low budget, sorting Algorithms go for bubble sort. However, For large input data use a quick or merge sort Algorithm. If data needs to be sorted quickly then use the Quicksort Algorithm.
Written by: Yatika Yadav
Reviewed By: Soutik Maity
If you are Interested In Machine Learning You Can Check Machine Learning Internship Program
Also Check Other Technical And Non Technical Internship Programs
