# Bubble Sort

Bubble sort is the simplest sorting algorithm. The Bubble sort is based on the idea that every adjacent elements are compared and swapped if found in wrong order.

### Example:

To understand the bubble sort, lets consider an unsorted array $[1, 23, 10, -2]$ and discuss each step taken to sort the array in ascending order. In every pass, two adjacent elements are checked and swapped if found in wrong order.

First Pass: $(1)$ and $(23)$ are compared and found in correct order(ascending order in this case). After that $(23)$ and $(10)$ are compared, since $(23>10)$, hence these numbers are swapped. Then $(23)$ and $(-2)$ are compared and swapped.

Second Pass: $(1)$ and $(10)$ are compared and found in correct order. Then $(10)$ and $(-2)$ are compared, since $(10>-2)$, hence these numbers are swapped. After that $(10)$ and $(23)$ are compared and found in correct order.

Third Pass: $(1)$ and $(-2)$ are compared, since $(1>-2)$, hence these numbers are swapped. After that $(1,10)$ and $(10,23)$ are checked and found in correct order.

## Implementation of Bubble Sort

# function for bubble sort
def bubblesort(MyList):
for i in range(len(MyList)):
for j in range(len(MyList)-i-1):
if(MyList[j]>MyList[j+1]):
MyList[j] , MyList[j+1] = MyList[j+1], MyList[j]

# function to print list
def PrintList(MyList):
for i in MyList:
print(i, end=" ")
print("\n")

# test bubble sort code
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
PrintList(MyList)

bubblesort(MyList)
print("Sorted List")
PrintList(MyList)


Output

Original List
1 10 23 50 4 9 -4

Sorted List
-4 1 4 9 10 23 50


public class MyClass {
// function for bubble sort
static void bubblesort(int Array[]) {
int n = Array.length;
int temp;
for(int i=0; i<n; i++)
{
for(int j=0; j<n-i-1; j++)
{
if(Array[j]>Array[j+1])
{
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
}
}
}
}

// function to print array
static void PrintArray(int Array[])
{
int n = Array.length;
for (int i=0; i<n; i++)
{
System.out.print(Array[i] + " ");
}
System.out.println();
}

//test bubble sort code
public static void main(String[] args) {
int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
System.out.println("Original Array");
PrintArray(MyArray);

bubblesort(MyArray);
System.out.println("\nSorted Array");
PrintArray(MyArray);
}
}


Output

Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50


#include <iostream>
using namespace std;

// function for bubble sort
static void bubblesort(int Array[], int n)
{
int temp;
for(int i=0; i<n; i++)
{
for(int j=0; j<n-i-1; j++)
{
if(Array[j]>Array[j+1])
{
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
}
}
}
}

// function to print array
static void PrintArray(int Array[], int n)
{
for (int i=0; i<n; i++)
{
cout<<Array[i]<<" ";
}
cout<<"\n";
}

// test bubble sort code
int main (){
int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
int n = sizeof(MyArray) / sizeof(MyArray[0]);
cout<<"Original Array\n";
PrintArray(MyArray, n);

bubblesort(MyArray, n);
cout<<"\nSorted Array\n";
PrintArray(MyArray, n);
return 0;
}


Output

Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50


#include <stdio.h>

// function for bubble sort
static void bubblesort(int Array[], int n)
{
int temp;
for(int i=0; i<n; i++)
{
for(int j=0; j<n-i-1; j++)
{
if(Array[j]>Array[j+1])
{
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
}
}
}
}

// function to print array
static void PrintArray(int Array[], int n)
{
for (int i=0; i<n; i++)
{
printf("%i ",Array[i]);
}
printf("\n");
}

// test bubble sort code
int main (){
int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
int n = sizeof(MyArray) / sizeof(MyArray[0]);
printf("Original Array\n");
PrintArray(MyArray, n);

bubblesort(MyArray, n);
printf("\nSorted Array\n");
PrintArray(MyArray, n);
return 0;
}


Output

Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50


using System;

namespace MyApplication {
class MyProgram {
// function for bubble sort
static void bubblesort(int[] Array)
{
int n = Array.Length;
int temp;
for(int i=0; i<n; i++)
{
for(int j=0; j<n-i-1; j++)
{
if(Array[j]>Array[j+1])
{
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
}
}
}
}

// function to print array
static void PrintArray(int[] Array)
{
int n = Array.Length;
for (int i=0; i<n; i++)
{
Console.Write(Array[i] + " ");
}
Console.Write("\n");
}

// test bubble sort code
static void Main(string[] args) {
int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
Console.Write("Original Array\n");
PrintArray(MyArray);

bubblesort(MyArray);
Console.Write("\nSorted Array\n");
PrintArray(MyArray);
}
}
}


Output

Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50


### Time Complexity:

The time complexity of bubble sort is $\mathcal{O}(N^2)$ in all cases even if the whole array is sorted because the entire array need to be iterated for every element and it contains two nested loops.