Optimized version of bubble sort, performance nearly doubled

The original bubble sort is relatively time-consuming. Even if an array has become ordered after several rounds of exchanges, for example, the array [2,1,3,4,5,6,7], after the first One round has become orderly, but the stubborn bubbling still has to continue the unnutritious pairwise comparison, thus sacrificing time.

If you use a flag to determine whether the current array is in order, exit the loop if it is in order, which can significantly improve the performance of bubble sort~

Since the time complexity of bubble sort is O(n* n) So when there is more data, it becomes slower and is very unsuitable for sorting big data, so we also used a random array with a length of 800 when testing.

The code is as follows:

package go.derek;
import java.util.*;
public class Sort {
//Bubble sort
public void bubbleSort(int[] arr){
for(int i=0; i for(int j=arr.length-1;j>i;j--){
if(arr[j] int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
}
}
}
//Improved version of bubble sort
public void bubbleSort_plus(int[] arr){
boolean flag=true;
for(int i=0;i flag=false;
for(int j=arr.length-1 ;j>i;j--){
if(arr[j] flag=true;
int tmp=arr[j];
arr[j]=arr[j -1];
arr[j-1]=tmp;
}
}
}
}
public static void main(String[] args){
Sort s=new Sort();
int[] arr1=new int[800];
for(int i=0;i arr1[i]=new Random().nextInt(800)+1;
}
int[] arr2=new int [800];
for(int i=0;i arr2[i]=new Random().nextInt(800)+1;
}
long n=System.currentTimeMillis() ;
s.bubbleSort_plus(arr1);
long m=System.currentTimeMillis();
System.out.println("Bubble sorting time: "+(m-n)+"ms");
long a=System. currentTimeMillis();
s.bubbleSort_plus(arr2);
long b=System.currentTimeMillis();
System.out.println("Time consuming after optimization: "+(b-a)+"ms");
}
}

After running it multiple times, we found the most obvious result:

Bubble sorting time: 12ms
After optimization, time: 4ms

You can see the importance of this flag~

More bubbling Sorting optimized version, the performance is almost doubled. For related articles, please pay attention to the PHP Chinese website!