Bubble Sort
Bubble Sort is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name because smaller elements slowly “float” to the top of the list through swapping.
The idea of bubble sort is a bit like when the teacher sorted the height of the students by the height of the class. When the height of the students is similar, the teacher will row them together and compare them. If the former is higher than the latter, they will swap their positions and then compare them backwards.
First compare the front 1,2 students, the former is higher than the latter, swap positions
Then compare the second and third students, the former is not higher than the latter, do not do the operation
And so on
When the first round of comparison is over, we can be sure that the highest student will be placed in the last position.
Each round of comparison can determine a position of the top students, so as long as we again for the rest of the former four students to go round the comparison, we can determine the five students in the second high classmates location to the penultimate (that is, the final location), then we in turn three, before the round compared two each. You can get the sorting result.
Algorithm description
- Compare adjacent elements. If the first one is larger 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, so that the last element should be the largest;
- Repeat for all elements except the last one;
- Repeat steps 1 to 3 until the sorting is complete.
Time complexity (average) | Time complexity (worst) | Time complexity (best) | Time complexity | The stability of |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n) | O(1) | stable |
We can see the sorting process in detail in the figure below
Code implementation
function bubbleSort(arr) {
let len = arr.length;
for(let i = len-1; i > 0; i--) { // I Controls the array range for the current round comparison to be 0-len-1 for the first round, 0-len-2 for the second round, and....
for(let j = 0; j < i; j++) {
if(arr[j] > arr[j+1]) { // Compare adjacent elements in pairs
var temp = arr[j+1]; // Element swap
arr[j+1] = arr[j]; arr[j] = temp; }}}return arr;
}
Copy the code
let arr = [3.44.38.5.47.15.36.26.27.2.46.4.19.50.48]
arr = bubbleSort(arr)
console.log(arr) / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the code