In this data structure course, one of the simplest sorting methods is bubble sorting. This session will explain about:
Definition/concept of bubble sort
Advantages of the bubble sort method
Disadvantages of the bubble sort method
Bubble sorting algorithm
Bubble sort algorithm analysis
Implement bubble sort in C or C++
Definition / Concept of Bubble Sort
The bubble sort method is inspired by the soap bubbles on the surface of the water. Because the density of soap bubbles is lighter than the density of water, soap bubbles always float to the surface. The above principles are used in bubble sorting.
Bubble sort is a sorting method/algorithm by exchanging the data right next to it continuously until it can be ensured that in one particular iteration there is no change. If there are no changes, the data is sorted. It’s called bubble sorting because each button will slowly bubble to the right position.
Advantages of Bubble Sort
The Bubble Sort method is the simplest method
The Bubble Sort method is easy to understand the algorithm
Weaknesses of Bubble Sort
Although the simple Bubble sort method is the least efficient method of ordering. The disadvantage of bubble sort is that when sorting very large data, it will experience tremendous delays, or in other words, a significant decrease in performance when the data is processed if the data is large enough. Another drawback is that the number of repetitions will remain the same even though the actual data is quite sorted. This is because each data is compared with every other data to determine its position.
Bubble Sort Algorithm
Compare data to I with data (i+1) (exactly next to each other). If it does not match, then an exchange is made (data i = data (i+1) and data (i+1) = data i). What does inappropriate mean? If we want the algorithm to generate data in ascending order (AZ) then the unsuitable condition is data i > data i+1, and vice versa for descending order (AZ).
Compare the data with (i + 1) with (i + 2) data. We do this benchmarking until the latest data. Example: 1 by 2; 2 by 3; 3 by 4; 4 by 5 …; n-1 with n.
Finished one iteration, is if we have finished comparing between (n-1) and n. After completing one iteration, we continue the next iteration according to rule 1. starting from the first data to the second data, and so on.
The process will stop if there is no exchange in one iteration.
Bubble Sort Case Example
Suppose we have data like this: 6, 4, 3, 2 and we want to sort this data (ascending) using bubble sort. The following are the processes that occur:
Iterations 1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (there are 3 exchanges)
2nd iteration: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (there are 2 swaps)
3rd iteration: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (there is 1 exchange)
4th iteration: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (there are 0 exchanges) -> process complete
Bubble Sort Algoritma Algorithm Analysis
The purpose of algorithm analysis is to determine the efficiency of the algorithm. In this case, a comparison is made between two or more sorting algorithms. The analysis stage is checking the program to ensure that the program is logically and syntactically correct (the tracing or debugging stage). The next step is to run the program to find out the running time or computing time in this case
including the number of steps. The test data used are unsorted data or random data, sequentially enlarged, and descending.
One way to analyze the speed of the sorting algorithm during running time is to use Big O notation. The sorting algorithm has the best, worst, and average time complexity. With Big O notation, we can optimize the use of sorting algorithms. For example, in cases where the number of entries for multiple is ordered, it is better to use a sorting algorithm such as quicksort, merge sort, or heap sort because the time complexity for the worst case is O(n log n). This of course will be very different if we use the insertion sort or bubble sort algorithm where the time required for searching will be very long. This is because the worst time complexity for a sorting algorithm with a large number of inputs is O(n2).
Download Implementation of Bubble Sort Program in C/C++ Language
Download Link
