Definition:
Bubble sort is a sorting algorithm. It will sort by checking if the next element is greater the present element, if greater then it will swap the elements.
Steps to perform for bubble sort:
1. In bubble sort we use 2 for loops. Outer loop and one inner loop.
2. Here each element will be compared with its adjacent element, if the current element is greater than the next element, we swap them.
3. At the end of the first iteration, the largest element will be at the end, similarly at the end of 2nd iteration 2nd highest element will be in n-1 position.
4. As we see that after every iteration highest element will be on the top, hence we call it as bubble sort.
Example:
Consider the array: [ 3, 4, 1, 2, 8, 5 ].
We perform bubble sort as shown below:
First Pass:
Hence after first pass, the largest element will be at the end. And we can ignore comparing the last element as it is the largest, in the next pass.
Second Pass:
In the second pass, 2nd largest element will be at n-1 place.
Third Pass:
In third pass the result will be the same as all the elements have been sorted.
In bubble sort, we use 2 loops. Outer loop is to loop n times and inner loop for swapping.
As you can see above, after 2nd pass all the elements are in the sorted order. Hence we can break the loop if no swapping done by the inner loop after third pass, hence saving the time. This is an improved version of bubble sort.
C program to implement bubble sort:
#include<stdio.h> void print_array(int array[], int length) { int index = 0; printf("The sorted array is \n"); for(index = 0 ; index < length ; index++) { printf("%d\n",array[index] ); } } void swap (int *num_1, int *num_2) { int temp = *num_1; *num_1 = *num_2; *num_2 = temp; } void bubble_sort (int array[], int length) { int outer_loop = 0; int inner_loop = 0; for(outer_loop = 0; outer_loop < length - 1; outer_loop ++) { for(inner_loop = 0; inner_loop < length - outer_loop - 1 ; inner_loop ++) { if(array [inner_loop] > array[inner_loop+1]) { swap(&array[inner_loop], &array [inner_loop+1]); } } } } int main() { int length = 0; int array[100]; int index = 0; printf("Enter the length of the array\n"); scanf("%d", &length); printf("Enter the array elements of length %d\n", length); for (index = 0; index < length; ++index) { scanf("%d", &array[index]); } bubble_sort(array, length); print_array(array, length); }
Output:
Enter the length of the array 5 Enter the array elements of length 5 5 4 3 2 1 The sorted array is 1 2 3 4 5
Running time at worst case for bubble sort:
From the above code, we can see that it always compares between 2 elements.
In the first pass, it will do n-1 comparisons
In the second pass, it will do n-2 comparisons
Similarly, we shall continue to compare elements, till it will become 1.
Hence the above sum can be written as:
(n-1) + (n-2) + (n-3) . . . + 1
It can be reduced to (n * (n -1))/2
0.5 n^2 + 0.5 n
n^2
Hence the worst case will be O(n^2)
AJ’s definitive guide for DS and Algorithms. Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.
Deepak Rajpurohit
python code for bubble sort -:
def bubble(arr):
n = len(arr)
for i in range(0,n-1):
for j in range(0, n-i-1):
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
arr = [4,3,6,2,8,0,1]
bubble(arr)
#print sorted array
for i in range(len(arr)):
print(arr[i])
Deepak Rajpurohit
i wrote this code with indentation but in comment indentation is not disappear so please run this code with indentation.
Himanshu J Prasad
*Bubble Sort – Python*
n = [3,4,5,2,8,1]
for i in range(0,len(n)):
for j in range(i+1,len(n)):
if(n[i]>n[j]):
temp = n[i]
n[i] = n[j]
n[j] = temp
print(n)