This is the third day of my participation in the August More text Challenge. For details, see: August More Text Challenge

concept

Let’s start with the Wikipedia definition of bubble sort:

Bubble Sort, also known as Bubble Sort, is a simple sorting algorithm. It repeatedly goes through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The work of visiting the sequence is repeated until no more exchanges are needed, that is, the sequence has been sorted. The algorithm gets its name from the fact that the smaller elements will slowly “float” to the top of the sequence by swapping.

The steps of the algorithm are as follows (from Wikipedia) :

  • Compare adjacent elements. If the first one is bigger than the second, swap them both.
  • Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. And when we do that, the last element is going to be the largest.
  • Repeat these steps for all the elements except the last one.
  • Keep repeating this step with fewer and fewer elements each time until there are no pairs of numbers to compare.

Don’t understand the concepts and procedures? Too much text to read? It doesn’t matter, let’s look at the bubble sort process through the GIF, suppose the array to be sorted is [29,10,14,37,14] :

First order

The first sorting comparison process is as follows:

  • Compare 29 with 10, 29 is larger than 10, swap positions, and then the array is,29,14,37,14 [10]
  • If you compare 29 to 14, 29 is larger than 14, and you switch places, then the array is,14,29,37,14 [10]
  • If you compare 29 to 37, 29 is less than 14, so you don’t need to swap,14,29,37,14 [10]
  • Compare 37 with 14, 37 is larger than 14, swap positions, and then the array is,14,29,14,37 [10]

At the end of the first sorting, the position is changed, and the second sorting is needed. The current array is [10,14,29,14,37]. The array to be sorted is [10,14,29,14].

Second order

The second sorting comparison process is as follows:

  • Compare 10 to 14, 10 is smaller than 14, so you don’t need to swap, so the array is,14,29,14 [10]
  • 14 is compared to 29, 14 is less than 29, so you don’t need to swap, and then the array is,14,29,14 [10]
  • If you compare 29 to 14, 29 is larger than 14, and you switch places, then the array is,14,14,29 [10]

At the end of the second sorting, the position is changed, and the third sorting is needed. The current array is [10,14,14,29,37], the array to be sorted is [10,14,14] ([29,37] ordered)

Third order

The third sorting comparison process is as follows:

  • Compare 10 to 14, 10 is smaller than 14, so you don’t need to swap, so the array is,14,14 [10]
  • 14 is compared to 14, so you don’t need to swap, so the array is,14,14 [10]

At this point, the third sorting is finished, there is no place exchange, bubble sorting is finished, and [10,14,14,29,37] is the final ordered sequence.

JavaScript code implementation

function bubbleSort(arr) {
    const len = arr.length
    let exchange = false // Indicates whether data is exchanged
    for (const i = 0; i < len - 1; i++) {
        exchange = false
        for (const j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                exchange = true
                // Switch positions
                const temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
            }
        }
        if(! exchange)return arr // There is no data position exchange, end prematurely, return array
    }
    return arr
}
Copy the code

Complexity analysis

When the array is ordered, there is no exchange of positions down a loop, the sort is finished, and the time complexity is O(n).

When the array is in reverse order, the inner loop executes (n-1)+(n-2)+… Plus 1=n times n minus 1 over 2, so the time complexity is O(n2).

conclusion

Bubble sort is one of the simplest sorting algorithms, is also the author opened sorting algorithm chapter in the first, the follow-up will continue to update the quick sort, heap sort, merge sort algorithm, please look forward to ~