preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

start

Bubble sort compares all two adjacent items and swaps them if the first is larger than the second. Items move up to the correct order, like bubbles rising to the surface, hence the name bubble sort.

When you start learning sorting algorithms, you usually start with bubbling, because it’s the easiest sorting algorithm of all. However, bubbling sort is one of the worst from a runtime perspective

Train of thought

Such as an array,4,3,2,1 [5]Pairwise comparison of two adjacent terms is carried out in the figure

  • As you can see from the figure above, after four comparisons between two adjacent elements, the 5>1 swap array on line 5 on the left becomes,3,2,1,5 [4]At the end of the first round, the last element has the highest value atarray[4]
  • As you can see from the figure above, the second round starts at line 6 on the left, also from the first element, and the next two elements are compared, but no morearray[4]It’s already the largest, and after line 9 to the left, it ranks the second largest numberarray[3]
  • With the exception of the first round, each subsequent round will be compared one less than the previous round, with the order of 4, 3, 2, and 1 round for a total of 10 rounds
  • And so on and so forth[1, 2, 3, 4, 5]

implementation

    function bubbleSort(array) {
      var sum = 0; // Count the number of loops
      for (var i = 0; i < array.length; i++) {
        noswap = true;
        for (var j = 0; j < array.length - 1 - i; j++) {
          sum += 1
          if (array[j] > array[j + 1]) {
            [array[j], array[j + 1]] = [array[j + 1], array[j]]; }}}console.log('sum: ', sum); / / 10
      return array
    }
    var arr = [5.4.3.2.1]
    console.log(bubbleSort(arr)) / / [1, 2, 3, 4, 5]
Copy the code

To optimize the

The above example writes [5,4,3,2,1] to form an array, which requires 10 comparisons. What about [2,1,3,4,5]? 4 and 5 is the right place, with the above method is still need more 10 times, the next is optimized, add a flag to jump out of the circle, in a round of cycle after the comparison, if don’t have any exchange, can think this array has the desired effect, the next round, it is not necessary to continue, the writing finally only compare the seven times

    function bubbleSort(array) {
      if (array.length <= 1)  return array;  // If the array length is 1, return it directly
      var sum = 0.// Count the number of loops
          flag = true; // it is used to check out of the loopTODO:To optimize the
      for (var i = 0; i < array.length; i++) {
        flag = true;
        for (var j = 0; j < array.length - 1 - i; j++) {
          sum += 1
          if (array[j] > array[j + 1]) {
            [array[j], array[j + 1]] = [array[j + 1], array[j]];
            flag = false; // TODO:To optimize the}}// TODO:To optimize the
        if(flag){
          break; }}console.log('sum: ', sum); / / 7
      return array
    }
    var arr = [2.1.3.4.5]
    console.log(bubbleSort(arr)) / / [1, 2, 3, 4, 5]
Copy the code

Time complexity

In worst-time order, the cases to be sorted are all inversions like [5,4,3,2,1]. Suppose there are n elements in the array, the first round needs to compare n-1 times, the second round needs to compare N-2 times, and so on, the last round only needs to compare n-1 times, so the time complexity = (n-1) + (n-2) +… + 2 + 1 = N (n-1)/2 = ½*n² -½ According to the calculation method of time complexity in the previous chapter, the calculation method is as follows: remove the low-order term from the operands of the operation performed by the algorithm, and then remove all the coefficients to calculate the complexity. Subtract the coefficient by 1/2 and you get O(n ^ 2).

The last

Dregs a, welcome all great god many correction, not praise, just supervision correction