Three implementations of bubble sort

Bubble sorting is very easy to understand and implement, take sorting from small to large as an example:

Suppose the array length is N.

1. Compare the two adjacent data before and after. If the former data is greater than the latter data, the two data will be exchanged.

2. In this way, after traversing the 0th data to the N-1th data of the array, the largest data will "sink" to the N-1th position of the array.

3. N=N-1, if N is not 0, repeat the previous two steps, otherwise the sorting is completed.

It is easy to write the code by definition:

//冒泡排序1  
void BubbleSort1(int a[], int n)  
{  
       int i, j;  
       for (i = 0; i < n; i++)  
              for (j = 1; j < n - i; j++)  
                     if (a[j - 1] > a[j])  
                            Swap(a[j - 1], a[j]);  
}

Let’s optimize it and set a flag, which is true if an exchange occurs on this trip, otherwise it is false. Obviously, if there is no exchange in one trip, it means that the sorting has been completed.

//冒泡排序2  
void BubbleSort2(int a[], int n)  
{  
       int j, k;  
       bool flag;  
  
       k = n;  
       flag = true;  
       while (flag)  
       {  
              flag = false;  
              for (j = 1; j < k; j++)  
                     if (a[j - 1] > a[j])  
                     {  
                            Swap(a[j - 1], a[j]);  
                            flag = true;  
                     }  
              k--;  
       }  
}

Let’s do further optimization. If there is an array of 100 numbers, only the first 10 are unordered, and the next 90 are all sorted and all are greater than the first 10 numbers, then after the first traversal, the last position where the exchange occurs must be less than 10, and this The data after the position must be in order. Record this position. The second time you just need to traverse from the head of the array to this position.

//冒泡排序3  
void BubbleSort3(int a[], int n)  
{  
    int j, k;  
    int flag;  
      
    flag = n;  
    while (flag > 0)  
    {  
        k = flag;  
        flag = 0;  
        for (j = 1; j < k; j++)  
            if (a[j - 1] > a[j])  
            {  
                Swap(a[j - 1], a[j]);  
                flag = j;  
            }  
    }  
}

Bubble sorting is, after all, an inefficient sorting method and can be used when the data size is small. When the data size is relatively large, it is best to use other sorting methods.

For more articles related to the three implementations of bubble sorting, please pay attention to the PHP Chinese website!