Bubble Sort Algorithm
Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with
n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.
Bubble sort is also known as sinking sort. This algorithm compares each pair of adjacent items and swaps them if
they are in the wrong order, and this same process goes on until no swaps are needed.
If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of
the array with the second element, if the first element is greater than the second element, it will swap both the
elements, and then move on to compare the second and the third element, and so on.
If we have total n elements, then we need to repeat this process for n-1 times.
It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles
up towards the last place or the highest index, just like a water bubble rises up to the water surface.
Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element
and swapping them if required.
Advantages:
• Easy to understand.
• Easy to implement.
• In-place, no external memory is needed.
• Performs greatly when the array is almost sorted.
Disadvantages
• Very expensive, O(n2) in worst case and average case.
• It does more element assignments than its counterpart, insertion sort.
Implementing Bubble Sort Algorithm
Following are the steps involved in bubble sort(for sorting a given array in ascending order):
1. Starting with the first element (index = 0), compare the current element with the next element of the array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next element, move to the next element. Repeat Step 1.
Let's consider an array with values {5, 1, 6, 2, 4, 3}
Below, we have a pictorial representation of how bubble sort will sort the given array.
So as we can see in the representation above, after the first iteration, 6 is placed at the last index, which is the
correct position for it.
Similarly after the second iteration, 5 will be at the second last index, and so on.
How Bubble Sort Works?
1. Starting from the first index, compare the first and the second elements. If the first element is greater than
the second element, they are swapped.
Now, compare the second and the third elements. Swap them if they are not in order.
The above process goes on until the last element.
2. The same process goes on for the remaining iterations. After each iteration, the largest element among the
unsorted elements is placed at the end.
In each iteration, the comparison takes place up to the last unsorted element.
The array is sorted when all the unsorted elements are placed at their correct positions.
Bubble sort program:
/* Bubble sort code */
#include <stdio.h>
int main()
{
int array[100], n, c, d, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
{
scanf("%d", &array[c]);
}
for (c = 0 ; c < n - 1; c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1]) /* For decreasing order use < */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}