In a data structure, the bubble sort algorithm is the most basic sorting approach. Bubble sort employs the swapping approach, in which we swap the elements of an array.
We have an array in this example, and we will sort it in ascending order.
Table of Contents
Steps for Bubble Sort Data Structure
- If the first element in an array is greater than the second element, the elements are swapped. That is, the second element is placed first, while the first element is placed second.
- In the following phase, the second position element is compared to the third position element. If the second position element is greater than the third position element, the value is swapped between the second and third positions.
- The interchanging/swapping operation is repeated until the highest element is found at the last or nth position.
If both elements are equal, the element's value is not swapped in adjacent positions.
The first pass has (n-1) pairs, the second pass has (n-2) pairs, and the last (or (n-1)th) pass has only one pair. As a result, a number of checks or comparisons are
(n-1) + (n+2) + (n+3) + ... + 1 = n(n-1)/2
Bubble sort has a complexity of O(n2) in both the average and worst cases, where n is the number of elements.
In term of performance bubble sort is only beneficial if there are only a few elements in the list/array to be sorted.
The program slows down when a lot of elements have to be sorted.
Where is bubble sort mainly used?
- If you want to write simple or sort code.
- If it doesn’t matter how complex it is.
Algorithm of Bubble Sort
START
Outer Loop: REPEAT FOR i=1 To N-1 STEP i=i+1
Inner Loop: REPEAT FOR j=1 To N–I STEP j=j+1
Condition: IF Array[j] > Array[j+1]
Swapping Data : Array[j] = Array[j+1]
[Inner Loop END ]
[Outer Loop END ]
End
If the number of data items is N, the outer loop is N times and the inner loop is N-i times comparison to find the smallest data based on the outer loop, as shown in the algorithm.
Bubble Sort step by step example
We’re going to use bubble sort to sort an array [51 11 41 21 81] from smallest to largest. Elements highlighted in bold are being compared in each step.
First Phase
(51 11 41 21 81) -> (11 51 41 21 81), Since 51 > 11, the algorithm compares the first two elements and swaps them.
(11 51 41 21 81) -> (11 41 51 21 81), Since 51 > 41, swap.
(11 41 51 21 81) -> (11 41 21 51 81), Since 51 > 21, Swap
(11 41 21 51 81) -> (11 41 21 51 81), The algorithm does not swap these elements because they are already in the correct order (81 > 51).
Second Phase
(11 41 21 51 81) -> (11 41 21 51 81)
(11 41 21 51 81) -> (11 21 41 51 81), Since 41 > 21, swap
(11 21 41 51 81) -> (11 21 41 51 81)
(11 21 41 51 81) -> (11 21 41 51 81)
The array is now sorted, but the algorithm is unsure if it is complete. For the algorithm to know it is sorted, an additional exhaustive pass without any swaps is required.
Third Phase
(11 21 41 51 81) -> (11 21 41 51 81)
(11 21 41 51 81) -> (11 21 41 51 81)
(11 21 41 51 81) -> (11 21 41 51 81)
(11 21 41 51 81) -> (11 21 41 51 81)
C program for bubble sort to sort the elements
The implementations of Bubble Sort are shown in the following programs.
#include <stdio.h>
#define MAX 5
void swapElement(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void sortBubble(int list[])
{
int i,j;
for(i=0;i<(MAX -1);i++)
{
for(j=0;j<(MAX-(i+1));j++)
{
if(list[j] > list[j+1])
{
swapElement(&list[j], &list[j+1]);
}
}
}
}
void printlist(int list[])
{
int i;
printf("The elements of the list are: \n");
for(i=0;i<MAX;i++)
{
printf("%d\t",list[i]);
}
}
void main()
{
int list[MAX] = {51, 11, 41, 21, 81}, n;
printf("The list before sorting is:\n");
printlist(list);
sortBubble(list);
printf("\nThe list after sorting is:\n");
printlist(list);
}
Output: The list before sorting is: The elements of the list are: 51 11 41 21 81 The list after sorting is: The elements of the list are: 11 21 41 51 81
Another bubble sort program
#include <stdio.h>
#define MAX 5
void binarySort(int list[])
{
int i,j, temp;
for(i=0; i<MAX; i++)
{
for(j=0; j<MAX-i; j++)
{
if(list[j]>list[j+1])
{
temp = list[j];
list[j] = list[j+1];
list[j+1] =temp;
}
}
}
}
void printlist(int list[])
{
int i;
printf("The elements of the list are: \n");
for(i=0;i<MAX;i++) {
printf("%d\t",list[i]);
}
}
void main()
{
int list[MAX] = {10, 30, 20, 50, 40}, n;
printf("\nThe list before sorting is:\n");
printlist(list);
binarySort(list);
printf("\nThe list after sorting is:\n");
printlist(list);
}
Output: The list before sorting is: The elements of the list are: 10 30 20 50 40 The list after sorting is: The elements of the list are: 10 20 30 40 50
From the bubble sort technique for ascending order, we can conclude that this algorithm looks for the smallest data item in the list and puts that data element at the first position. As a result, the iteration starts at the element and proceeds to the last position, where the elements are ordered appropriately. The largest element will be placed at the last position of the list.
