# Bubble Sort

## Bubble Sort

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

This is a very slow sorting algorithm compared to algorithms like quicksort, with worst-case complexity O(n^2). However, the tradeoff is that bubble sort is one of the easiest sorting algorithms to implement from scratch. As a result, bubble sort algorithm is commonly taught as the first sorting algorthim in Algorithm and Data structure classes. From technical perspective, bubble sort is reasonable for sorting small-sized arrays or specially when executing sort algorithms on computers with remarkably limited memory resources.

### 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 )

#### Properties

• Space complexity: O(1)
• Best case performance: O(n*n)
• Average case performance: O(n*n)
• Worst case performance: O(n*n)
• Stable: Yes

### Video Explanation

Bubble sort in easy way

### Example in Java.

``````public int[] bubSort(int []ar)
{
int i, j, temp;
for (i = 0; i < n; i++)
{
for (j = 0; j < n - 1 - i; j++)
{
if (ar[j] > ar[j+1])
{
temp = ar[j];
ar[j] = ar[j + 1];
ar[j + 1] = temp;
}
}
}
return ar[];
}``````

### Example in C++

``````#include <iostream>
using namespace std;
int BubbleSort[] (int arr[], int n)
{
int i, j, temp;
for (i = 0; i < n; ++i)
{
for (j = 0; j < n-i-1; ++j)
{
if (arr[j] > arr[j+1])
{
temp = arr[j]
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}    ``````

### Example in Swift

``````func bubbleSort(_ inputArray: [Int]) -> [Int] {
guard inputArray.count > 1 else { return inputArray } // make sure our input array has more than 1 element
var numbers = inputArray // function arguments are constant by default in Swift, so we make a copy
for i in 0..<(numbers.count - 1) {
for j in 0..<(numbers.count - i - 1) {
if numbers[j] > numbers[j + 1] {
numbers.swapAt(j, j + 1)
}
}
}
return numbers // return the sorted array
} ``````

### Example in Python

``````def bubblesort( A ):
for i in range( len( A ) ):
for k in range( len( A ) - 1, i, -1 ):
if ( A[k] < A[k - 1] ):
swap( A, k, k - 1 )

def swap( A, x, y ):
tmp = A[x]
A[x] = A[y]
A[y] = tmp``````

### Modified Bubble Sort

We now know that Bubble Sort has a general complexity of O(n^2) for all input cases. Since this is a very slow sort, one of the commonly-suggested and fairly easy optimizations can be made to include the best case (where the list/array provided as input is already sorted). If we are able to check this condition (by making N comparisons), we should be able to terminate execution immediately after validating the fact that the array is sorted.

This means that in the best case, our modified Bubble Sort Algorithm would have a complexity of O(n). This doesn’t change the average or worst case, of course, but may show a decent uptick in speed if you intend to sort a number of instances, some of which are likely to be sorted already.

### Example in JavaScript

``````let arr = [1, 4, 7, 45, 7,43, 44, 25, 6, 4, 6, 9],
sorted = false;

while(!sorted) {
sorted = true;
for(var i=0; i < arr.length; i++) {
if(arr[i] < arr[i-1]) {
let temp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = temp;
sorted = false;
}
}
}``````

### Example in Java.

``````public int[] bubSortModified(int []ar)
{
int i, j, temp;
boolean sorted;
for (i = 0; i < n; i++)
{
sorted = true;
for (j = 0; j < n - 1 - i; j++)
{
if (ar[j] > ar[j+1])
{
sorted = false; //implying array was not sorted already, swaps are needed
temp = ar[j];
ar[j] = ar[j + 1];
ar[j + 1] = temp;
}
}
if (sorted == true)
break;  //if array is sorted, stop iterating
}
return ar[];
}``````

### Example in C++

``````// Recursive Implementation
void bubblesort(int arr[], int n)
{
if(n==1)    //Initial Case
return;
bool swap_flag = false;
for(int i=0;i<n-1;i++)  //After this pass the largest element will move to its desired location.
{
if(arr[i]>arr[i+1])
{
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
swap_flag = true;
}
}
// IF no two elements were swapped in the loop, then return, as array is sorted
if(swap_flag == false)
return;
bubblesort(arr,n-1);    //Recursion for remaining array
}``````

### Example in Ruby

``````def bubble_sort(arr)
sorted = false
until sorted
sorted = true
(arr.count-1).times do|i|
if arr[i] > arr[i + 1]
arr[i], arr[i +1] = arr[i +1], arr[i]
sorted = false
end
end
end
arr end``````

### Example in PHP

``````function bubble_sort(\$arr) {
\$size = count(\$arr)-1;
for (\$i=0; \$i<\$size; \$i++) {
for (\$j=0; \$j<\$size-\$i; \$j++) {
\$k = \$j+1;
if (\$arr[\$k] < \$arr[\$j]) {
// Swap elements at indices: \$j, \$k
list(\$arr[\$j], \$arr[\$k]) = array(\$arr[\$k], \$arr[\$j]);
}
}
}
return \$arr;// return the sorted array
}

\$arr = array(1,3,2,8,5,7,4,0);
print("Before sorting");
print_r(\$arr);

\$arr = bubble_sort(\$arr);
print("After sorting by using bubble sort");
print_r(\$arr);``````

### Example in C

``````#include <stdio.h>

int BubbleSort(int array[], int n);

int main(void) {
int arr[] = {10, 2, 3, 1, 4, 5, 8, 9, 7, 6};
BubbleSort(arr, 10);

for (int i = 0; i < 10; i++) {
printf("%d", arr[i]);
}
return 0;
}
int BubbleSort(int array[], n)
{
for (int i = 0 ; i < n - 1; i++)
{
for (int j = 0 ; j < n - i - 1; j++)     //n is length of array
{
if (array[j] > array[j+1])      // For decreasing order use
{
int swap   = array[j];
array[j]   = array[j+1];
array[j+1] = swap;
}
}
}
}``````