Giải thuật sắp xếp Bubble Sort

Giải thuật

Phương pháp này sẽ duyệt mảng nhiều lần, mỗi lần duyệt sẽ so sánh cập giá trị thứ i và [i + 1] và đổi chỗ cho nhau nếu chúng không đúng thứ tự.

Code mẫu

public void BubbleSort(int[] array){
        int temp = 0;                           //{1}
        int n = array.length;                   //{2}
        for (int i = 0; i < n - 1; i++) {       //{3}
            for (int j = n - 1; j > i;j--) {    //{4}
                if (array[j - 1] > array[j]){   //{5}
                    temp = array[j];            //{6}
                    array[j] = array[j - 1];    //{7}
                    array[j - 1] = temp;        //{8}
                }
            }
        }

        Log.i("OKE", "BubbleSort: "+ Arrays.toString(array));
    }

 

Tính độ phức tạp

Ta thấy, {1}, {2} và {5},{6},{7},{8} điều là những lệnh gán nên áp dụng quy tắc tổng quát thì bằng O(1).

Lệnh {4} được lồng trong lệnh {3}, vậy thời gian thực hiện của chương trình cũng chính bằng thời gian thực hiện của lệnh {3} theo tổng quát.

Giải

Vòng lập {3} sẽ chạy [n – 2] lần, mỗi chạy sẽ gọi vòng lập {4} [n – 1 – i] lần. Suy ra được công thức:

Chú ý: Công thức tổng quát tính tổng tại đây