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

Ý tưởng

Ý tưởng chúng ta sẽ chia mảng lớn thành những mảng con nhỏ hơn bằng cách chia đôi mảng lớn và chúng ta tiếp tục chia đôi các mảng con cho tới khi mảng con nhỏ nhất chỉ còn 1 phần tử. Sau đó chúng ta sẽ tiếng hành so sánh 2 mảng con có cùng mảng cơ sở (khi chúng ta chia đôi mảng lớn thành 2 mảng con thì mảng lớn đó chúng ta gọi là mảng cơ sở của 2 mảng con đó) khi so sánh chúng sẽ vừa sắp xếp vừa ghép 2 mảng con đó lại thành mảng cơ sở, chúng ta tiếp tục so sánh và ghép các mảng con lại đến khi còn lại mảng duy nhất thì đó là mảng đã được sắp xếp.

Ảnh minh họa

 

Các công thức cần thiết

Quy tắc tổng quát để phân tích 1 chương trình

• Thời gian của lệnh gán, read, write là O(1)
• Thời gian thi hành của một chuỗi lệnh được xác định bằng qui tắc cộng. Như vậy thời gian thi hành này bằng với thời gian thi hành một lệnh lâu nhất trong chuỗi lệnh
• Thời gian thi hành của lệnh IF là thời gian thi hành lớn nhất trong điều kiện IF hoặc sau ELSE
• Thời gian thực hiện vòng lập là tổng thời gian thực hiện thân vòng lập. Nếu thời gian thực hiện thân vòng lập không đổi thì thời gian thực hiện vòng lập bằng tích thời gian thân vòng lập với số lần lập.

Công thức tính tổng tổng quát

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