6/7/2021 OneNote
Sorting Techniques
23 May 2020 21:46
1. Number of comparisons -
This determines the time complexity.
2. No. of swaps-
3. Adaptive -
Time taken if elements are mostly sorted already.
If less time is taken(less comparisons made) for a sorted list then we can say the sorting is adaptive.
4. Stable -
If for same value their order is preserved the sorting is called stable.
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 1/8
6/7/2021 OneNote
i.e. Previous sorting is preserved.
5. If extra memory space is required.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
BUBBLE SORT -
(seems like rising of bubble when a stone settles at the bottom)
• If k number of largest/smallest elements are require only that many passes.
• Time complexity is determined form number of comparisons hence o(n^2)
• It is Stable.(since no swap if elements are equal)
• It can be made adaptive.
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 2/8
6/7/2021 OneNote
This makes the sorting adaptive. (only 1 pass(less #comparisons) if list is already sorted)
(this is called adaptive bubble sort)
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 3/8
6/7/2021 OneNote
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
INSERTION SORT -
(basically element is inserted in the sorted position)
• Intermediate passes unlike bubble sort doesn't give any useful result.
• It is more useful (or designed for) linked lists.
• It is adaptive. (by nature)
• It is stable(no shifting for equal element)
If array is already present we can perform in place sorting.
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 4/8
6/7/2021 OneNote
Here n is the index of the last element.
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 5/8
6/7/2021 OneNote
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
BUBBLE SORT VS INSERTION SORT -
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SELECTION SORT-
• In each pass the smallest element is searched and put to the beginning of the array.
• It sorts elements with minimum no. of swaps.
• Intermediate results are useful.
• It is not stable.(because on swapping
(since it is not always done on adjacent elements) the order of equal elements can be altered)
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 6/8
6/7/2021 OneNote
• It is not adaptive and cannot be made adaptive.
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 7/8
6/7/2021 OneNote
https://onedrive.live.com/redir?resid=EAE757CE2D8A8DDE%21426&page=Edit&wd=target%28DSnA Course.one%7Cf1a18435-74a… 8/8
