Time complexity analysis of bubble sorting

1. Unoptimized bubble sort

• Inner loop ： Because the array subscript involves i+1, So the maximum is length-2, In addition, every time the external circulation is completed , The elements to be processed in the array will be reduced by one , Therefore, the maximum value of internal circulation is ：length -1- k

   /** *  Analysis of comparison times ： * int[]  There are elements  n individual  * i = 0 -->  All in all n Pending elements   A total comparison n-1 Time  * i = 1 -->  All in all n-1 Pending elements   A total comparison n-2 Time  * i = 2 -->  All in all n-2 Pending elements   A total comparison n-3 Time  * ...... * i = n-3 -->  All in all 3 Pending elements   A total comparison 2 Time  * i = n-2 -->  All in all 2 Pending elements   A total comparison 1 Time  * *  Add the above comparison times to get   Total number of comparisons ： * (n-1)+(n-2)+(n-3)+ ... +3+2+1 = (1+(n-1))*(n-1)/2 = n*(n-1)/2 = (n^2 -n)/2 */
    public static void mppx(int[] oldArr){
    
        if (oldArr.length > 1){
    
            for (int k = 0; k < oldArr.length; k++) {
     //  Outer loop 
                for (int i = 0; i < oldArr.length -1-k; i++) {
     //  Inner loop 
                    if (oldArr[i]>oldArr[i+1]){
    
                        int max = oldArr[i];
                        oldArr[i] = oldArr[i+1];
                        oldArr[i+1] = max;
                    }
                }
            }
        }
    }

2. Bubble sorting after optimization

• External circulation optimization ：n Elements Actually, it only needs to be completed n-1 Great wheel
• If the first big round （ Outer loop ） Come down , If there is no exchange , Then the elements in the array are ordered , So we can optimize the algorithm

public static void mppx(int[] oldArr){
    
        if (oldArr.length > 1){
    
            int k,i,max,
                    flag=1,//  be used for   It is the judgment of ordered array flag： If there is no element exchange after the first round of outer loop , That proves that the array is ordered 
                    //moveCount = 0,//  Record the number of exchanges 
                    len = oldArr.length ;
            for ( k = 0; k < len-1; k++) {
     //  Outer loop ： Loop through every element in the array ,n Elements   Actually, it only needs to be completed n-1 round 
                for ( i = 0; i < len-1-k; i++) {
     //  Inner loop ：  Used to compare and exchange with other elements 
                    if (oldArr[i] > oldArr[i+1]){
    
                        max = oldArr[i];
                        oldArr[i] = oldArr[i+1];
                        oldArr[i+1] = max;
                        flag = 0;
                        moveCount++;
                    }
                }
                //  The first round comes down , If there is no exchange , The elements in the array are ordered 
                if (flag==1){
    
                    //System.out.println("k = " + k + "： The elements in an array are ordered ");
                    break;
                }
            }
            //System.out.println("moveCount = " + moveCount);
        }
    }

3. Best case analysis （ The elements in the array are ordered ）

• Bubble sorting algorithm is optimized （ pivotal flag）

Array	Compare and move times
123	Compare 2 Time In exchange for 0 Time
1234	Compare 3 Time In exchange for 0 Time
12345	Compare 4 Time In exchange for 0 Time
123456	Compare 5 Time In exchange for 0 Time
…	…
n An ordered element	Compare n-1 Time In exchange for 0 Time

• therefore Bubble sorted The optimal time complexity is ： O(n)

4. Worst case analysis （ The elements in the array are completely in reverse order ）

• Hypothetical array 2 The process of exchanging element values is an operation

Original array + Moving process	Comparison and exchange times
21： 12	2 Elements == Compare 1 Time In exchange for 1 Time
321： 231->213->123	3 Elements == Compare (1+2) Time In exchange for (1+2) Time
4321: 3421->3241->3214->2314->2134->1234	4 Elements == Compare (1+2+3) Time In exchange for (1+2+3) Time
54321: 45321->43521->43251->43215->34215->32415->32145->23145->21345->12345	5 Elements == Compare (1+2+3+4) Time In exchange for (1+2+3+4) Time
654321：	6 Elements == Compare (1+2+3+4+5) Time In exchange for (1+2+3+4+5) Time
…	…
n Elements in reverse order	n Elements == Compare (1+2+3+4+5+…+ n-1) Time In exchange for (1+2+3+4+5+…+ n-1) Time
n Elements in reverse order	n Elements == Compare (n-1)*n/2 Time In exchange for (n-1)*n/2 Time

• therefore Bubble sorted The worst time complexity is ：(n-1)*n/2 + (n-1)*n/2 = n^2 -n Ignore the lower power and get O(n^2)

5. Stability of bubble sorting algorithm

• If two adjacent elements are equal , No swap operation will occur , So bubbling doesn't change the subscript of the same element , So bubble sort is a stable sort algorithm .