Hi everyone, I am going to start a blog series from today where I will be revising some concepts which are important for any entry-level IT interview. The first series is starting with different sorting techniques. In this blog, Bubble sort is discussed and will revise sorting first for a few days by picking one concept on a daily basis.
Bubble Sort: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
Example: Sort series in ascending order
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, the algorithm compares the first two elements and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
The number of passes is decided by the no. of elements in the array/list. Example:
size of list=5, so n=5
No. of passes= n-1 =5-1=4
Now, let’s see a program that I wrote in Python to get a better understanding at this:
list1=[10000,4000,0,900,10]
passes=len(list1)-1 // len() func to find size of list
while(passes!=0):
for i in range(0,len(list1)-1):
if(list1[i]>list1[i+1]):
temp=list1[i]
list1[i]=list1[i+1]
list1[i+1]=temp
passes=passes-1
print(list1)
OUTPUT: [0, 10, 900, 4000, 10000]
Reference for definition: https://www.geeksforgeeks.org/bubble-sort/
P.S: Keep Learning 🙂
deepti96.wordpress.com 