Three ways to implement bubble sorting

Bubble sorting is very easy to understand and implement, and use the example of sorting from small to large:

Suppose the array length is N.

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

2. In this way, after traversing the 0th data of the array to N-1 data, the largest data is "sinked" 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 will be completed.

It's easy to write code by definition:

Copy the codeThe code is as follows:

//Bubblestone 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]);
}

The following is to optimize it and set a flag, which is true if there is an exchange in this trip, otherwise it is false. Obviously, if there is no exchange in one trip, it means that the sorting has been completed.

Copy the codeThe code is as follows:

//Bubblestone 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--;
       }
}

Make further optimizations. If there is an array of 100 numbers, only the first 10 are out of order, and the next 90 are all sorted and are all larger than the first 10 numbers, then after the first traversal, the final exchange position must be less than 10, and the data after this position must be ordered. Record this position, and the second time you just traverse from the head of the array to this position.

Copy the codeThe code is as follows:

//Bubbling sort 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 an inefficient sorting method after all, and can be used when the data scale is very small. When the data scale is relatively large, it is best to use other sorting methods.