Detailed explanation of bubble sorting method

Bubble sorting method

HTML5 Academy-Coder: This issue continues to introduce the algorithm - bubble sorting method. The bubble sort algorithm is relatively simple, easy to use, and relatively stable. It is a relatively easy-to-understand algorithm and one of the algorithms that interviewers frequently ask questions about.

Tips: The basic knowledge of "algorithm" and "sorting" has been explained in detail in the previous "Selection Sorting Method". You can click on the relevant article link at the end of the article to view it, and I will not repeat it here.

Principle of Bubble Sorting

Basic Principle

Traverse from the head of the sequence, compare them two by two, if the former is larger than the latter, swap positions until the end Swap the largest number (the largest number in this sorting) to the end of the unordered sequence, thereby becoming part of the ordered sequence;

During the next traversal, the maximum number after each previous traversal will no longer participate. Sorting;

Repeat this operation multiple times until the sequence sorting is completed.

Because in the sorting process, decimals are always placed forward and large numbers are placed backward, similar to bubbles gradually floating upward, so it is called bubble sorting.

Principle Illustration

Tips: Blue represents waiting for exchange in a round of sorting, black represents exchange completed in this round of sorting, red represents sorting completed

Decomposition of steps to achieve bubbling

Use a for loop to determine the number of sorting

Since the sequence to be sorted can already be determined when there is only one number left, there is no need Sort, therefore, the number of sorting is sequence length – 1.

Control the number of comparisons for each sorting

Every time you sort, multiple numbers in the sequence must be compared in pairs, and multiple comparisons are required Use the for statement to achieve this. This for loop is nested in the for loop of sorted times (forming a nest of double for).

Tips: j needs to be set to less than len - i - 1. The reason for subtracting i is that the sorted numbers no longer participate in the comparison. The reason for subtracting 1 is that the array Index values ​​start from 0.

Core function - compare pairs and exchange positions according to the situation

Compare the size of the two numbers. If the former is larger than the latter, exchange the values, that is, exchange the positions.

Full code of bubble sorting method

Optimization of bubble sorting method

If the sequence The data is: [0, 1, 2, 3, 4, 5];

Use the above bubble sorting method to sort, and the result will definitely be fine, but the sequence to be sorted is in order Yes, theoretically there is no need to traverse sorting.

The current algorithm will perform traversal sorting regardless of whether the initial sequence is in order, and the efficiency will be relatively low, so the current sorting algorithm needs to be optimized.

In the following algorithm, a swap variable is introduced and initialized to false before each sorting; if two numbers exchange positions, set it to true.

At the end of each sorting, determine whether swap is false. If so, it means that the sequence has been sorted or the sequence itself is an ordered sequence, and the next sorting will not be performed.

Through this method, unnecessary comparisons and position exchanges are reduced, and the performance of the algorithm is further improved.

Efficiency of bubble sorting method

Time complexity

The best state: the sequence to be sorted itself is an ordered sequence, According to the optimized code, it can be concluded that the number of sorting is n-1 times, and the time complexity is O(n);

Worst case scenario: the sequence to be sorted is in reverse order, and 1 needs to be sorted at this time + 2 +3...(n - 1) = n(n - 1)/2 times

The time complexity is O(n^2).

Space complexity

The bubble sort method requires an extra space (temp variable) to exchange the position of elements, so the space complexity is O(1).

Stability of the algorithm

When adjacent elements are equal, there is no need to exchange positions, and the order of the same elements will not change. Therefore, it is a stable sorting.

What is O? !

Time complexity, more accurately, describes the time growth curve of an algorithm as the size of the problem continues to increase. Therefore, these orders of magnitude increase are not an accurate performance evaluation and can be understood as an approximation. (Similar to space complexity)

O(n?) means that when n is large enough, the complexity is approximately equal to Cn?, C is a certain constant. Simply put, when n is large enough, then As n grows linearly the complexity will grow squarely.

O(n) means that when n is very large, the complexity is approximately equal to Cn, and C is a certain constant. In short: as n grows linearly, the complexity grows along a linear scale.

O(1) means that when n is very large, the complexity basically does not increase. In short: as n grows linearly, the complexity is not affected by n and grows along a constant level (the constant here is 1).

Tips: In the picture, O(1) is close to the X-axis and cannot be seen clearly.

Tips: This picture comes from the "Stack Overflow" website.

Related article links

Selection sorting method

Happy every day

Life is hard and coding is not easy, but don’t forget to smile!

The above is the detailed content of Detailed explanation of bubble sorting method. For more information, please follow other related articles on the PHP Chinese website!