Bubble sort
Bubble sort compares the value of first element with the immediate next element and swaps according to the requirement and goes till the last element. This iteration repeates for (N - 1) times/steps where N is the number of elements in the list.
Compare and swapping two elements like small soap bubbles and hence the name given as bubble sort.
Bubble sort design
We are taking one inner loop for doing the exchange of the bubble. This loop will start from index 0 and take two immediate elements and swap if required. So this loop will iterate from 0 to a max of (count – 1) (note there are two elements).
Inner bubble iteration & swap
Outer bubble sort steps
Now, this loop is needed for each step of the bubble sort. A bubble sort will require to iterate n-1 steps as the outer loop. For each step, it will go around to the inner bubble iteration & exchange steps.
Bubble sort swap function
Bubble elements or two immediate elements can be exchanged via a swap function. This function should be a call be reference. We pass the address of two elements and this function will have a local variable to swap these two.
Bubble sort example code
Here is a C source code of Bubble sorting with 5 integer elements. This code sorts the elements in ascending order.
Steps and Iterations (diagrams)
Output
Unsorted elements [4, 9, 5, 1, 0] Bubble sort started- ==== Step 1 ==== [4, 9, 5, 1, 0] #1 no swap 4 <= 9 [4, 9, 5, 1, 0] #2 swap 9 > 5 [4, 5, 9, 1, 0] #3 swap 9 > 1 [4, 5, 1, 9, 0] #4 swap 9 > 0 [4, 5, 1, 0, 9] ==== Step 2 ==== [4, 5, 1, 0, 9] #1 no swap 4 <= 5 [4, 5, 1, 0, 9] #2 swap 5 > 1 [4, 1, 5, 0, 9] #3 swap 5 > 0 [4, 1, 0, 5, 9] ==== Step 3 ==== [4, 1, 0, 5, 9] #1 swap 4 > 1 [1, 4, 0, 5, 9] #2 swap 4 > 0 [1, 0, 4, 5, 9] ==== Step 4 ==== [1, 0, 4, 5, 9] #1 swap 1 > 0 [0, 1, 4, 5, 9] Bubble sort ended Bubble sorted elements [0, 1, 4, 5, 9]
Efficiency and Big(O)
The efficiency of a sorting algorithm decides the performance of the algorithm when the total count of the elements reaches a large number. Bubble sort of N elements can take (N - 1) steps and (N -1) iterations in each step. Thus the total number of iterations needed for bubble sort is (N - 1)*(N - 1). This sorting algorithm is however not the best in performance when considering the scalability of the elements. The time complexity of bubble sort is O(N^2) [Square of N]. This sorting is well suited for a small number of elements and it is easy to implement in C or any other programming languages.
Further readings
Types of sorting algoritms Selection Sort Insertion Sort Quick Sort Heap Sort Merge sort Radix Sort
- www.geeksforgeeks.org - bubble-sort
- www.studytonight.com - bubble-sort
- wikipedia.org - bubble-sort
- www.tutorialspoint.com - bubble-sort
- www.hackerearth.com - bubble-sort
About our authors: Team EQA
You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.