1) Bubble Sort - Big O(n^2):
The Bubble Sort makes multiple passes through a list, comparing two adjacent items and swapping them if they are out of order. For example bubble sort on ( 9 1 4 3 10 ):
First Pass:
( 9 1 4 3 10 )
( 1 9 4 3 10 ), The algorithm compares the first two items and swaps them since 9 > 1.( 1 9 4 3 10 )
( 1 4 9 3 10 ), Swap since 9 > 4( 1 4 9 3 10 )
( 1 4 3 9 10 ), Swap since 9 > 3( 1 4 3 9 10 )
( 1 4 2 9 10 ), Since the 10 > 9 the algorithm doesn't swap the numbers.After multiple passes of bubble sort the list will be completely sorted.
2) Selection Sort - Big O(n^2):
The Selection Sort finds the biggest number in the list and puts it to the proper location.
Example: bubble sort on ( 9 1 4 3 10 ):
( 9 1 4 3 10 ) -> ( 9 1 4 3 10 ) Since 10 is the largest item in the list, the algorithm is not going to change anything.
( 9 1 4 3 10 ) -> ( 3 1 4 9 10 ) Since 9 is the second greatest item in the list, the algorithm swaps 9 with 3.
And so on till the list is sorted.
3) Insertion Sort - Big O(n^2):
The algorithm always keeps a part of the list sorted and adds up items to the sorted part of the list as it progresses. Example: ( 9 1 4 3 10 )
( 9 1 4 3 10 ) -> ( 1 9 4 3 10 ) Swaps 9 and 1 because 9 > 1
( 1 9 4 3 10 ) -> ( 1 4 9 3 10 ) Inserts 4 between 1 and 0.
( 1 4 9 3 10 ) -> ( 1 3 4 9 10 ) Inserts 3 to the proper location.
( 1 3 4 9 10 ) -> ( 1 3 4 9 10 ) The list is fully sorted.
4) Shell Sort - Big O(n^2):
The Shell Sort improves Insertion Sort by splitting the list into multiple parts and sorting them with Insertion Sort. The algorithm uses an increment i as a gap between the numbers. After every pass the algorithm reduces the increment.
Example: sorting ( 9 1 4 3 7 8 2 5 6) with i = 3
( 9 1 4 3 7 8 2 6 5) The highlighted items are the first numbers of the sublists.
Doing the insertion sort through the sublists we get:
( 1 4 9 3 7 8 2 5 6) setting i = 2
( 1 4 3 9 7 8 2 5 6 ) After this the algorithm does the standard Insertion Sort.
( 1 2 3 4 5 6 7 8 9 )
5) Merge Sort - Big O(logn):
It is a recursive algorithm that splits the list in half till every sublist consists of 1 item. Then, the algorithm merges 2 adjacent sublists and sorts them again. Example:
1) ( 9 1 4 3 10 )
-> 9, 1, 4 , 3, 10 -> (1, 9), (3, 4) (10) -> (1, 3, 4, 9) (10)
2)
