Writing in the front
For bubble sort, many small partners can already be said to be very familiar with, easy to write, but for a beginner, deer want to through this article, let you understand bubble sort and bubble sort optimization, do not have to go to read other articles.
I remember that a reader told Deer that when he went for an interview, the interviewer asked him to write a bubble sort, which was also written, but he failed to pass the interview. In fact, his bubble sort is not optimized, and that’s not the point.
In the data structure and algorithm, I have a important discoveries, myself included early just contact data structure, for some sorting algorithms are to go back and understand, but this understanding, if you don’t have very deep understanding, at the time of writing code easily, so, if you want to quickly and accurately and give the interviewer a satisfactory bubble sort, follow the deer to learn.
1. What is bubble sort?
Bubbling sort, as the name suggests, is bubbling. The first thing that comes to mind is the bubbling process of fish in the water. “Never seen a fish! Well, then let you see fish bubble, ha ha!
2. Design a bubble sort
If you were the person who designed the bubble sort, how would you design it according to the principle of fish blowing bubbles? So today we’re going to assume that we’re the one designing bubble sort, how do we design a bubble sort?
The rule we found in fish bubbles is that the largest bubbles per bubble are at the top (near the surface), so we also want to put the maximum value of a set of data at the top. The raw data given is as follows:
So just to make sense of it, let’s make the array stand up.
The basic goal we have identified is to put the largest number at the end of the array (we can imagine the array standing up with the tail on top and the header on the bottom). Since the largest is at the top, how can you find the largest in a set of data and put it at the top? The top data will look like the following (with 8 at the top) :
If we start at the bottom, compare the first two numbers, and if the number on the top is larger than the number on the bottom, compare the number on the top with the number on the top. If the bottom number is larger than the top number, we switch the two numbers. And so on, when the group comes down, the maximum value of the group goes to the top. How does this process work? The following animation:
Flicker represents comparison and magnifies to two maximum values
Each time you look for the maximum value, you look for the maximum value from the remaining data and place it at the top.
What we see is that after the top group bubbles down, 8 is at the top, and then the rest of the data bubbles again, same bubbling process.
Let’s say I have n data, and when I bubble n minus 1 times, all of the data is sorted.
3. Bubble sorting optimization
We will find that one problem in the bubble sort we designed is that if the group of data is already sorted, if we still say as above, each data needs to bubble once, the performance efficiency will be very low, so we optimize the bubble sort we designed once.
How do you optimize it? We can add a judgment, if we don’t exchange data when we’re bubbling in the first set of data, the data is already in order, and we just go back to this set of data, there’s no need to continue bubbling down.
4, handwritten bubble sort
1/** 2 * Time :2019/3/14 3 * Function: bubble sort 4 * @param A: array 5 * @param N: array size 6 * Boundary conditions: 7 * 1) Check whether the array has data 8 * Algorithm idea: 9 * 1) outer loopforN data required n times of bubbling 10 * 2) comparison number of each bubbling in the inner loop, the comparison number of each bubbling is -1 11 * 3) bubbling optimization 12 */ 13var flag =false;
14const bubblesort = (a) =>{
15 if(a.length < 1) return;
16 for(leti = 0; i < a.length; i++){ 17for(letj = 0; j < a.length-1-i; j++){ 18if(a[j]>=a[j+1]){
19 let temp = a[j];
20 a[j] = a[j+1];
21 a[j+1] = temp;
22 flag = true; 23} 24} 25if(! flag){ 26break; 27} 28} 29}Copy the code
5. Bubble sort performance
For the performance of bubble sort, you can analyze the performance from two aspects, the first is time complexity, and the other is space complexity.
5.1 Time Complexity
In terms of time complexity, let’s look at efficiency, if the process of finding the maximum value of data is n minus 1 times, n data, n times of bubbling. So the time is (n-1) ² = n² -2n + 1, omitting the coefficients and the lower orders, so the time is O(n²).
We also have a case where the data is already sorted, so it just bubbles once, order n time. This is the best time, but in general, it’s very rare, so the average time for bubble sort is O(n ^ 2).
5.2 Space Complexity
What are we looking at in spatial complexity? The space complexity is mainly concerned with the extra space used. For example, in the process of bubbling, data exchange is involved, and temporary space needs to be applied for during the exchange, which is constant level. For other things, there is no need to open additional memory space, so the space complexity is O(1).
6, summary
Today we mainly shared bubble sort, what it is, and we designed our own bubble sort through the principle of fish bubble, to deepen the understanding of the whole process of bubble sort. Then we also broke down the process of handwritten fake sorting, as well as bubbling optimization, which allowed us to give the interviewer a satisfactory bubbling sorting during the interview.
Usually in the interview, bubble sort is the most important is not only write the main process, but also consider the optimization process of bubble sort, many candidates tend to ignore this, you must not forget oh!
❤️ Don’t forget to leave your learning footprints[Likes + Favorites + comments]
All see the article not praise are “play rascal”, hey hey ヾ(◍°∇°◍) Blue! Just as a joke, move your little hands and click “like”, each of you will make more learners join in with a contribution (like + comment)! Thank you very much! ￣ ￣ omega =
The author Info:
【 author 】 : Deer
[original public account] : Deer animation programming.
[Introduction] : I learned programming from zero based on animation with Little Deer, and presented easy-to-understand Web front-end fields, data structures and algorithms, and network principles to my friends. Public reply “information” to send a from zero self-study information package!
[reproduced description] : reproduced please explain the source, thank you for your cooperation! ~