Looking for software development internships? Hackr.io is hiring!

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 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 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 + 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
Lalit pawar
Lalit pawar

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

Vijay Singh
Vijay Singh 262 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.

Dawne Godfrey
Dawne Godfrey

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

Agnes Ward
Agnes Ward

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.

Jess Berube
Jess Berube

How many comparisons are made in bubble sort?

Patricia Olive
Patricia Olive

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

Manual Guerra
Manual Guerra

Real Time Application of Bubble sort in C?

Ian Wingfield
Ian Wingfield

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.

Beverley Arthur
Beverley Arthur

Which sorting algorithm has the best asymptotic runtime complexity?

Sian Rees
Sian Rees

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.

Leandra Ludwig
Leandra Ludwig

What is the difference between bubble sort and merge sort?

Christine Towers
Christine Towers

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.

Kyung Looney
Kyung Looney

How do you do a bubble sort?

Terence Weaver
Terence Weaver

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.

Vivien Aaron
Vivien Aaron

Why is bubble sort stable?

Victoria Hogan
Victoria Hogan

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.

Nicky Starr
Nicky Starr

Deep Comparison between Selection Sort and Bubble Sort

Matthew Pepper
Matthew Pepper

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.

Zenia Lindstrom
Zenia Lindstrom

Is selection sort same as bubble sort?

Mohammed Islam
Mohammed Islam

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.

Chang Caruso
Chang Caruso

What is the big O of bubble sort?

Olive Mann
Olive Mann

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.