BUBBLE SORT

 Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example: 

First Pass: 
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, 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 ) 

Algorithm:

1. begin BubbleSort(arr)  
2.    for all array elements  
3.       if arr[i] > arr[i+1]  
4.          swap(arr[i], arr[i+1])  
5.       end if  
6.    end for     
7.    return arr     
8. end BubbleSort 
   

Program:

"""Formulate a Program that implement Bubble sort, to sort a given list of integers in descending order.
  """

def b_sort(x):
    n=len(x)
    for i in range(0,len(x)):
        for j in range(0,n-i-1):
            if x[j] <x[j+1]:
                (x[j],x[j+1])=(x[j+1],x[j])
                '''t=x[j]
                x[j]=x[j+1]
                x[j+1]=t'''
    return x       
print("\n Sorting using Bubble Sorting \n\n Enter values please: ")
x=[int(b) for b in input().split()]
print("\n LIST IS GIVEN BELOW: \n",x)
print("\n SORTED LIST IS GIVEN BELOW: \n", b_sort(x))       

Output:

 Sorting using Bubble Sorting

 Enter values please:
5 1 4 2 8

 LIST IS GIVEN BELOW:
 [5, 1, 4, 2, 8]

 SORTED LIST IS GIVEN BELOW:
 [8, 5, 4, 2, 1]
 

Application:

 W.A.P. to implement list of students with marks and arrange them in ascending order of Total marks.

from random import randint

def b_sort(x):
    n=len(x)
    for i in range(0,len(x)):
        for j in range(0,n-i-1):
            if x[j]['total'] < x[j+1]['total']:
                (x[j],x[j+1])=(x[j+1],x[j])
    return x        
l=[]
for i in range(50):
    l.append( {"name":"abc"+str(i),
    "roll":i,
    "marks":[randint(10,99) for i in range(10)],
    "total":0})
for i in range(50):# l
    for j in l[i]["marks"]:
        l[i]["total"]+=j
b_sort(l)
for i in range(0,10):
    print("\n",l[i])

OUTPUT:

 {'name': 'abc21', 'roll': 21, 'marks': [93, 62, 91, 72, 90, 95, 92, 20, 99, 43], 'total': 757}

 {'name': 'abc43', 'roll': 43, 'marks': [64, 87, 50, 61, 66, 70, 79, 96, 94, 54], 'total': 721}

 {'name': 'abc24', 'roll': 24, 'marks': [94, 68, 95, 39, 75, 66, 72, 57, 85, 69], 'total': 720}

 {'name': 'abc6', 'roll': 6, 'marks': [56, 59, 68, 19, 90, 95, 82, 76, 69, 83], 'total': 697}

 {'name': 'abc28', 'roll': 28, 'marks': [30, 58, 35, 76, 61, 88, 97, 31, 83, 96], 'total': 655}

 {'name': 'abc8', 'roll': 8, 'marks': [39, 59, 35, 83, 84, 28, 96, 95, 69, 60], 'total': 648}

 {'name': 'abc22', 'roll': 22, 'marks': [93, 91, 74, 78, 71, 77, 41, 65, 27, 31], 'total': 648}

 {'name': 'abc29', 'roll': 29, 'marks': [87, 29, 57, 70, 31, 64, 90, 95, 40, 72], 'total': 635}

 {'name': 'abc10', 'roll': 10, 'marks': [99, 65, 53, 53, 12, 59, 75, 96, 40, 77], 'total': 629}

 {'name': 'abc25', 'roll': 25, 'marks': [22, 66, 17, 97, 52, 96, 67, 52, 82, 72], 'total': 623}

 

Optimized Implementation: 
The above function always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop didn’t cause any swap. 

 

FAQ:

What is the best time complexity of bubble sort?

	N^2
	NlogN
	N
	N(logN)^2

 Ans: N

Assume that we use Bubble Sort to sort n distinct elements in ascending order. When does the best case of Bubble Sort occur?

A	When elements are sorted in ascending order
B	When elements are sorted in descending order
C	When elements are not sorted by any order
D	There is no best case for Bubble Sort. It always takes O(n*n) time

Ans: When elements are sorted in ascending order

 

The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order, using bubble sort is

A	11
B	12
C	13
D	10

 Ans: 10

1 : 8, 7, 9, 22, 5, 13, 31 = 4 swaps 

2 : 7, 8, 9, 5, 13, 22, 31 = 3 swaps 

3 : 7, 8, 5, 9, 13, 22, 31 = 1 swap 

4 : 7, 5, 8, 9, 13, 22, 31 = 1 swap 

5 : 5, 7, 8, 9, 13, 22, 31 = 1 swap 

Total 10 swaps are required to sort the array.