# Advanced optimization of bubble sorting

The idea of bubble sorting: we take ascending sorting as an example. The so-called bubble sorting is to select the largest number in each run in an unordered array and put the next largest number in the second run in the last place until the sorting is completed. And so on Descending is to sort small numbers after them. The code is as follows:

Method (1)

``` 1     var arr = [6, 5, 3, 4, 1, 2];
2     function sort(arr) {
3         // Traverse array, times is arr.length - 1
4         for (var i = 0; i < arr.length - 1; i++) {
5             // Here, according to the outer layer for Cyclic i，Gradually reduce the inner layer for loop j So we need to reduce the number of times i.
6             for (var j = 0; j < arr.length - 1-i; j++) {
7                 if (arr[j] > arr[j + 1]) {
8                 //Set third party variables( x)It is used for data exchange, and the performance of this variable is better when it is placed outside the loop. Compare the two, and put the large number behind.
9                     var x = arr[j + 1];
10                     arr[j + 1] = arr[j];
11                     arr[j] = x;
12                     // Using addition to realize the exchange of two data
13                     // arr[j] = arr[j] + arr[j+1];
14                     // arr[j+1] = arr[j] - arr[j+1];
15                     // arr[j] = arr[j] - arr[j+1];
16
17                     // Using bit operation to realize the exchange of two data
18                     //arr[j] = arr[j]^arr[j+1];
19                     //arr[j+1] = arr[j]^arr[j+1];
20                     //arr[j] = arr[j]^arr[j+1];
21
22                 }
23
24             }
25
26             console.log("The first" + (i + 1) + "The array after suborder is" + arr);
27
28         }
29
30     }
31  sort(arr);32 console.log(arr);```

Operation mechanism is shown in the figure:

Method (2)

It is mainly about the optimization of method 1. Set a flag. If there is an exchange this time, it is true. Otherwise, it is false. If there is no exchange after a visit, the sorting is completed. The code is as follows:

``` 1   var arr = [3, 2, 1, 4, 5, 6];
2     function sort(arr) {
3         var maxNum = arr.length - 1;
4         for (var j = 0; j < maxNum; j++) {
5             // Declare a variable as a flag bit
6             var done = true;
7             for (var i = 0; i < maxNum - j; i++) {
8                 if (arr[i] > arr[i + 1]) {
9                     var temp = arr[i];
10                     arr[i] = arr[i + 1];
11                     arr[i + 1] = temp;
12                     done = false;
13                 }
14             }
15             console.log("The first" + (i + 1) + "The array after suborder is" + arr);
16             if (done) {
17                 break;
18             }
19         }
20         return arr;
21     }
22     sort(arr);
23     console.log(arr);```

Method (3)

The first two methods are further optimized. If the array length is 30, if only the first 15 bits are in disorder, the last 15 bits are in order and larger than the first 15 bits, so the exchange position must be less than 15 in the first traversal sorting, and the position after it must be in order. We only need to sort the position before it, so we need to mark Just remember this location. The code is as follows:

```    var arr = [3, 2, 1, 4, 5, 6];

function sort(arr) {
var n = arr.length;
var j, k;
var flag = n;
while (flag > 0) {
k = flag;
flag = 0;
for (j = 1; j < k; j++) {
if (arr[j - 1] > arr[j]) {
x = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = x;
flag = j;
}
}
}
}
sort(arr);
console.log(arr);
```

Keywords: Javascript less

Added by timgetback on Tue, 03 Dec 2019 13:24:02 +0200