This is the 5th day of my participation in the August More Text Challenge

Bubble sort

Bubble sort is probably the first algorithm that every programmer learns. Bubble sort is very simple, we will be a data before and after a data comparison, if the previous data is bigger than a data after (smallest), will the data before and after a data exchange, this operation has been from the first data to the last data of the previous data, this time we just finished a bubbling operation. Data in order to facilitate understanding, we can be divided into two, one is bubbling interval (requires bubbling operating range), another is ordered interval, each bubble operation from the inside of the bubble find maximum and put orderly interval, so if an array with n data, also is that we need to be n times of bubble to finish sorting operation.

For example, suppose there are five numbers in an array and they need to be sorted from smallest to largest.

Perform the first bubbling operation, find the maximum value 5 from the bubbling interval, and put it into the ordered interval.

For the second bubbling operation, find the maximum value 4 from the bubbling interval and put it into the ordered interval.

And so on, continue bubbling until the sorting is complete. The result of each bubble is as shown in the figure below. Each bubble takes a sorted number and places it in an ordered interval.

Bubble sort code

function bubbleSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  for (var i=0; i<arr.length; i++) {
    for (var j=0; j<arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        var temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
  return arr
}
Copy the code

The I loop body is used to iterate over the number of bubbling operations. The number of bubbling operations is the number of data in the array. The operation in the j loop body is a bubble operation. The J loop body is used to iterate over each data in the number set and determine whether a swap operation is needed.

The most difficult part of the code to understand is the j < arr.length-i – 1 in the body of the j loop. Arr.length-i is the length of the array minus the number of bubbles, because each time the bubble completes, one data is arranged, and the next bubble does not need to manipulate the arranged data. In other words, the amount of data operated by the next bubble must be the amount of data operated by the last bubble minus 1, and the amount of data operated by each bubble is equal to arr. Length -i. Why subtract 1 from arr. Length-i – 1? That’s because the arr[j+1] subscript in the if judgment needs to be kept out of bounds, and the bubbling operation traverses the last data without having to swap with the next data because there is no data left.

Optimized version of bubble sort

If you are careful, you will notice that the bubble sort in the above example is actually completed after the third bubble, and the following bubble operation does not seem to need to continue.

This can be optimized so that during one bubbling operation, when no data is swapped, the sequence is sorted and the next bubbling operation is not required. In other words, after the third bubbling, the fourth bubbling found that no data exchange had occurred in the bubbling interval, which was sorted.

Optimized version of bubble sort

function bubbleSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  for (var i=0; i<arr.length; i++) {
    var flag = false
    for (var j=0; j<arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        var temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
        flag = true}}if(! flag) {break}}return arr
}
Copy the code