Three implementation methods of bubble sort

Bubble sort is very easy to understand and implement, to sort from small to large for example:

Let's say the length of the array is N.

1. Compare two adjacent data before and after, if the former data is greater than the latter data, the two data exchange.

2. After traversing the array from the 0th data to the n-1st data, the largest data "sinks" to the n-1st position of the array.

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

It's easy to write code by definition:

//Bubble sort 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 next step in optimizing it is to set a flag that is true if the swap occurs, or false otherwise. Obviously if there's one pass that doesn't exchange, the sorting is done.

//Bubble sort 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 some more optimization. If 100 number of arrays, only 10 in front of the disorder, the 90 has been sorted and front are greater than 10 Numbers, so in the first time, after the traversal last exchange position must be less than 10, and after the position data must have been ordered, to record the location, the second time as long as from array traversal head to this position.

//Bubble 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 sort is, after all, an inefficient sorting method that can be used when the data size is small. When the data size is large, it is better to use other sorting methods.