[interview: Basics 02: bubble sort]

【 interview ： The basic chapter 02： Bubble sort 】

00. Preface

Please point out any questions , Thank you guys .

01. Introduce

Bubble sort, as its name suggests, is a sort algorithm Compared with adjacent elements Then exchange Because the biggest one without a trip / minimum value Finally, it will be sorted to the last position of the current trip So the image is called bubble sort , It is a basic sort of sorting algorithm , This means that we must master .

02. Case-based reasoning

For this series {5,2,7,4,1,3,8,9} Sort by bubbling Order from small to large
The first trip
2 5 4 1 3 7 8 9, Comparison of the 7 Time , To determine the 9 It is the last place in the current trip
The second trip
2 4 1 3 5 7 8 9, Comparison of the 6 Time , To determine the 8 It is the last place in the current trip
The third time
2 1 3 4 5 7 8 9, Comparison of the 5 Time , To determine the 7 It is the last place in the current trip
The fourth trip
1 2 3 4 5 7 8 9, Comparison of the 4 Time , To determine the 5 It is the last place in the current trip
The fifth trip
1 2 3 4 5 7 8 9, Comparison of the 3 Time , To determine the 4 It is the last place in the current trip
The sixth time
1 2 3 4 5 7 8 9, Comparison of the 2 Time , To determine the 3 It is the last place in the current trip
The seventh time
1 2 3 4 5 7 8 9, Comparison of the 1 Time , To determine the 2 It is the last place in the current trip

To complete the order

03. What does this case tell us

First of all ： We found out 8 Elements need 7 Trip to sort .
second ： We found out Each sorting only needs to compare the elements that are not determined in the current time The identified elements do not need to be compared , That is, each trip only needs to be compared Element number - Current number of trips For example, on the third trip, we only need to compare 8-3 Time Because two values have been determined in the first two trips We only need to compare five of the remaining six You can determine the extreme value of the third trip .
Third ： We found that the fourth time has been sorted , But still compared three times , This is one of our optimization points , Optimize the number of trips .
Fourth ： We found that the times of each trip can also be optimized , For example, on the second trip, we compared it six times , But in fact, it was already determined in the first comparison 7 8 9 Three maximum values , So we only need to compare the rest 5 Elements , That is, only four comparisons are needed , Because we have fewer trips , So our final number of trips will also be reduced .

04. Algorithm 1 No optimization

Code

public static void main(String[] args) {
    
    int[] a = {
    5,2,7,4,1,3,8,9};
    int len = a.length;
    for(int i=0;i<len-1;i++){
    
        int cnt=0;
        System.out.println(" The first "+(i+1)+" Trip to ");
        for (int j=0;j<len-i-1;j++){
    
            if(a[j]>a[j+1]){
    
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
            cnt++;
        }
        for (int k=0;k<len;k++)
            System.out.printf("%d ",a[k]);
        System.out.printf(" Comparison times :%d\n",cnt);
    }
}

result

The first 1 Trip to
2 5 4 1 3 7 8 9 Comparison times :7
The first 2 Trip to
2 4 1 3 5 7 8 9 Comparison times :6
The first 3 Trip to
2 1 3 4 5 7 8 9 Comparison times :5
The first 4 Trip to
1 2 3 4 5 7 8 9 Comparison times :4
The first 5 Trip to
1 2 3 4 5 7 8 9 Comparison times :3
The first 6 Trip to
1 2 3 4 5 7 8 9 Comparison times :2
The first 7 Trip to
1 2 3 4 5 7 8 9 Comparison times :1

It can be seen that the non optimized version is exactly the same as our reasoning

05. Algorithm 2 Optimize the number of trips

Optimization idea

Look at the above examples We can see that the main problem is that when it is completely sorted The number of trips did not stop, but continued to compare three times , To solve this problem, we have this idea ： It's not hard to imagine. After complete sorting In each trip There must be no exchange Because and orderly Adjacent elements Are not satisfied with the exchange situation So we can only judge if No exchange at all Then it can be proved that Completely sorted

Code

public static void main(String[] args) {
    
    int[] a = {
    5,2,7,4,1,3,8,9};
    int len = a.length;
    for(int i=0;i<len-1;i++){
    
        int cnt=0;
        boolean flag=false;//  Determine whether there is an exchange 
        System.out.println(" The first "+(i+1)+" Trip to ");
        for (int j=0;j<len-i-1;j++){
    
            if(a[j]>a[j+1]){
    
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
                flag=true;
            }
            cnt++;
        }
        for (int k=0;k<len;k++)
            System.out.printf("%d ",a[k]);
        System.out.printf(" Comparison times :%d\n",cnt);
        if (!flag)
            break;
    }
}    

result

The first 1 Trip to
2 5 4 1 3 7 8 9 Comparison times :7
The first 2 Trip to
2 4 1 3 5 7 8 9 Comparison times :6
The first 3 Trip to
2 1 3 4 5 7 8 9 Comparison times :5
The first 4 Trip to
1 2 3 4 5 7 8 9 Comparison times :4
The first 5 Trip to
1 2 3 4 5 7 8 9 Comparison times :3

It can be seen that the number of trips has been reduced twice , But the reason why it didn't stop on the fourth trip was On the fourth trip, there was an exchange The real non exchange is the fifth time .

06. Algorithm 3 Optimize the number and times

Optimization idea

The optimization point of this problem is ： for example On the first trip 8 9 At the beginning, there are the two largest values So when we compare, the final result is 7 8 9 The second time we compare Will be able to 7 8 Compare again But we have determined 7 8 9 Is the maximum value , So our optimization idea is Let's record the index of the last one by one exchange , such as In the first sort The final exchange is 7 3 That is array subscript 4 The array subscript 4 The following elements are sorted So we sort the second time Only compare The array subscript 4 This position That is, just compare 4 Time Directly two times less , If the final exchange subscript is 0 It means that we have finished sorting .

Because we need to compare less times per trip than before As a result, our number of trips will decrease , Because the number of comparisons per trip was only reduced 1 Time , And now we reduce every trip >=1 So the number of trips decreases .

Understand again ： The last sorting must be the maximum number of current runs And The number of previous trips must have been arranged So we can Next time, you only need to compare to the position of the last sorting

Code

int[] a = {
    5,2,7,4,1,3,8,9};
int len = a.length;
int n=len-1;
int i=0;
while (true) {
    
    System.out.println(" The first "+(++i)+" Trip to ");
    int pos=0;// Temporarily record the position subscript of the last exchange 
    int cnt=0;
    for(int j=0;j<n;j++){
    
        if(a[j]>a[j+1]){
    
            int t = a[j];
            a[j] = a[j+1];
            a[j+1] = t;
            pos=j;
        }
        cnt++;
    }
    n=pos;// Really record the subscript of the last position 
    for (int k=0;k<len;k++)
        System.out.printf("%d ",a[k]);
    System.out.printf(" Comparison times :%d\n",cnt);
    if (n==0)
        break;
}

result

The first 1 Trip to
2 5 4 1 3 7 8 9 Comparison times :7
The first 2 Trip to
2 4 1 3 5 7 8 9 Comparison times :4
The first 3 Trip to
2 1 3 4 5 7 8 9 Comparison times :3
The first 4 Trip to
1 2 3 4 5 7 8 9 Comparison times :2

It can be seen that our comparison times and sorting times are reduced a lot