bubble sort algorithm

The basic idea of ​​exchange sorting is: compare the keywords of the records to be sorted pairwise, and when it is found that the order of the two records is reversed, the exchange is performed until there are no records in the reverse order.

The main sorting methods that apply the basic idea of ​​exchange sort are: bubble sort and quick sort.

Bubble sort

1. Sorting method
Arrange the sorted record array R[1..n] vertically, and each record R[i] is regarded as a bubble with a weight of R[i].key. According to the principle that light bubbles cannot be under heavy bubbles, the array R is scanned from bottom to top: any light bubble that violates this principle will be "floated" upward. This is repeated until the last two bubbles are the lighter one at the top and the heavier one at the bottom.
(1) Initial
　 R[1..n] is an unordered area.

(2) The first scan
　 Compare the weights of two adjacent bubbles from the bottom of the disordered area upwards. If it is found that the lighter one is at the bottom and the heavier one is at the top, swap the positions of the two. That is, compare (R[n], R[n-1]), (R[n-1], R[n-2]),..., (R[2], R[1]) in sequence; for each pair Bubble (R[j+1], R[j]), if R[j+1].key When the first scan is completed, the "lightest" bubble floats to the top of the interval, that is, the record with the smallest keyword is placed at the highest position R[1].

(3) The second scan
　 Scan R[2..n]. When the scan is completed, the "second lightest" bubble floats to the position of R[2]...
Finally, after n-1 scans, the ordered area R[1..n] can be obtained
Note:
The ith scan When , R[1..i-1] and R[i..n] are the current ordered area and unordered area respectively. Scanning is still from the bottom of the disordered area upward to the top of the area. When the scan is completed, the lightest bubble in the area floats to the top position R[i], and the result is that R[1..i] becomes a new ordered area.

2. Example of bubble sorting process
 The process of bubble sorting the files with the keyword sequence 49 38 65 97 76 13 27 49

3. Sorting algorithm
(1) analysis
Because each sorting process uses A bubble is added to the ordered area. After n-1 sortings, there are n-1 bubbles in the ordered area, and the weight of the bubbles in the disordered area is always greater than or equal to the weight of the bubbles in the ordered area, so The entire bubble sort process requires at most n-1 sorting passes.
If no exchange of bubble positions is found in a certain sorting pass, it means that all the bubbles in the unordered area to be sorted satisfy the principle of the lighter ones at the top and the heavier ones at the bottom. Therefore, the bubble sorting process can be sorted in this pass. then terminate. To this end, in the algorithm given below, a Boolean exchange is introduced, and it is set to FALSE before each sorting starts. Set to TRUE if an exchange occurs during sorting. The exchange is checked at the end of each sorting pass. If no exchange has occurred, the algorithm is terminated and the next sorting pass is not performed.

(2) Specific algorithm
void BubbleSort(SeqList R)
{ //R (l..n) is the file to be sorted. Use bottom-up scanning to perform bubble sorting on R
int i, j;
Boolean exchange; //Exchange flag
for(i=1;i Exchange=FALSE; //Exchange flag should be false before this sorting starts
for (j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描
        if(R[j+1].key                                                                                                                                    . [j]=R[0];
                                                                                                                                                                                                                        . D} // endfor (outer cycle)}} // bubblesort

For more bubbling sorting algorithms related articles, please follow PHP Chinese website!