In this data structure course material, one of the simplest sorting methods is Buble sort (bubble method). This session will explain about:
Definition/concept of bubble sort
The advantages of the bubble sort method
A weakness of the bubble sort method
Buble sort algorithm
Analysis of the bubble sort algorithm
Implement bubble sort in C or C ++ language
Definition / Concept of Buble Sort
Bubble sort method is inspired by soap bubbles that are on the surface of the water. Because the density of soap bubbles is lighter than the density of water, the soap bubbles always float to the surface. The above principle is used in bubble sequencing.
Bubble sort is a sorting method/algorithm by exchanging data right next to it continuously until it can be ascertained in one particular iteration there is no change. If there is no change, the data is sorted. It is called bubble sorting because each key will slowly balloon to its right position.
Excess Bubble Sort
Buble Sort method is the simplest method
Buble Sort method is easy to understand the algorithm
A weakness of Bubble Sort
Although simple Bubble sort method is the most inefficient ordering method. The weakness of bubble sort is that when sorting out very large data will experience tremendous delays, or in other words, the performance deteriorates quite significantly when the data is processed if the data is quite large. Another disadvantage is the number of repetitions will remain the same even though the actual data is sufficiently ordered. This is because each data is compared with every other data to determine its position.
Bubble Sort Algorithm
Compare the data to the I with the (i + 1) data (right next to each other). If it is not appropriate then exchange (data i = data (i + 1) and data (i + 1) = data i). What does that mean is not appropriate? If we want the algorithm to produce data with ascending order (A-Z) the condition is not suitable is data i> data i + 1, and vice versa for descending (A-Z) sequence.
Compare the data to (i + 1) with (i + 2) data. We do this benchmarking until the latest data. Example: 1 with 2; 2 with 3; 3 with 4; 4 with 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 the 1st rule. starting from the first data with the second data, etc.
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:
1st iteration: 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 exchanges)
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) -> the process is complete
Bubble Sort Algorithm Analysis
The purpose of algorithm analysis is to find out the efficiency of the algorithm. In this case, a comparison is made between two or more sorting algorithms. The analysis stage is to check the program to ensure that the program is logically and syntactically correct (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 is data that is not sorted or random data, enlarged sequentially /, and sorted decreases.
One way to analyze the speed of the sorting algorithm when 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 the case where the number of entries for a lot is ordered, it is better to use sorting algorithms such as quicksort, merge sort, or heap sort because the time complexity for the worst case is O (n log n). This will certainly be very different if we use the sorting insertion sort or bubble sort algorithm where the time needed to search will be very long. This is due to the worst time complexity for the sorting algorithm with a large number of inputs is O (n2).
