Sit on the toilet and watch the algorithm (2): neighbors are easy to talk, bubble sorting

Sit on the toilet and watch the algorithm (2): neighbors are easy to talk, bubble sorting

Original source: Ji Lei

The simplified version of bucket sorting is not only the problem left over from the previous section , but it is even more terrible: it is a waste of space! For example, the range of the number to be sorted is between 0-2100000000, then you need to apply for 2100000001 variables, that is to say, write int a[2100000001]. Because we need to use 2100000001 "buckets" to store the number of occurrences of each number between 0 and 2100000000. Even if you only sort 5 numbers (for example, the 5 numbers are 1, 1912345678, 2100000000, 18000000 and 912345678), you still need 2100000001 "buckets", which is a waste of space! Also, what if the numbers that need to be sorted are no longer integers but some decimals, such as 5.56789, 2.12, 1.1, 3.123, 4.1234, which are five numbers sorted from small to large? Now we come to learn another new sorting algorithm: bubble sort. It can solve these two problems very well.

The basic idea of ​​bubble sort is: every time two adjacent elements are compared, if they are in the wrong order, they will be exchanged.

For example, we need to sort the 5 numbers [12, 35, 99, 18, 76] from largest to smallest. Since it is sorted from largest to smallest, that is to say, the smaller the lower, do you think I am talking nonsense, but this sentence is very important (∩_∩).

First compare the size of the first and second digits. Now the first digit is 12 and the second digit is 35. It is found that 12 is smaller than 35, because we want to be as small as possible, so we need to exchange the positions of these two numbers. After the exchange, the order of these 5 numbers is 35 12 99 18 76.

According to the method just now, continue to compare the size of the second and third digits. The second digit is 12 and the third digit is 99. 12 is smaller than 99, so you need to swap the positions of these two numbers. After the exchange, the order of these 5 numbers is 35 99 12 18 76.

According to the rules just now, continue to compare the size of the 3rd and 4th digits, and if the 3rd digit is smaller than the 4th digit, exchange positions. After the exchange, the order of these 5 numbers is 35 99 18 12 76.

Finally, compare the 4th and 5th positions. The order of the 5 numbers after 4 comparisons is 35 99 18 76 12.

After 4 comparisons, we found that the smallest number is already in place (already in the last digit, please pay attention to the movement process of the number 12), is it magical? Now let's recall the process of comparison just now. Each time, two adjacent numbers are compared. If the number behind is larger than the number before, the positions of the two numbers are exchanged. The comparison continues until the last two numbers are compared, and the smallest number is the last one. Just like a bubble, "rolling" step by step backwards until the last one. So this sorting method has a nice name "bubble sort".

Speaking of this, in fact, our sorting only returns the smallest one of the five numbers. Every time we return a number, we call it "a trip." Below we will continue to repeat the process just now, returning the remaining 4 numbers one by one.

Fortunately, now we will start the "second trip". The goal is to return the second smallest number to its place. 1. compare the first and second positions. If the first position is lower than the second position, the positions are exchanged. After the exchange, the order of these 5 numbers is 99 35 18 76 12. Next you should be all, compare the 2nd and the 3rd, the 3rd and the 4th in turn. Note that there is no need to compare the 4th and 5th positions at this time. Because after the end of the first trip, it can be determined that the 5th place is the smallest. After the second pass, the order of these 5 numbers is 99 35 76 18 12.

The same is true for the third pass. After the third pass, the order of the 5 numbers is 99 76 35 18 12.

Now it's the last trip, the "fourth trip". Some students have to ask again, isn't this already arranged? Want to continue? Of course, this is purely coincidental, and you can try it with other numbers. Can you find a sample of such data? Please give it a try.

The principle of "bubble sorting" is that only one number can be determined in each pass. That is to say, the first pass can only determine to return the number in the last place (that is, the fifth place), the second pass can only return the number in the penultimate place (that is, the fourth place), and the third pass can only return The number in the third place from the bottom (that is, the third place) has returned to its place, and now there are two numbers in the previous position that have not returned to its place, so we still need to do the "fourth pass".

The "fourth trip" only needs to compare the size of the first and second digits. Because the numbers in the last three positions are back in place, now the first digit is 99 and the second digit is 76, so there is no need to swap. The order of these 5 numbers remains unchanged at 99 76 35 18 12. At this point, the sorting is perfectly finished, and 4 of the 5 numbers have returned, so the last number can only be placed in the first place.

Finally, let's summarize: if there are n numbers to sort, just return the n-1 numbers, which means to perform n-1 operations. "Each trip" needs to compare two adjacent numbers starting from the first digit, put the smaller number behind, and move one digit backward after the comparison to continue to compare the size of the next two adjacent numbers. , Repeat this step until the last number that has not been reset, and the number that has been reset does not need to be compared again (what do you compare with the number that has been reset, waste expression)

Is this algorithm very powerful? I remember that every time I took a group photo, I was always exchanged for it, which was very annoying at the time. I don’t know if the inspiration of the person who invented this algorithm came from this. Rory talked so much, here is the code. It is recommended to try to realize it by yourself first, and then see how I realized it.

The core part of bubble sort is double nested loops. It is not difficult to see that the time complexity of bubble sort is O(N2). This is a very high time complexity. Bubble sorting has been studied as early as 1956. After that, many people have tried to improve the bubble sorting, but the results were disappointing. As Knuth (Donald E. Knuth's Chinese name is Gartner, winner of the Turing Award in 1974) said: "Bubble sorting, in addition to its fascinating name and the fact that it has caused some interesting theoretical problems, seems There is nothing to recommend." You may ask: Is there a better sorting algorithm? Please look forward to next week's update-quick sort.

Reference: https://cloud.tencent.com/developer/article/1055102 Sit on the toilet and watch the algorithm (2): Neighbors talk easily, bubble sorting-Cloud + Community-Tencent Cloud