Bubble Sort
Introduction to sorting
Bubble Sort
Bubble sort is one of the most basic and simplest sorting algorithm, it revolves around two principles of sorting comparing and swapping.
Note: We swap if the preceding term is greater than the later term and in the following example we are comparing the highlighted term.
Example :
( 1 , 2 , 5 , 3 , 0 )
Pass 1:
( 1 , 2 , 5 , 3 , 0 ) // No swap.
( 1 , 2 , 5 , 3 , 0 ) // No swap.
( 1 , 2 , 5 , 3 , 0 ) -> ( 1 , 2 , 3 , 5 , 0 ) // Swap
( 1 , 2 , 3 , 5 , 0 ) -> ( 1 , 2 , 3 , 0 , 5 ) // Swap
After pass 1, we don't need to look at the last term at all since due to pass 1, the last term will always be the greatest number in the list.
Pass 2:
( 1 , 2 , 3 , 0 ) 5 //No swap.
( 1 , 2 , 3 , 0 ) 5 //No swap.
( 1 , 2 , 3 , 0 ) 5 -> ( 1 , 2 , 0 , 3 ) 5 //Swap.
Similarly in pass 3, we don't need to take a look at last term of the current list under consideration.
Pass 3:
( 1 , 2 , 0 ) 3 5 //No swap.
( 1 , 2 , 0 ) 3 5 -> ( 1 , 0 , 2 ) 3 5 // Swap
Similarly in pass 4
Pass 4:
( 1 , 0 ) 2 3 5 -> ( 0 , 1 ) 2 3 5
Since next list will contain only one element , we know that the obtained list is sorted.
with the help of the example we can see an intuition of bubble sort that we basically move the largest number at the end of the list so we don't need to worry about it later, in the process sorting the current list.
Note: We swap if the preceding term is greater than the later term and in the following example we are comparing the highlighted term.
Example :
( 1 , 2 , 5 , 3 , 0 )
Pass 1:
( 1 , 2 , 5 , 3 , 0 ) // No swap.
( 1 , 2 , 5 , 3 , 0 ) // No swap.
( 1 , 2 , 5 , 3 , 0 ) -> ( 1 , 2 , 3 , 5 , 0 ) // Swap
( 1 , 2 , 3 , 5 , 0 ) -> ( 1 , 2 , 3 , 0 , 5 ) // Swap
After pass 1, we don't need to look at the last term at all since due to pass 1, the last term will always be the greatest number in the list.
Pass 2:
( 1 , 2 , 3 , 0 ) 5 //No swap.
( 1 , 2 , 3 , 0 ) 5 //No swap.
( 1 , 2 , 3 , 0 ) 5 -> ( 1 , 2 , 0 , 3 ) 5 //Swap.
Similarly in pass 3, we don't need to take a look at last term of the current list under consideration.
Pass 3:
( 1 , 2 , 0 ) 3 5 //No swap.
( 1 , 2 , 0 ) 3 5 -> ( 1 , 0 , 2 ) 3 5 // Swap
Similarly in pass 4
Pass 4:
( 1 , 0 ) 2 3 5 -> ( 0 , 1 ) 2 3 5
Since next list will contain only one element , we know that the obtained list is sorted.
with the help of the example we can see an intuition of bubble sort that we basically move the largest number at the end of the list so we don't need to worry about it later, in the process sorting the current list.
