What is Bubble Sort?

Bubble Sort

In Bubble sort, Each element of the array is compared with its adjacent element. The algorithm processes the list in passes. A list with n elements requires n-1 passes for sorting. Consider an array A of n elements whose elements are to be sorted by using Bubble sort. The algorithm processes like following.

1. In Pass 1, A[0] is compared with A[1], A[1] is compared with A[2], A[2] is compared with A[3] and so on. At the end of pass 1, the largest element of the list is placed at the highest index of the list.
2. In Pass 2, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of Pass 2 the second largest element of the list is placed at the second highest index of the list.
3. In pass n-1, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of this pass. The smallest element of the list is placed at the first index of the list.

Algorithm :

• Step 1: Repeat Step 2 For i = 0 to N-1
• Step 2: Repeat For J = i + 1 to N - I
• Step 3: IF A[J] > A[i]
  SWAP A[J] and A[i]
  [END OF INNER LOOP]
  [END OF OUTER LOOP
• Step 4: EXIT

Complexity

Scenario	Complexity
Space	O(1)
Worst case running time	O(n2)
Average case running time	O(n)
Best case running time	O(n2)

C Program

1. #include<stdio.h>  
2. void main ()  
3. {  
4.     int i, j,temp;   
5.     int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
6.     for(i = 0; i<10; i++)  
7.     {  
8.         for(j = i+1; j<10; j++)  
9.         {  
10.             if(a[j] > a[i])  
11.             {  
12.                 temp = a[i];  
13.                 a[i] = a[j];  
14.                 a[j] = temp;   
15.             }   
16.         }   
17.     }   
18.     printf("Printing Sorted Element List ...\n");  
19.     for(i = 0; i<10; i++)  
20.     {  
21.         printf("%d\n",a[i]);  
22.     }  
23. }  

Output:

Printing Sorted Element List . . . 
7
9
10
12
23
34
34
44
78 
101

---

C++ Program

1. #include<iostream>  
2. using namespace std;  
3. int main ()  
4. {  
5.     int i, j,temp;   
6.     int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
7.     for(i = 0; i<10; i++)  
8.     {  
9.         for(j = i+1; j<10; j++)  
10.         {  
11.             if(a[j] < a[i])  
12.             {  
13.                 temp = a[i];  
14.                 a[i] = a[j];  
15.                 a[j] = temp;   
16.             }   
17.         }   
18.     }   
19.     cout <<"Printing Sorted Element List ...\n";  
20.     for(i = 0; i<10; i++)  
21.     {  
22.         cout <<a[i]<<"\n";  
23.     }  
24.     return 0;  
25. }  

Output:

Printing Sorted Element List ...
7
9
10
12
23
23
34
44
78
101

---

Java Program

1. public class BubbleSort {  
2.     public static void main(String[] args) {  
3.     int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
4.     for(int i=0;i<10;i++)  
5.     {  
6.         for (int j=0;j<10;j++)  
7.         {  
8.             if(a[i]<a[j])  
9.             {  
10.                 int temp = a[i];  
11.                 a[i]=a[j];  
12.                 a[j] = temp;   
13.             }  
14.         }  
15.     }  
16.     System.out.println("Printing Sorted List ...");  
17.     for(int i=0;i<10;i++)  
18.     {  
19.         System.out.println(a[i]);  
20.     }  
21. }  
22. }  

Output:

Printing Sorted List . . . 
7
9
10
12
23
34
34
44
78 
101 

---

C# Program

1. using System;  
2.                       
3. public class Program  
4. {  
5.     public static void Main()  
6.     {  
7.         int i, j,temp;   
8.     int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
9.     for(i = 0; i<10; i++)  
10.     {  
11.         for(j = i+1; j<10; j++)  
12.         {  
13.             if(a[j] > a[i])  
14.             {  
15.                 temp = a[i];  
16.                 a[i] = a[j];  
17.                 a[j] = temp;   
18.             }   
19.         }   
20.     }   
21.     Console.WriteLine("Printing Sorted Element List ...\n");  
22.     for(i = 0; i<10; i++)  
23.     {  
24.         Console.WriteLine(a[i]);  
25.     }  
26.     }  
27. }  

Output:

Printing Sorted Element List . . . 
7
9
10
12
23
34
34
44
78 
101 

---

Python Program

1. a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]  
2. for i in range(0,len(a)):  
3.     for j in range(i+1,len(a)):  
4.         if a[j]<a[i]:  
5.             temp = a[j]  
6.             a[j]=a[i]  
7.             a[i]=temp  
8. print("Printing Sorted Element List...")  
9. for i in a:   
10.     print(i)  

Output:

Printing Sorted Element List . . . 
7
9
10
12
23
34
34
44
78 
101 

---

Rust Program

1. fn main()  
2. {  
3.     let mut temp;  
4.  let mut a: [i32; 10] = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
5.     for i in 0..10  
6.     {  
7.         for j in (i+1)..10  
8.         {  
9.             if a[j] < a[i]  
10.             {  
11.                 temp = a[i];  
12.                 a[i] = a[j];  
13.                 a[j] = temp;   
14.             }  
15.         }   
16.     }   
17.     println!("Printing Sorted Element List ...\n");  
18.     for i in &a  
19.     {  
20.         println!("{} ",i);  
21.     }  
22. }  

Output:

Printing Sorted Element List . . . 
7
9
10
12
23
34
34
44
78 
101
4 

---

JavaScript Program

1. <html>  
2. <head>  
3. <title>   
4. Bubble Sort   
5. </title>   
6. </head>   
7. <body>  
8. <script>   
9.     var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
10.     for(i=0;i<10;i++)  
11.     {  
12.         for (j=0;j<10;j++)  
13.         {  
14.             if(a[i]<a[j])  
15.             {  
16.                  temp = a[i];  
17.                 a[i]=a[j];  
18.                 a[j] = temp;   
19.             }  
20.         }  
21.     }  
22.     txt = "<br>";  
23.     document.writeln("Printing Sorted Element List ..."+txt);  
24.     for(i=0;i<10;i++)  
25.     {  
26.         document.writeln(a[i]);  
27.         document.writeln(txt);  
28.     }  
29.     </script>   
30.     </body>  
31. </html>  

Output:

Printing Sorted Element List ...
7
9
10
12
23
23
34
44
78
101

---

PHP Program

1. <html>  
2. <head>  
3. <title>Bubble Sort</title>  
4. </head>  
5. <body>  
6. <?php  
7.     $a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);  
8.     for($i=0;$i<10;$i++)  
9.     {  
10.         for ($j=0;$j<10;$j++)  
11.         {  
12.             if($a[$i]<$a[$j])  
13.             {  
14.                  $temp = $a[$i];  
15.                 $a[$i]=$a[$j];  
16.                 $a[$j] = $temp;   
17.             }  
18.         }  
19.     }  
20.     echo "Printing Sorted Element List ...\n";  
21.     for($i=0;$i<10;$i++)  
22.     {  
23.         echo $a[$i];  
24.         echo "\n";  
25.     }  
26. ?>  
27. </body>  
28. </html>  

Output:

Printing Sorted Element List ...
7
9
10
12
23
23
34
44
78
101