To Sort N Numbers Bubble Sort Continues Making Passes Through the Array Until
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.
How does Bubble Sort Work?
Input: arr[] = {5, 1, 4, 2, 8}
First Pass:
- Bubble sort starts with very first two elements, comparing them to check which one is greater.
- ( 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:
- Now, during second iteration it should look like this:
- ( 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 )
Third Pass:
- 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.
- ( 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 )
Illustration:
Follow the below steps to solve the problem:
- Run a nested for loop to traverse the input array using two variables i and j, such that 0 ≤ i < n-1 and 0 ≤ j < n-i-1
- If arr[j] is greater than arr[j+1] then swap these adjacent elements, else move on
- Print the sorted array
Below is the implementation of the above approach:
C
#include <stdio.h>
void swap( int * xp, int * yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort( int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}
void printArray( int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf ( "%d " , arr[i]);
printf ( "\n" );
}
int main()
{
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int n = sizeof (arr) / sizeof (arr[0]);
bubbleSort(arr, n);
printf ( "Sorted array: \n" );
printArray(arr, n);
return 0;
}
C++
#include <bits/stdc++.h>
using namespace std;
void bubbleSort( int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
void printArray( int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " " ;
cout << endl;
}
int main()
{
int arr[] = { 5, 1, 4, 2, 8};
int N = sizeof (arr) / sizeof (arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n" ;
printArray(arr, N);
return 0;
}
Java
class BubbleSort {
void bubbleSort( int arr[])
{
int n = arr.length;
for ( int i = 0 ; i < n - 1 ; i++)
for ( int j = 0 ; j < n - i - 1 ; j++)
if (arr[j] > arr[j + 1 ]) {
int temp = arr[j];
arr[j] = arr[j + 1 ];
arr[j + 1 ] = temp;
}
}
void printArray( int arr[])
{
int n = arr.length;
for ( int i = 0 ; i < n; ++i)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[])
{
BubbleSort ob = new BubbleSort();
int arr[] = { 64 , 34 , 25 , 12 , 22 , 11 , 90 };
ob.bubbleSort(arr);
System.out.println( "Sorted array" );
ob.printArray(arr);
}
}
Python3
def bubbleSort(arr):
n = len (arr)
for i in range (n):
for j in range ( 0 , n - i - 1 ):
if arr[j] > arr[j + 1 ]:
arr[j], arr[j + 1 ] = arr[j + 1 ], arr[j]
if __name__ = = "__main__" :
arr = [ 64 , 34 , 25 , 12 , 22 , 11 , 90 ]
bubbleSort(arr)
print ( "Sorted array is:" )
for i in range ( len (arr)):
print ( "%d" % arr[i], end = " " )
C#
using System;
class GFG {
static void bubbleSort( int [] arr)
{
int n = arr.Length;
for ( int i = 0; i < n - 1; i++)
for ( int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
static void printArray( int [] arr)
{
int n = arr.Length;
for ( int i = 0; i < n; ++i)
Console.Write(arr[i] + " " );
Console.WriteLine();
}
public static void Main()
{
int [] arr = { 64, 34, 25, 12, 22, 11, 90 };
bubbleSort(arr);
Console.WriteLine( "Sorted array" );
printArray(arr);
}
}
PHP
<?php
function bubbleSort(& $arr )
{
$n = sizeof( $arr );
for ( $i = 0; $i < $n ; $i ++)
{
for ( $j = 0; $j < $n - $i - 1; $j ++)
{
if ( $arr [ $j ] > $arr [ $j +1])
{
$t = $arr [ $j ];
$arr [ $j ] = $arr [ $j +1];
$arr [ $j +1] = $t ;
}
}
}
}
$arr = array (64, 34, 25, 12, 22, 11, 90);
$len = sizeof( $arr );
bubbleSort( $arr );
echo "Sorted array : \n" ;
for ( $i = 0; $i < $len ; $i ++)
echo $arr [ $i ]. " " ;
?>
Javascript
<script>
function swap(arr, xp, yp)
{
var temp = arr[xp];
arr[xp] = arr[yp];
arr[yp] = temp;
}
function bubbleSort( arr, n)
{
var i, j;
for (i = 0; i < n-1; i++)
{
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(arr,j,j+1);
}
}
}
}
function printArray(arr, size)
{
var i;
for (i=0; i < size; i++)
document.write(arr[i]+ " " );
document.write( "\n" );
}
var arr = [64, 34, 25, 12, 22, 11, 90];
var n = 7;
document.write( "UnSorted array: \n" );
printArray(arr, n);
bubbleSort(arr, n);
document.write( "Sorted array: \n" );
printArray(arr, n);
</script>
Output
Sorted array: 1 2 4 5 8
Time Complexity: O(N2)
Auxiliary Space: O(1)
Optimized Implementation of Bubble Sort:
The above function always runs O(N2) time even if the array is sorted. It can be optimized by stopping the algorithm if the inner loop didn't cause any swap.
Below is the implementation for the above approach:
C
#include <stdio.h>
#include <stdbool.h>
void swap( int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort( int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false ;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true ;
}
}
if (swapped == false )
break ;
}
}
void printArray( int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf ( "%d " , arr[i]);
printf ( "n" );
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof (arr)/ sizeof (arr[0]);
bubbleSort(arr, n);
printf ( "Sorted array: \n" );
printArray(arr, n);
return 0;
}
C++
#include <bits/stdc++.h>
using namespace std;
void bubbleSort( int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false ;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(arr[j], arr[j+1]);
swapped = true ;
}
}
if (swapped == false )
break ;
}
}
void printArray( int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << " " << arr[i];
}
int main()
{
int arr[] = {5, 3, 1, 9, 8, 2, 4, 7};
int N = sizeof (arr)/ sizeof (arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n" ;
printArray(arr, N);
return 0;
}
Java
import java.io.*;
class GFG
{
static void bubbleSort( int arr[], int n)
{
int i, j, temp;
boolean swapped;
for (i = 0 ; i < n - 1 ; i++)
{
swapped = false ;
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;
swapped = true ;
}
}
if (swapped == false )
break ;
}
}
static void printArray( int arr[], int size)
{
int i;
for (i = 0 ; i < size; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[])
{
int arr[] = { 64 , 34 , 25 , 12 , 22 , 11 , 90 };
int n = arr.length;
bubbleSort(arr, n);
System.out.println( "Sorted array: " );
printArray(arr, n);
}
}
Python3
def bubbleSort(arr):
n = len (arr)
for i in range (n):
swapped = False
for j in range ( 0 , n - i - 1 ):
if arr[j] > arr[j + 1 ] :
arr[j], arr[j + 1 ] = arr[j + 1 ], arr[j]
swapped = True
if swapped = = False :
break
arr = [ 64 , 34 , 25 , 12 , 22 , 11 , 90 ]
bubbleSort(arr)
print ( "Sorted array :" )
for i in range ( len (arr)):
print ( "%d" % arr[i],end = " " )
C#
using System;
class GFG
{
static void bubbleSort( int []arr, int n)
{
int i, j, temp;
bool swapped;
for (i = 0; i < n - 1; i++)
{
swapped = false ;
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;
swapped = true ;
}
}
if (swapped == false )
break ;
}
}
static void printArray( int []arr, int size)
{
int i;
for (i = 0; i < size; i++)
Console.Write(arr[i] + " " );
Console.WriteLine();
}
public static void Main()
{
int []arr = {64, 34, 25, 12, 22, 11, 90};
int n = arr.Length;
bubbleSort(arr,n);
Console.WriteLine( "Sorted array" );
printArray(arr,n);
}
}
PHP
<?php
function bubbleSort(& $arr )
{
$n = sizeof( $arr );
for ( $i = 0; $i < $n ; $i ++)
{
$swapped = False;
for ( $j = 0; $j < $n - $i - 1; $j ++)
{
if ( $arr [ $j ] > $arr [ $j +1])
{
$t = $arr [ $j ];
$arr [ $j ] = $arr [ $j +1];
$arr [ $j +1] = $t ;
$swapped = True;
}
}
if ( $swapped == False)
break ;
}
}
$arr = array (64, 34, 25, 12, 22, 11, 90);
$len = sizeof( $arr );
bubbleSort( $arr );
echo "Sorted array : \n" ;
for ( $i = 0; $i < $len ; $i ++)
echo $arr [ $i ]. " " ;
?>
Javascript
<script>
function bubbleSort(arr, n)
{
var i, j, temp;
var swapped;
for (i = 0; i < n - 1; i++)
{
swapped = false ;
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;
swapped = true ;
}
}
if (swapped == false )
break ;
}
}
function printArray(arr, size)
{
var i;
for (i = 0; i < size; i++)
document.write(arr[i] + " " );
document.writeln();
}
var arr = [ 64, 34, 25, 12, 22, 11, 90 ];
var n = arr.length;
bubbleSort(arr, n);
document.write( "Sorted array: " );
printArray(arr, n);
</script>
Output
Sorted array: 1 2 3 4 5 7 8 9
Time Complexity: O(N2)
Auxiliary Space: O(1)
Worst Case Analysis for Bubble Sort:
The worst-case condition for bubble sort occurs when elements of the array are arranged in decreasing order.
In the worst case, the total number of iterations or passes required to sort a given array is (n-1). where 'n' is a number of elements present in the array.
At pass 1 : Number of comparisons = (n-1)
Number of swaps = (n-1)At pass 2 : Number of comparisons = (n-2)
Number of swaps = (n-2)At pass 3 : Number of comparisons = (n-3)
Number of swaps = (n-3)
.
.
.
At pass n-1 : Number of comparisons = 1
Number of swaps = 1Now , calculating total number of comparison required to sort the array
= (n-1) + (n-2) + (n-3) + . . . 2 + 1
= (n-1)*(n-1+1)/2{ by using sum of N natural Number formula }
= n (n-1)/2
For the Worst case:
Total number of swaps = Total number of comparison
Total number of comparison (Worst case) = n(n-1)/2
Total number of swaps (Worst case) = n(n-1)/2
Worst and Average Case Time Complexity: O(N2). The worst case occurs when an array is reverse sorted.
Best Case Time Complexity: O(N). The best case occurs when an array is already sorted.
Auxiliary Space: O(1)
Recursive Implementation Of Bubble Sort:
The idea is to place the largest element in its position and keep doing the same for every other element.
Follow the below steps to solve the problem:
- Place the largest element at its position, this operation makes sure that the first largest element will be placed at the end of the array.
- Recursively call for rest n – 1 elements with the same operation and place the next greater element at their position.
- The base condition for this recursion call would be, when the number of elements in the array becomes 0 or 1 then, simply return (as they are already sorted).
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
void bubblesort( int arr[], int n)
{
if (n == 0 || n == 1)
{
return ;
}
for ( int i = 0; i < n - 1; i++)
{
if (arr[i] > arr[i + 1])
{
swap(arr[i], arr[i + 1]);
}
}
bubblesort(arr, n - 1);
}
int main()
{
int arr[5] = {2, 5, 1, 6, 9};
bubblesort(arr, 5);
for ( int i = 0; i < 5; i++)
{
cout << arr[i] << " " ;
}
return 0;
}
What is the Boundary Case for Bubble sort?
Bubble sort takes minimum time (Order of n) when elements are already sorted. Hence it is best to check if the array is already sorted or not beforehand, to avoid O(N2) time complexity.
Does sorting happen in place in Bubble sort?
Yes, Bubble sort performs swapping of adjacent pairs without the use of any major data structure. Hence Bubble sort algorithm is an in-place algorithm.
Is the Bubble sort algorithm stable?
Yes, the bubble sort algorithm is stable.
Where is the Bubble sort algorithm used?
Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm.
In computer graphics, it is popular for its capability to detect a tiny error (like a swap of just two elements) in almost-sorted arrays and fix it with just linear
complexity (2n).
Example: It is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to the x-axis), and with incrementing y their order changes (two elements are swapped) only at intersections of two lines (Source: Wikipedia)
Snapshots:Quiz on Bubble Sort
Other Sorting Algorithms on GeeksforGeeks/GeeksQuiz:
Recursive Bubble Sort
Coding practice for sorting.
Source: https://www.geeksforgeeks.org/bubble-sort/
0 Response to "To Sort N Numbers Bubble Sort Continues Making Passes Through the Array Until"
Post a Comment