JavaScript bubble sort algorithm

via Bubble sort is often the first sorting algorithm that people think of because it is relatively simple and easy to understand. The basic idea is to compare two numbers at once and make sure they are in the correct order before moving on to other items. At the end of each level, valuable items are "sorted" into their correct positions, ultimately leaving only other items to sort. Original text from: http://caibaojian.com/javascript-bubble-sort.html

Algorithm implementation idea

Compare the first item and the second item

If the first item should be behind the second item, swap them

Compare the second item and the third item

If the second item should be after the third item, swap them

Continue until the end of the data

This process is repeated several times until the data is completely sorted. In each cycle, Since the last item is sorted correctly each time, fewer and fewer items are sorted. For a better understanding, let’s compare an array: [3, 2, 4, 5, 1].

Example comparison process

The first is positive sorting, comparing the first item and the second item, because 2 to 3 small, so 3 is arranged at the end, and the result is [2,3,4,5,1].

The order of the second and third items is correct and no need to be exchanged; the third and fourth items are also correct , no need to exchange, the fourth and fifth items are exchanged, the result is [2,3,4,1,5].

Loop the first and second items again, and then exchange the third and fourth items, For [2,3,1,4,5]

The third cycle, the second and third exchanges are [2,1,3,4,5]

The fourth cycle, the first and second exchanges The first step to implement bubble sorting for [1,2,3,4,5]

is to create a method to exchange the two items in the array. This method is common in many inefficient sorting. A simple JavaScript implementation code is:

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

via As mentioned above, this sorting algorithm is relatively inefficient because it requires multiple sortings. Assuming that an array has n items, then it requires 2 to the nth power to calculate. Let us take a look at this original text from: http://caibaojian.com/javascript-bubble-sort.html

Forward Bubble Algorithm

function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }

    return items;
}

The outer loop of via controls the number of cycles, and the inner loop is the sorting comparison between items.

Reverse Bubble Sort

function bubbleSort(items){
    var len = items.length,
        i, j;

    for (i=len-1; i >= 0; i--){
        for (j=len-i; j >= 0; j--){
            if (items[j] < items[j-1]){
                swap(items, j, j-1);
            }
        }
    }

    return items;
}

viaThe results of the above two codes are the same, they are both sorted from small to large, but the order of the loop is slightly different, they are all positive order bubbles.

Reverse bubble sort

actually judges the size change. When the first item is smaller than the second item, swap positions, and so on.

function bubbleSort2(items){
var len = items.length,
i,j,stop;
for(i=0;i<len; i++){
for(j=0,stop=len-i;j<stop;j++){
if(items[j]<items[j+1]){
swap(items,j,j+1);
}
}
}
return items;
}

Summary

via Once again, bubble sort may not be applicable to your actual work. It is just a simple tool to help us understand the algorithm and lay the foundation for further acquisition of more knowledge. The one we use most is probably the built-in Array.prototype.sort() prototype method because it is more efficient.

For more articles related to JavaScript bubble sorting algorithm, please pay attention to the PHP Chinese website!