K[vtt] <-> K[j];
return j; //trả về vị trí đúng của chốt
}
Phân tích giải thuật
Gọi T(n) là thời gian thực hiện giải thuật ứng với 1 khoá,
P(n) là thời gian để phân đoạn 1 mảng n khoá thành 2 mảng con, ta có:
T(n) = P(n) + T(j-t) + T(p-j)
Ta thấy P(n) = Cn = O(n)
- Trường hợp xấu nhất: Dãy đã được sắp xếp sẵn
-> Sau khi phân đoạn thì 1 trong 2 mảng là rỗng (j = t hoặc j = p)
Giả sử j = t ta có:
Tx(n) = P(n) + Tx(0) + Tx(n-1)
= C(n) + Tx(n-1)
= C(n) + C(n-1) + Tx(n-2)....
= Tổng từ 1 đến n của Cn + Tx(0)
= C(n.(n+1)/2) = O(n^2)
-> Vậy với trường hợp xấu nhất thì Quicksort
không hơn gì các phương pháp sắp xếp đơn giản
- Trường hợp tốt nhất là khi dãy khoá tiếp tục được chia đều làm 2 nửa
Tt(n) = P(n) + 2*Tt(n/2)= Cn + 2*C(n/2) + 2^2*Tt(n/4)
.....
= log2(n)*Cn + 2^(log2(n)) * Tt(1) = log2(n)*Cn + n*Tt(1)
= O(nlog2n)
13. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp vun đống (Heap Sort).Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử.
HEAP_SORT(){
//vòng for sau đây sẽ tạo thành đống cho cây ban đầu
//và tất cả các cây con của nó
for(int i = (n-1)/2; i >=0; i--){
ADJUST(i, n);
}
for(int i = n-1; i >= 0; i--){
K[0] <-> K[i];
ADJUST(0, i);
}
}
ADJUST(int root, int n){
/*
Giải thuật này thực hiện việc chỉnh sửa 1 cây
thành ĐỐNG với điều kiện rằng 2 cây con của cây
Chia sẻ với bạn bè của bạn: |
