Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

preface

Recently in the study of some sorting algorithm related knowledge, and then in order to consolidate knowledge, want to learn to think in the form of the article to collate records and output. Mention sort, presumably everyone can think of bubble sort, I believe that as long as programmers should also know this familiar classical algorithm. Although bubble sort is not the optimal sorting scheme, it is definitely a classic. When I first learned bubble sort, I didn’t know its specific idea. The teacher just let us remember a formula: “outer loop N-1, inner loop N-I-1. Where n is the length of the array and I is the variable of the outer loop “. Not to mention this formula is really accurate, a set of accurate. So confused with the use of several years, although every time can be used to, but as that sentence: know what you know, do not know why. It wasn’t until a while ago that I learned about algorithms that I completely understood why I did it this way, and I also learned that there was an optimization. Next we will analyze the bubble sort implementation ideas and optimization scheme.

Thought analysis

Given an unordered array [12, 1,8,21,7,4,10], we want the values in this array to be sorted in ascending order. The desired result is [1, 4,7,8,10,12,21]. In fact, the principle of bubbling is very simple, two adjacent numbers compare and then switch positions, for example, the array above. Remember our formula (outer cycle N-1, inner cycle N-I-1)

  • The loop starts with 12 and 1, and finds that 12 is larger than 1. Then switch places and become: [1,12,8,21,7,4,10]
  • The cycle continues 12 to 8, switching positions: [1,8,12,21,7,4,10]
  • The loop continues 12 and 21 without switching places: [1,8,12,21,7,4,10]
  • The cycle continues 21 and 7, switching positions: [1,8,12,7,21,4,10]
  • The cycle continues 21 and 4, switching positions: [1,8,12,7,4,21,10]
  • Continue the loop 21 and 10, switch places: [1,8,12,7,4,10,21]
  • At the end of the cycle, six comparisons were made

We found that we didn’t get what we wanted in the end, but the largest number was last. Obviously, one cycle is not enough. According to the formula above, a total of 6 (outer cycle n-1) cycles are required to get the desired result.

  • At the end of the second cycle, the results are obtained: [1,8,7,4,10,12,21]. This cycle is compared for 5 times in total, and the second largest value is ranked to the last.
  • The end of the third cycle: the results obtained are as follows: [1,7,4,8,10,12,21]. This cycle has been compared for 4 times in total, and the third largest value is ranked as the third from the bottom.
  • End of the fourth cycle: the results are obtained: [1,4,7,8,10,12,21]. This cycle is compared for three times in total, and the fourth value is ranked to the fourth from the bottom.
  • End of the fifth cycle: the result is obtained: [1,4,7,8,10,12,21]. This cycle is compared twice in total, and the fifth value is ranked to the fifth from the bottom.
  • The end of the sixth cycle: the result is obtained: [1,4,7,8,10,12,21]. This cycle is compared once in total, and the sixth value is ranked to the sixth from the bottom.
Copy the code

After the above six cycles, we have finally got the expected result. However, it is not difficult to see from the above analysis that in fact, we have already got the expected result in the fourth round, so why we need to continue the cycle for 2 rounds (outer cycle N-1), and why the inner cycle is n-I-1? In fact, the array in the above example is quite special and gets the result on the fourth round, but according to the bubbling principle: Both adjacent numbers need to be compared, and only two adjacent numbers change positions in each cycle. Therefore, after the end of the fourth round, the fifth round of 1, 4, 7 and the sixth round of 1, 4 need to be compared to ensure that every two adjacent numbers can be compared. In other words, n-1 round must be carried out.

As for the inner cycle N-I-1: Can be seen from the above several rounds of cycle, the cycle of each round will be larger number to the back, such as the first round of the end of the cycle maximum 21 in the ranking, and again for a second loop 21 don’t have to participate in the comparison, because it is the maximum value, in the same way in the third round loop so penultimate values and the last value were also does not need to participate in, Similarly, the number of inner cycle comparison is gradually decreasing, so the inner cycle n-i-1 is obtained

The bubbling code

let nums = [12.1.8.21.7.4.10];
let n = nums.length;
for(let i = 0; i < n - 1; i++){
	for(let j = 0; j < n - i - 1; j++){
		if(nums[j] > nums[j+1]){
			[nums[j+1], nums[j]] = [nums[j], nums[j+1]]}}}Copy the code

conclusion

So far we have realized the bubble sorting algorithm, but from the above analysis, this is not the optimal bubble, there will be some unnecessary waste. We will analyze bubbling optimization in the next article on bubbling optimization of classical sorting algorithms.