C and Data Structures and Algorithms

Bubble Sort in C - [Program & Algorithm] Step-by-Step Explanation

Posted in C, Data Structures and Algorithms
Bubble Sort in C - [Program & Algorithm] Step-by-Step Explanation

Sorting of data is one of the most fundamental, yet important problem in computer science. Sorting forms a great case study for those who want to learn Data Structures and Algorithms.

What is Sorting - Definition

Often in real life, we are supposed to arrange data in a particular order. For instance, during our school days, we are told to stand in the queue based on our heights. Another example is the attendance register at school/college which contains our names arranged in alphabetical order.

These data arrangements give easier access to data for future use for ex. finding "Joe" in an attendance register of 100 students. The arrangement of data in a particular order is called as sorting of the data by that order. 2 of the most commonly used orders are:

  • Ascending order: while sorting the data in ascending order, we try to arrange the data in a way such that each element is in some way “smaller than” its successor. This “smaller than” relation is an ordered relation over the set from which the data is taken. As a simple example, the numbers 1, 2, 3, 4, 5 are sorted in ascending order. Here, the “smaller than” relation is actually the “<” operator. As can be seen, 1 < 2 < 3 < 4 < 5.
  • Descending order: descending order is the exact opposite of ascending order. Given a data that is sorted in ascending order, reverse it and you will get the data in descending order.

Due to the similar nature of the 2 orders, we often drop the actual order and we say - we want to sort the data. This generally means that we want the data to be sorted in ascending order. Before we get into the details of the sorting algorithm, let us understand the problem statement.

Problem statement

We are given an array (or a list) of data. We are also given a way to “order” the elements present in the data. Now, we are asked to arranged the data as per the given order. As an example, we are given an array of integers: [5, 1, 4, 2, 3]. We are given the “order” as “smaller than”. So, we are asked to arrange the elements of this array in such a way that each element is smaller than its successor. Basically, we need to find a way to sort this array so that the final array obtained is [1, 2, 3, 4, 5]. There are several techniques/algorithms to achieve this ordered output array. One such well-known technique that we will discuss in this blog is called Bubble Sort.

Bubble Sort Algorithm in C - Introduction

Bubble Sort in C is a sorting algorithm where we repeatedly iterate through the array and swap adjacent elements that are unordered. We repeat this until the array is sorted.

As an example, for the array mentioned above - [5, 1, 4, 2, 3] we can see that 5 should not be on the left of 1 and so, we swap them to get: [1, 5, 4, 2, 3]. Next, we see that 5 should again not be on the left of 4. We swap 5 and 4 to get [1, 4, 5, 2, 3]. We repeat this for 5 and 2 and subsequently for 5 and 3 to get [1, 4, 2, 3, 5].

As can be seen - after one “pass” over the array, the largest element (5 in this case) has reached its correct position - extreme right. Let us try to repeat this process.

(1, 4) is correct. However, (4, 2) is an incorrect order. Therefore, we swap 4 and 2 to get [1, 2, 4, 3, 5]. Now again, (4, 3) is incorrect so we do another swap and get [1, 2, 3, 4, 5].

As can be seen, the array is sorted!

This exactly is how bubble sort in C works.

As an example, check this graphic that pictorially depicts how bubble sort works.How-bubble-sort-works-gif

Bubble Sort - Explanation

In the first “pass” through the array, the largest element will always get swapped until it is placed to the extreme right. This is because this largest element will always break the desired order. So, at the end of the first pass, the largest element will always reach its correct position.

Now that the largest element has reached its correct position (for instance, 5 reached the last position), we can simply ignore it and concentrate on the rest of the array ([1, 4, 2, 3] in the above case). Here, the largest element in the rest of the array (which is 4) will be nothing but the second largest element in the array. By the above recursive argument, this second largest array will then reach the last position in the remaining array ([1, 2, 3, 4]). This is nothing but a recursive argument on the remaining array.

This continues until for n iterations where n = number of elements in the array. Finally, the array gets sorted.

#include <stdio.h>
void bubble_sort(int a[], int n) {
   int i = 0, j = 0, tmp;
   for (i = 0; i < n; i++) {   // loop n times - 1 per element
       for (j = 0; j < n - i - 1; j++) { // last i elements are sorted already
           if (a[j] > a[j + 1]) {  // swop if order is broken
               tmp = a[j];
               a[j] = a[j + 1];
               a[j + 1] = tmp;
           }
       }
   }
}
int main() {
 int a[100], n, i, d, swap;
 printf("Enter number of elements in the array:\n");
  scanf("%d", &n);
 printf("Enter %d integers\n", n);
 for (i = 0; i < n; i++)
   scanf("%d", &a[i]);
 bubble_sort(a, n);
 printf("Printing the sorted array:\n");
 for (i = 0; i < n; i++)
    printf("%d\n", a[i]);
 return 0;
}

Bubble Sort Program in C

We loop n times - once for each element of the array. When i = 0, with the j loop, the largest element of the array reaches its correct position. When i = 1, with the j loop, the second largest element of the array reaches its correct position. So on and so forth.

Conclusion

Bubble sort is a fairly simple algorithm. It forms an interesting example of how simple computations can be used to perform more complex tasks. However, there is one issue with the algorithm - it is relatively slower compared to other sorting algorithms. To understand that, let us take a look at the loops involved - there are 2 loops:

  • First, the outer loop of variable i that goes from i = 0 to i = n - 1.
  • For each iteration of the outer i loop, the inner loop of variable j goes from j = 0 to j = n - i - 2.

We can consolidate the number of iterations to see that:

  • When i = 0, the inner j loop goes from j = 0 to j = n - 2
  • When i = 1, the inner j loop goes from j = 0 to j = n - 3
  • When i = 2, the inner j loop goes from j = 0 to j = n - 4
  • When i = n - 2, the inner j loop goes from j = 0 to j = 0

We can sum this up to see that the total iterations are (n - 2) + (n - 3) + (n - 4) … + 1 + 0 = (n - 2) * (n - 3) / 2 = (n2 - 5n + 6) / 2 = n2/2 - 2.5n + 3As can be seen, this term is proportional to n2 (the largest power of n is n2). Mathematically, this is stated as - bubble sort algorithm is of O(n2) complexity. This isn’t the best because when n is large (say n = 106), n2 is huge (n2 = 1012). Therefore, it will take a lot of iterations for the algorithm to complete. This is undesirable. There are some better algorithms like merge sort in C, etc that take O(nlog2n) iterations. logn is much smaller than n. As an example, when n = 230 (which is approximately 109), log2n is just 30). Nevertheless, bubble sort is an interesting algorithm and is a great way for beginners to understand how sorting works.

People are also reading:

Aman Goel

Aman Goel

Entrepreneur, Coder, Speed-cuber, Blogger, fan of Air crash investigation! Aman Goel is a Computer Science Graduate from IIT Bombay. Fascinated by the world of technology he went on to build his own start-up - AllinCall Research and Solutions to build the next generation of Artificial Intelligence, Machine Learning and Natural Language Processing based solutions to power businesses. View all posts by the Author

Leave a comment

Your email will not be published
Cancel
Rona
Rona

How to find the difference between the sum of maximum and minimum sum of N-M elements of the given array?

Lalit pawar
Lalit pawar

Write a program c to short an array using bubble sort technique plase give the algorithm.

Vijay Singh
Vijay Singh 312 Points

begin BubbleSort(list)

for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for

return list

end BubbleSort

Sudarshan
Sudarshan

Thanks

Amado Orta
Amado Orta

What is the loop invariant of bubble sort?

Heather Williams
Heather Williams

Loop invariant condition for bubble sort is that when i number of iterations right most i elements are sorted and in place.
for (i = 0 to n-1)
for (j = 0 to j arr[j+1])
swap(&arr[j], &arr[j+1]);

John Smith
John Smith

What is the algorithm for sorting an array using bubble support in C++?

Ken Wanless
Ken Wanless

Algorithm in C++
1) Start loop till N no. of elements.
2) Start 2nd loop till N-1 because every time highest element reaches at the last position.
3) Compare next two numbers, if they are in wrong order, swap them.
4) Else compare next two elements and repeat the 2nd loop ends and decrement 1st loop.
5) Do this till 1st loop ends.

Evangelina Slocum
Evangelina Slocum

How do I merge or combine a bubble sort and a insertion sort under a single c program?

Scarlet Wing
Scarlet Wing

What is a C program to sort elements in ascending order using bubble sort (Turbo C software)?

James Swift
James Swift

void bubble_sort( void* array, const int numberOfItems )
{
int firstItem = 0;
int lastItem = numberOfItems - 1;
for( int pass = 0; pass < numberOfItems; ++pass )
{
for( int i = firstItem; i 0 )
swap( array, i, i+1 );
}
--lastItem;
}
}

Haywood Schwarz
Haywood Schwarz

How do I make a bubble sorted 2-D string array in C?

Rhiannon Oldfield
Rhiannon Oldfield

This is the way to sort a 2-D string array in C:
void bubbleSort(char a[][100], int size){
char temp[100];
int i,j;
for(i=0; i

RAHMAN
RAHMAN

What is j 0?

Ryan Henning
Ryan Henning

How can the efficiency of bubble sort algorithm be determined?

Tim Liu
Tim Liu

The number of exchange and the number of comparison between the elements determine the efficiency of the algorithm. Complexity of bubble sort in average and worst case are same that is O(n^2), where n is the number of elements.
The no. of comparisons in bubble sort are = n*(n-1)/2

Doretha Fortin
Doretha Fortin

Is O N better than O Nlogn?

Roy Herring
Roy Herring

It depends on the input size. If the input is small data set then this doesn’t make a huge difference. But if the size of the input is large, then it would make a difference. O(n) actually be slower than n(log n) (not necessarily), when you are looking over the time complexity.