Bubble Sort
Bubble sort is the simplest sorting algorithm and it 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 the code
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
PrintList(MyList)
bubblesort(MyList)
print("Sorted List")
PrintList(MyList)
The above code will give the following 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 the 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);
}
}
The above code will give the following 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 the 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;
}
The above code will give the following 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 the 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;
}
The above code will give the following output:
Original Array 1 10 23 50 4 9 -4 Sorted Array -4 1 4 9 10 23 50
using System;
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 the 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);
}
}
The above code will give the following output:
Original Array 1 10 23 50 4 9 -4 Sorted Array -4 1 4 9 10 23 50
<?php
// function for bubble sort
function bubblesort(&$Array, $n) {
$temp;
for($i=0; $i<$n; $i++) {
for($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
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
// test the code
$MyArray = array(1, 10, 23, 50, 4, 9, -4);
$n = sizeof($MyArray);
echo "Original Array\n";
PrintArray($MyArray, $n);
bubblesort($MyArray, $n);
echo "\nSorted Array\n";
PrintArray($MyArray, $n);
?>
The above code will give the following 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 Θ(N²) 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.
