Bubble sort algorithm is implemented in Java

Analysis and improvement of bubble sort algorithm

The basic idea of swap sort is to compare the keywords of the records to be sorted in pairs and swap them when they are found in opposite order until there are no records in reverse order.
The main sorting methods that apply the basic idea of exchange sort are bubble sort and quicksort.

 
public class BubbleSort implements SortUtil.Sort{ 
public void sort(int[] data) { 
int temp; 
for(int i=0;i<data.length;i++){ 
for(int j=data.length-1;j>i;j--){ 
if(data[j]<data[j-1]){ 
SortUtil.swap(data,j,j-1); 
} 
} 
} 
} 

Bubble sort

1. Sorting method

The sorted records array R[1..n] is arranged vertically, and each record R is considered as a bubble with the weight of r.ey. According to the principle that light bubbles cannot be below heavy bubbles, scan the array R from bottom to top: any light bubbles that violate this principle are scanned to "float" upward. And so on, until finally any two bubbles are light on the top and heavy on the bottom.

(1) initial

R[1..n] is the unordered region.

(2) the first scan

Compare the weight of the two adjacent bubbles from the bottom of the disordered area to the top. If the light one is found to be on the bottom and the heavy one on the top, switch the positions of the two. (R[n], R[n-1]), (R[n-1], R[n-2]),... (R[2], R[1]); For each pair of bubbles (R[j+1], R[j]), if R[j+1]. R[j]. Key, then exchange the contents of R[j+1] and R[j].
At the end of the first scan, the "lightest" bubble floats to the top of the interval, where the record of the smallest keyword is placed at the highest position, R[1].

(3) second scan

Scanning R [2.. n]. At the end of the scan, the "sub-light" bubbles float to R[2]...
Finally, after n-1 scan, the ordered region R[1..n] can be obtained.
Note: in the i-th scan, R[1..i-1] and R[I..n] are the current ordered and disordered regions, respectively. The scan continues from the bottom up to the top of the disordered area. At the end of the scan, the lightest bubbles in the region float to the top position R, resulting in R[1.. I] becoming a new ordered region.

2. Example of bubble sort process

The process of bubbling sort a file with a keyword sequence of 49, 38, 65, 97, 76, 13, 27, 49

3. Sorting algorithm

(1) analysis

Since each sequence adds a bubble to the ordered region, there will be n-1 bubbles in the ordered region after n-1 sorting, and the weight of bubbles in the disordered region is always greater than or equal to the weight of bubbles in the ordered region, so the whole bubble sorting process at most requires n-1 sorting.
If the exchange of bubble positions is not found in a sort, it indicates that all bubbles in the unordered area to be sorted satisfy the principle of light on top and heavy on bottom. Therefore, the bubble sort process can be terminated after this sort. To do this, in the algorithm given below, a Boolean exchange is introduced and set to FALSE before each sort. If an exchange occurs during the sort, set it to TRUE. At the end of each sort, check exchange. If no exchange has occurred, the algorithm will be terminated and the next sort will not be carried out.

(2) specific algorithm

void BubbleSort(SeqList R) 
{ //R (l.. N) is the file to be sorted, which is scanned from bottom to top to do bubble sort on R
int i . j ;  
Boolean exchange ;  //Exchange of mark
for(i=1;i<n;i++){ //N minus one sort at most
exchange=FALSE ;  //The swap flag should be false prior to the start of this sort
for(j=n-1;j>=i ; j--) //Scan the current unordered region R[I..n] from bottom to top
if(R[j+1].key<R[j].key){//Exchange record
R[0]=R[j+1] ;  //R[0] is not a sentry
R[j+1]=R[j] ;  
R[j]=R[0] ;  
exchange=TRUE ;  //The swap occurs, so the swap flag is set to true
} 
if(!exchange) //This sort does not exchange, terminate the algorithm in advance
return ;  
} //Endfor (outer loop)
} //BubbleSort 

4. Algorithm analysis

(1) the best time complexity of the algorithm
If the file's initial state is in positive order, a single scan completes the sorting. The required number of keyword comparison C and the number of record movement M both reach the minimum value:
Cmin = n - 1
Mmin = 0.
The best time complexity of bubble sort is O(n).
(2) the worst time complexity of the algorithm
If the original file is in reverse order, n-1 sort is required. N-i keyword comparisons (1 Or less I Or less n-1) are performed for each sequence, and records must be moved three times for each comparison. In this case, the number of comparisons and moves reaches the maximum:
Cmax = n (n - 1) / 2 = O (n2)
Mmax = 3 n (n - 1) / 2 = O (n2)
The worst time complexity of bubble sort is O(n2).
(3) the average time complexity of the algorithm is O(n2)
Although bubble sort does not have to make n-1 passes, its average time performance is much worse than that of direct insertion sort because of the number of record moves.
(4) algorithm stability
Bubble sort is sort in place, and it's stable.
5. Algorithm improvement
The bubble sort above can also be improved as follows:
(1) remember the bubble sort of lastExchange where the lastExchange occurred
In each scan, remember the location, lastExchange, where the lastExchange occurred (the adjacent records prior to that location are in order). At the beginning of the next sort, R[1.. lastexchang-1] is the ordered region, and R[lastExchange..n] is the unordered region. In this way, a single sort may cause the current ordered area to expand more than one record, thus reducing the number of sorts. Specific algorithm [see exercise].
(2) change the bubble sort of scanning direction
(1) the asymmetry of bubble sort
Can complete the sorting in one scan:
Only the lightest bubbles are in the R[n] position, and the rest are sorted, so it only takes one scan to complete the sorting.
Initial keyword sequence 12,18,42,44,45,67,94,10 requires only one scan.
N -1 scan is needed to complete the sorting:
When only the heaviest bubbles are in the position of R[1] and the rest are sorted, an n-1 scan is still needed to complete the sorting.
For the initial sequence of keywords: 94,10,12,18,42,44,45,67 required seven scans.
(2) causes of asymmetry
Each scan only makes the heaviest bubble "sink" one place, so n-1 scans are needed to make the heaviest bubble at the top sink to the bottom.
(3) ways to improve asymmetry
The asymmetry can be improved by changing the scanning direction alternately in the sorting process.
JAVA code:

package Utils.Sort;


public class BubbleSort implements SortStrategy
{
       
       public void sort(Comparable[] obj)
       {
              if (obj == null)
              {
                     throw new NullPointerException("The argument can not be null!");
              }

              Comparable tmp;

              for (int i = 0 ;i < obj.length ;i++ )
              {
                     //Remember, always start with the first one. The last one doesn't have to be compared.
                     for (int j = 0 ;j < obj.length - i - 1 ;j++ )
                     {
                            //The adjacent elements are compared, and if they are small, they are swapped
                            if (obj[j].compareTo(obj[j + 1]) > 0)
                            {
                                   tmp = obj[j];
                                   obj[j] = obj[j + 1];
                                   obj[j + 1] = tmp;
                            }
                     }
              }
       }
}