In preparation for the interview process, we often easily fall in to a lot of difficulty is high in the title, ignoring the more basic questions, the interviewer in our case, did not understand at first might ask us more based algorithm, data structure, for example, excuse me you good write bubble sort? If not, the interview may be over. Ha ha ~, let’s learn this relatively simple sorting algorithm today ~

What is bubble sort?

Bubble sort is a sort of ideology, if we get an array, the array is a pile of chaotic digital, bubble sort can make this pile of chaotic digital and orderly, so called XX sort, bubble sort, rather than the other because bubble sort sorting of each round will be the biggest value set to the last position, like a bubble, That’s why it’s called bubble sort.

The idea of bubbling sort

  1. The number of rounds sorted is the length of the array -1.
  2. Each round of sorting puts the largest value at the end.
  3. The next round of sorting requires one less comparison than the previous round.

Implement bubble sort

function mySort(arr) {
    let temp;
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp; }}}console.log(arr);
    return arr;
}
mySort([8.9.7.3.2.6])
Copy the code

Time complexity and space complexity analysis

  • Spatial complexity

In space, we only define a temporary variable for interchangeability, so the space complexity is O(1).

  • Time complexity

Let’s analyze the worst-case time complexity. If the array is fully inverted, the time complexity is 3n(n-1)/2, so the average time complexity is O(n^2).

Stability of bubble sort

Before we can tell whether bubble sort is stable, we need to know what kind of algorithm is stable. Stable algorithm popular speaking is that if two values are the same, sorting A in front of B, sorting A in front of B, such sorting algorithm we call stable sorting algorithm, on the contrary, called unstable sorting algorithm, so bubble sorting is stable.