神刀安全网

The Bubble sort algorithm in JavaScript

About the #sorting-algorithms series

The #sorting-algorithms series is a collection of posts about reimplemented sorting algorithms in JavaScript.

If you are not familiar with sorting algorithms, a quick introduction and the full list of reimplemented sorting algorithms can be found in the introduction post of the series on sorting algorithms in JavaScript .

If you feel comfortable with the concept of each sorting algorithm and only want to see the code, have a look at the summary post of the series. It removes all explanations and contains only the JavaScript code for all sorting algorithms discussed in the series.

Of course, all the code can also be found on Github in the repository sorting-algorithms-in-javascript .

A good way to compare all of them

Unlike thedata structures, allsorting algorithms have the same goal and they can all take the same input data. So, for every sorting algorithms of the series, we are going sort an array of 10 numbers from 1 to 10.

By doing so we will be able to compare the different sorting algorithms more easily. Sorting algorithms are very sensitive to the input data so we will also try different input data to see how they affect the performances.

The Bubble sort algorithm

Definition

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. From Wikipedia

Visualization

If you want to have a nice visualization of the algorithm, the visualgo.net website is a nice resource. You can play with many parameters and see which part of the algorithm is doing what.

Complexity

Time complexity
Best Average Worst
O(n) O(n^2) O(n^2)

To get a full overview of the time and space complexity of the Bubble sort algorithm, have a look to this excellent Big O cheat sheet .

The code

For each sorting algorithm, we are going to look at 2 versions of the code. The first one is the final/clean version, the one that you should remember. The second one implements some counters in order to demonstrate the different time complexities depending of the inputs.

Clean version

// array to sort var array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8]  // swap function helper function swap(array, i, j) {   var temp = array[i];   array[i] = array[j];   array[j] = temp; }  // be careful: this is a very basic implementation which is nice to understand the deep principle of bubble sort (going through all comparisons) but it can be greatly improved for performances function bubbleSortBasic(array) {   for(var i = 0; i < array.length; i++) {     for(var j = 1; j < array.length; j++) {       if(array[j - 1] > array[j]) {         swap(array, j - 1, j);       }     }   }   return array }  console.log(bubbleSortBasic(array)); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]  // correct implementation: this is the usual implementation of the bubble sort algorithm. Some loops execution are avoided if not they are not needed function bubbleSort(array) {   var swapped;   do {     swapped = false;     for(var i = 0; i < array.length; i++) {       if(array[i] && array[i + 1] && array[i] > array[i + 1]) {         swap(array, i, i + 1);         swapped = true;       }     }   } while(swapped);   return array }  console.log(bubbleSort(array)); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] 

Version with counters

// sample of arrays to sort var arrayRandom = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8] var arrayOrdered = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] var arrayReversed = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]  // swap function helper function swap(array, i, j) {   var temp = array[i];   array[i] = array[j];   array[j] = temp; }  // be careful: this is a very basic implementation which is nice to understand the deep principle of bubble sort (going through all comparisons) but it can be greatly improved for performances function bubbleSortBasic(array) {   var countOuter = 0;   var countInner = 0;   var countSwap = 0;    for(var i = 0; i < array.length; i++) {     countOuter++;     for(var j = 1; j < array.length; j++) {       countInner++;       if(array[j - 1] > array[j]) {         countSwap++;         swap(array, j - 1, j);       }     }   }    console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);   return array }  bubbleSortBasic(arrayRandom.slice()); // => outer: 10 inner: 90 swap: 21 bubbleSortBasic(arrayOrdered.slice()); // => outer: 10 inner: 90 swap: 0 bubbleSortBasic(arrayReversed.slice()); // => outer: 10 inner: 90 swap: 45  // correct implementation: this is the usual implementation of the bubble sort algorithm. Some loops execution are avoided if not they are not needed function bubbleSort(array) {   var countOuter = 0;   var countInner = 0;   var countSwap = 0;    var swapped;   do {     countOuter++;     swapped = false;     for(var i = 0; i < array.length; i++) {       countInner++;       if(array[i] && array[i + 1] && array[i] > array[i + 1]) {         countSwap++;         swap(array, i, i + 1);         swapped = true;       }     }   } while(swapped);    console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);   return array }  bubbleSort(arrayRandom.slice()); // => outer: 9 inner: 90 swap: 21 (average case) bubbleSort(arrayOrdered.slice()); // => outer: 1 inner: 10 swap: 0 (best case) bubbleSort(arrayReversed.slice()); // => outer: 10 inner: 100 swap: 45 (worst case) 

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » The Bubble sort algorithm in JavaScript

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮