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

Bubble Sort in C

Hackr.io.

Sorting of data is one of the most fundamental, yet an 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 of the attendance register at school/college which contains our names arranged in the 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 as 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.

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 + 3

As 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.

Related Posts

33 Comments, RSS

  1. Chang Caruso November 21, 2018 @ 1:21 pm

    What is the big O of bubble sort?

    • Olive Mann November 22, 2018 @ 2:05 am

      Big O is the mathematical representation to show the efficiency of an algorithm. Big O notation specifies that how much space is required by an algorithm for program’s input. Big O notation is also known as Bachmann-Landau notation. For Bubble sort algorithm, Big O is n^2 which is written as O(n^2) in worst and average case. This means in bubble sort, both inner and outer loop iterated n times.

  2. Zenia Lindstrom November 21, 2018 @ 1:21 pm

    Is selection sort same as bubble sort?

    • Mohammed Islam November 22, 2018 @ 2:07 am

      No, only average-case complexity of both algorithms are same i.e. O(n^2) but both are the different approaches of sorting. Selection sort is faster than bubble sort.
      In the Selection sort, it starts with finding the minimum element from the list and swapping it with the first element. Then same process repeats on the remaining list from the second element until the complete list is sorted.
      While in the Bubble sort, the adjacent elements are compared and swapped if they are in the wrong order. This will repeat until we get the sorted array.

  3. Nicky Starr November 21, 2018 @ 1:22 pm

    Deep Comparison between Selection Sort and Bubble Sort

    • Matthew Pepper November 22, 2018 @ 2:08 am

      Comparison chart of Selection sort and Bubble sort respectively.
      Definition- Selection sort is to select minimum element and swapped with the first element. While Bubble sort is to compare adjacent elements and swapped if they are in wrong order.
      Method- Selection sort prefers selection method. Bubble sort follows exchanging method.
      Efficiency- Selection sort is more efficient than Bubble sort.
      Speed- Selection sort is faster than bubble sort.
      Time complexity- O(n^2) for both in average case.
      Stability- Bubble sort is stable while selection sort is not stable.

  4. Vivien Aaron November 21, 2018 @ 1:24 pm

    Why is bubble sort stable?

    • Victoria Hogan November 22, 2018 @ 2:08 am

      Stability of an algorithm is that in which two key elements appear in the same order in the output as they are in input. Bubble sort is the most efficient and stable algorithm, as two equal elements will never be swapped in bubble sort. Because of the stability factor of the Bubble sort, it is most preferable sorting algorithm.

  5. Kyung Looney November 21, 2018 @ 1:25 pm

    How do you do a bubble sort?

    • Terence Weaver November 22, 2018 @ 2:09 am

      Bubble sort is very simple and mostly used sorting algorithm. These are the steps to follow in a Bubble sort:
      1. Compare the each pair of adjacent elements and swapped them if they are in wrong order.
      2. Repeat step 1 if at least one swap has been done from the beginning to the end of an array.

  6. Leandra Ludwig November 21, 2018 @ 1:26 pm

    What is the difference between bubble sort and merge sort?

    • Christine Towers November 22, 2018 @ 2:10 am

      Comparison chart of Bubble sort and Merge sort respectively.
      Definition- Bubble sort is to compare adjacent elements and swapped if they are in wrong order while in Merge sort, its takes a divide and conquer technique for sorting.
      Method- Bubble sort follows exchanging method. Merge sort follows divide and conquer method.
      Efficiency- Merge sort is more efficient than Bubble sort.
      Speed- Bubble sort is better for small data sets but for the large data merge sort is faster than bubble sort.
      Time complexity- O(n^2) for Bubble sort and O(n log n) for Merge sort.
      Stability- Both are stable sorting algorithms.

  7. Beverley Arthur November 21, 2018 @ 1:31 pm

    Which sorting algorithm has the best asymptotic runtime complexity?

    • Sian Rees November 22, 2018 @ 2:11 am

      There is nothing like the best sorting algorithm. That is depends on the situation and the implementation technique. Furthermore, Merge and heap sort have the best asymptotic runtime complexity because of its O(n log n) complexity in the worst case. After that, bubble and insertion sort comes in the list with O(n^2) complexity.

  8. Manual Guerra November 21, 2018 @ 1:32 pm

    Real Time Application of Bubble sort in C?

    • Ian Wingfield November 22, 2018 @ 2:12 am

      The famous real time use of the bubble sort is, we all seen in our classroom when our teacher used to say that stand up in a row and then teacher lining you all up in an ascending order of height. The bubble sort algorithm comes in use here. Teacher starts to compare the height of two adjacent students and then arrange them in their height’s ascending order. With every repeating steps of this sort, the students start standing in a more orderly fashion.

  9. Jess Berube November 21, 2018 @ 1:33 pm

    How many comparisons are made in bubble sort?

    • Patricia Olive November 22, 2018 @ 2:12 am

      In bubble sort, it requires a pair of nested loops. So, the comparison starts with (n-1) in 1st pass and with each iteration in inner loop it becomes (n-2), (n-3), and so on. Therefore total no. of comparisons will be:
      (n-1) + (n-2) + (n-3) + ……….. + 3 + 2 + 1 = n*(n-1)/2

  10. Dawne Godfrey November 21, 2018 @ 1:34 pm

    What is the best space complexity of bubble sort and What is the time complexity of bubble sort?

    • Agnes Ward November 22, 2018 @ 2:13 am

      The total no. of comparisons in the bubble sort is:
      (n-1) + (n-2) + (n-3) + ……….. + 3 + 2 + 1 = n*(n-1)/2, so the time complexity of bubble sort is O(n^2).
      Bubble sort is the simplest algorithm so the best space complexity for bubble sort is O(1) because the only one single space is required for temp variable.

  11. Doretha Fortin November 21, 2018 @ 1:34 pm

    Is O N better than O Nlogn?

    • Roy Herring November 22, 2018 @ 2:14 am

      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.

  12. Ryan Henning November 21, 2018 @ 1:36 pm

    How can the efficiency of bubble sort algorithm be determined?

    • Tim Liu November 22, 2018 @ 2:15 am

      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

  13. Haywood Schwarz November 21, 2018 @ 1:41 pm

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

    • Rhiannon Oldfield November 22, 2018 @ 2:16 am

      This is the way to sort a 2-D string array in C:
      void bubbleSort(char a[][100], int sz){
      char temp[100];
      int i,j;
      for(i=0; i<sz; i++){
      for(j=i+1; j 0){
      strcpy(temp, a[j]);
      strcpy(a[j], a[j-1]);
      strcpy(a[j-1], temp);
      } } }
      }
      main(){
      char x[10][100] = {“to”,”be”,”or”,”not”,”to”,”be”,”that”,”is”,”the”,”question”};
      bubbleSort(x,10);
      for(int i=0;i<10;i++)
      printf("%s\n",x[i]);
      system("pause");
      }

  14. Scarlet Wing November 21, 2018 @ 1:41 pm

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

    • James Swift November 22, 2018 @ 2:17 am

      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;
      }
      }

  15. Evangelina Slocum November 21, 2018 @ 2:09 pm

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

  16. John Smith November 21, 2018 @ 2:13 pm

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

    • Ken Wanless November 22, 2018 @ 2:17 am

      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.

  17. Amado Orta November 21, 2018 @ 2:13 pm

    What is the loop invariant of bubble sort?

    • Heather Williams November 22, 2018 @ 2:18 am

      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]);

Your email address will not be published. Required fields are marked *

*