Bubble Sort

Sorting Algorithm

Share

About Bucket Sort

In this technique we sort the given elements in ascending or descending order by comparing two adjacent elements at a time and placing them in correct position.

  • Bubble sort requires n – 1 pass to sort an array a having n elements.
  • In each pass every adjacent elements a[i] and a[i+1] is compared and if they are not in order then they are swapped.
  • In each pass we have n – k comparisons, where n is the number of elements and k is the pass number.
    So, 1st pass requires n – 1 comparisons,
    kth pass requires n – k comparisons and
    the last pass requires 1 comparison.

Algorithm


/*
a[0:n-1] is an array of n elements.
temp is a variable to facilitate exchange.
*/
BubbleSort(a,n)
Begin
    for k = 1 to n-1 by 1 do	//this is for pass
        for j = 0 to n – k – 1 by 1 do	//this is for comparison
            if a[j] > a[j+1] then	
                Set temp = a[j];
                Set a[j] = a[j+1];
                Set a[j+1] = temp;
            endif
        endfor
    endfor
End

Code in C


#include <stdio.h>

//function declaration
void bubbleSort(int *a, int n);

int main(){
	//variable declaration
	int arr[5], i;
	
	//input
	for(i = 0; i < 5; i++)
		scanf("%d", &arr[i]);
	
	//sort
	bubbleSort(arr,5);	//sending arr address and no. of elements
	
	//output
	for(i = 0; i < 5; i++)
		printf("%d\n", arr[i]);
		
	return 0;
}

//function definition
void bubbleSort(int *a, int n){
	int k, j, temp;
	for(k = 1; k <= n-1; k++){
		for(j = 0; j <= n-k-1; j++){
			if(a[j] > a[j+1]){
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}
}

Time Complexity

Worst-case and average complexity of Bubble sort is O(n2), where n is the number of items being sorted. When n is very large then Bubble sort is not a suitable choice to sort the elements.