Abstract: Bubble sort should be most people learn the first sorting algorithm, it is simple in thought, is a good choice of entry sorting algorithm. However, since its time complexity is O(n^2), we rarely think about it except for the time it takes to learn it, usually referring to faster sorting algorithms such as quicksort. However, after the improvement of the classical bubble sort, under certain conditions, it still has a useful place.
This paper first introduces three kinds of improvement ideas of classical bubble sort, and then combines these three ideas to realize the method of synthesizing their respective advantages.
Classic implementation of bubble sort
Instead of spending a lot of time talking about the idea of bubble sort, it simply puts the most value at the end of the array by pairwise comparison and swapping. The concrete realization can use a double layer cycle, the outer layer is used to control the inner layer cycle in the most value of the floating position, the inner layer is used for pairwise comparison and exchange positions.
Take sorting an array from smallest to largest, which is the default in the following sections. The classic implementation of bubble sort is as follows:
function bubbleSort(array){
// The outer loop uses end to control where the extreme value of the inner loop ends up
for(let end = array.length - 1; end > 0; end--){
// The inner loop is used for pairwise comparisons and swaps
for(let i = 0; i < end; i++){
if(array[i] > array[i + 1]){
swap(array, i, i+1); }}}}Copy the codeSwap () : swap() : swap() : swap() : swap() : swap() : swap() : swap() : swap()) : swap() : swap() : swap() : swap(); swap() : swap() : swap();
function swap(arr, i, j){
// [arr[i],arr[i+1]] = [arr[i+1],arr[i]]; // ES6
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Copy the codeImprovement 1: Handle the case where the whole array is already in order during sorting
If the array is already ordered or was ordered during sorting, there is no need to continue the following comparison and the array can be returned directly. But the classic implementation of bubble sort still continues to visit each element one by one and compare sizes. Although there are only comparisons and no swaps at this point, these comparisons are still unnecessary.
The sign that an array has been ordered is that no element swap has occurred in an inner loop, that is, every element from the beginning to the end is smaller than the element after it.
Using the principle above, you can improve on the classic implementation by setting a variable to record whether an element swap occurred during an inner loop, and determining whether an element swap occurred at the end of each inner loop. If no element exchange occurs, the array is in order and the program returns. Otherwise, do nothing and start the next cycle:
function bubbleSortOpt1(array){
for(let end = array.length - 1; end > 0; end--){
let isSorted = true; // <== sets the token variable isSorted to an initial value of true
for(let i = 0; i < end; i++){
if(array[i] > array[i + 1]){
swap(array, i, i+1);
isSorted = false; // <== = the array is still out of order in this round. Set isSorted to false}}// Check if the inner loop is in order, if it is in order, stop the program directly; Otherwise start the next cycle
if(isSorted){
return ; // The <== array is in order, stop the function}}}Copy the codeImproved idea 2: array local order
If the array is locally ordered, for example, if the array is already ordered after starting at a certain location, there is no need to compare that part of the array.
At this time, the improvement method is: in the traversal process, the position of the last exchange event can be recorded, and the next inner loop will terminate at this position, which can save redundant comparison operations.
Use a variable to hold the last place where the swap occurred and set it to the end of the next inner loop:
function bubbleSortOpt2(array){
let endPos = array.length - 1; // Record the position where the swap operation last occurred in this cycle
while(endPos > 0) {let thisTurnEndPos = endPos; // <== sets the end of the loop
for(let i = 0; i < thisTurnEndPos; i++){
if(array[i] > array[i+1]){
swap(array, i, i+1);
endPos = i; // <== sets (updates) the location where the swap operation last occurred}}// If there is no swap in this round, the array is in order
if(endPos === thisTurnEndPos){
return; }}}Copy the codeImprovement idea 3: return the maximum and minimum values simultaneously
In the classical implementation, the largest value is adjusted to the end of the current array each time, and the smallest value is not operated on. In fact, in the same outer loop, you can adjust the maximum value to the bottom of the array and the minimum value to the front, as long as the inner loop arranges the maximum value from front to back, and also arranges the minimum value from back to front. This idea is called bidirectional bubble sort.
If you look at the code, it’s easy to understand:
// Two-way bubble sort, not only put the largest to the last, but also put the smallest to the first
function bubbleSortOpt3(array){
// <== sets the start and end positions of each cycle
let start = 0,
end = array.length - 1;
while(start < end){
for(let i = start; i < end; i++){ // Arrange the maximum position from start to end
if(array[i] > array[i+1]){
swap(array, i, i+1);
}
}
end --; // <== because the current maximum number is already in the end position, the end position is moved forward
for(let i = end; i > start; i--){ // Go from end to start and arrange the minimum position
if(array[i] < array[i- 1]){
swap(array, i, i- 1);
}
}
start ++; // <== the start position is moved backwards because the smallest number is already in the start position}}Copy the codeHowever, this method has the disadvantage of moving backwards and forwards one position at a time, namely end– and start++. You can’t handle the two cases described in the previous section, so you can combine these three methods to your advantage.
A combination of three ideas
The above three ideas respectively deal with the case that the whole array is already ordered, the array is locally ordered, and the maximum and minimum values are placed in appropriate positions. Better results can be achieved by combining the advantages of the above three.
Step by step, let’s talk about the combination of these two ideas
A combination of ideas 1 and 2
Combining ideas 1 and 2, we deal with local ordering of arrays and global ordering during sorting:
function bubbleSortOpt1and2(array){
let endPos = array.length - 1; // Record the position at the end of the cycle, that is, the position last swapped in the previous round
while(endPos > 0) {let isSorted = true; // Sets the array's overall ordered flag variable
let thisTurnEndPos = endPos; // Record the end of the cycle
for(let i = 0; i < thisTurnEndPos; i++){
if(array[i] > array[i+1]){
swap(array, i, i+1);
endPos = i; // This position has been swapped, record this position
isSorted = false; // Set the epicycle to unordered}}if(isSorted){ // Check whether the array is fully ordered
console.log(endPos);
return; }}}Copy the codeA combination of ideas 2 and 3
Combine ideas 2 and 3 to deal with both maxima and minima in both directions, and to deal with locally ordered arrays
// In combination with the idea of the second and third improvements, record the last exchange position in each direction of two-way sorting, and update the end position of the next round of the cycle
function bubbleSortOpt2and3(array){
let start = 0, startPos = start,
end = array.length - 1, endPos = end;
while(start < end){
// Go back and forth
for(let i = start; i < end; i++){
if(array[i] > array[i+1]){
swap(array, i, i+1);
endPos = i; // Record the swap position
}
}
end = endPos; // Sets the end of the next iteration
// Go from the back to the front
for(let i = end; i > start; i--){
if(array[i] < array[i- 1]){
swap(array, i, i- 1);
startPos = i; // Record the swap position
}
}
start = startPos; // Sets the end of the next iteration}}Copy the codeUse all three ideas at once
With a pairwise foundation in place, it’s not hard to write code that combines all three ideas:
function bubbleSortOptTriple(array){
let start = 0, startPos = start,
end = array.length - 1, endPos = end;
while(start < end){
let isSorted = true; // Set the ordered unordered flag variable
// Go back and forth
for(let i = start; i < end; i++){
if(array[i] > array[i+1]){
swap(array, i, i+1);
endPos = i; // Record the swap position
isSorted = false; // Set the unordered flag}}if(isSorted){
return;
}
end = endPos; // Sets the end of the next iteration
// Go from the back to the front
for(let i = end; i > start; i--){
if(array[i] < array[i- 1]){
swap(array, i, i- 1);
startPos = i; // Record the swap position
isSorted = false; // Set the unordered flag}}if(isSorted){
return;
}
start = startPos; // Sets the end of the next iteration}}Copy the codeIs this the end?
In fact, the above program can be improved: There is no need to set another variable to record whether the array has been ordered in a sort. Instead, we can compare whether endPos is equal to end at the end of a loop. If it is, then endPos has not been updated in this round, i.e., no swap has taken place, further indicating that the array has been ordered. Of course, the same goes for startPos and start.