preface

When an interviewer asks you what is a sorting algorithm? Please use JavaScript to implement a simple bubble sort, if you do not master, you will be asked.

This article uses the way of text and text to explain the characteristics of bubble sort, step by step to explain the implementation of JS ideas and the corresponding code, welcome interested developers to read this article 😋

concept

Bubble sort is the algorithm that repeats this operation by comparing the size of the two adjacent numbers from the far right of the sequence and then switching the positions of the two numbers according to the result.

The characteristics of

  • Compare the size of two adjacent digits starting at the end of the sequence
  • If the compared data is smaller than the adjacent data on the left, the current compared data is moved left.
  • When the position of the current comparison data is equal to the current comparison times, the round ends.
  • After a round is compared, if the current round is not equal to the length of the sequence, the comparison continues from the end.

The illustration example

Put the following numbers in descending order, as shown in the figure.

  • Compare the size of two adjacent digits starting at the end of the data
  • After comparison, it is found that 6 is less than 7, so the position is changed.
  • When done, compare 6 with the adjacent number 4, 6>4, so no position is swapped
  • When done, compare 4 with the adjacent number 8, 4<8, so switch places
  • Repeat the comparison until the currently compared value is at the far left of the data.
  • Swap numbers over and over until the number currently being compared reaches the far left, and there is no adjacent data to compare, and the smallest number in the sequence moves to the far left.
  • Continue the next round of sorting, comparing from the end of the data until you reach the second position in the data.
  • When compared to the second position to the left of the data, the second smallest number in the sequence reaches the specified position.
  • Repeat until the position of the current comparison number is the number of current comparisons, that is, the sorting is complete.

Implementation approach

  • Declares a function that takes an array
  • The number of initialization comparison rounds is 1
  • Iterate over the array
  • Gets the index of the current comparison value in the array in the loop: array length – number of current loops
  • Gets the index of the adjacent value to the left of the current comparison value in the array in the loop: Array length – (number of current loops +2)
  • After the subscript is obtained, the current comparison value and the value adjacent to it to the left are obtained respectively
  • Determines whether the array subscript of the current comparison value is equal to the current number of rounds
  • The number of rounds increases by 1 if it is equal, and the loop continues if the current number of rounds is not equal to the array length
  • If not, the current value is compared to the adjacent value on the left, and if the current value is less than the adjacent value on the left, the position is swapped
  • If the current number of rounds equals the length of the array, the loop ends and the sorted array is returned.

Next, we use JavaScript to implement bubble sort according to the implementation idea.

const bubbleSort = function (arr) {
    // The number of rounds to compare
    let round = 1;
    for (let i = 0; i < arr.length; i++){// The current position of the comparison value = array length - number of current loops (I starts at 0, so +1 is required)
        const compareIndex = arr.length-(i+1);
        // Position of adjacent value to the left of current comparison value = array length - (number of current loops +2)
        const leftNeighborIndex = arr.length-(i+2);
        // Get the current comparison value
        const compareVal = arr[compareIndex];
        // Get the adjacent left value
        const leftNeighborVal = typeofarr[leftNeighborIndex] ! = ="undefined"? arr[leftNeighborIndex]:"";
        // If the current position of the comparison value is equal to the number of rounds (since the number of rounds starts at 1 and the array subscript starts at 0, -1 is required), the round ends
        if(compareIndex===round- 1) {console.log(The first `${round}Round ends:${arr}, a total of more${i}Time `);
            // The number of rounds is increased
            round ++;
            // If the current number of rounds is not equal to the array length, the loop continues
            if(round! ==arr.length){ i =- 1; }}else{
            // Compare the size of the current value with the adjacent value on the left
            if(compareVal<leftNeighborVal){
                // Switch positions using structure assignment. [array[index1],array[index2]] = [array[index2],array[index1]][arr[compareIndex],arr[leftNeighborIndex]] = [arr[leftNeighborIndex],arr[compareIndex]]; }}}return arr;
};

// Declare an out-of-order
const dataArr = [5.8.2.7.9.1.10.0];
// Call the function
console.log(bubbleSort(dataArr));
Copy the code

The execution result

Comparison of double-layer and single-layer bubbling

Originally to my single layer bubble very confident, think I write the single layer efficiency must be higher than the double layer efficiency, the result slap slap face, I took my write and the double layer loop on the console again, only to find that I write is rubbish.

Why is single-layer inefficient

When I wondered why MY productivity was slow, my friend gave me the conclusion that, well, I was too bad.

Write in the last

  • The pictures used in this article are from “my first algorithm book”, if infringement, please leave a message in the comment section, the author immediately delete the relevant pictures.
  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌