9) Trình bày giải thuật sắp xếp nhanh (QuickSort)? Trình bày thời gian thực hiện giải thuật với dãy n phần tử. Minh họa diễn biến ở từng bước khi áp dụng giải thuật này với dãy số: 24, 42, 74, 11, 65, 58, 83, 36, 88, 99
Bài làm:
Procedure Quick_Sort(a, vt_dau, vt_cuoi);
Kt:= True;
If vt_cuoi > vt_dau then
Begin
i:= vt_dau + 1;
j:= vt_cuoi - 1;
x:= a[vt_dau];
While kt do
While a[i] < x and I =< vt_cuoi do i:= i+1;
While a[i] > x and j > vt_dau do j:= j+1;
If j>i then
Begin
y := a[j];
a[j] := a[i];
a[i] := y;
End;
Else
Begin
Kt := False;
y := a[vt_dau];
a[vt_dau] := a[j];
a[j] := y;
Quick_Sort(a, vt_dau, j – 1);
Quick_Sort(a, j + 1, vt_cuoi);
End;
End;
Return;
Thời gian thực hiện giải thuật:
Gọi T(n) là thời gian thực hiện giải thuật với dãy n phần tử
P(n) là thời gian để phân chia dãy n phần tử thành 2 đoạn
=> T(n) = P(n) + T(j – vt_dau) + T(vt_cuoi – j)
= C.n + …
Giả sử: Sau mỗi bước dãy được chia làm 2 phần bằng nhau
=> T(n) = C.n + 2.T(n/2)
= C.n + 2 C.n/2 + 4.T(n/4)
= …
= C.n + 2 C.n/2 + 4 C.n/4 + 2log2n C(n/2log2n) T(1)
= C.n + C.n + … + C.n
T(1) = 1 khi thực hiện đến bước thứ log2n
Có log2n phần tử C.n
T(n) = C.n log2n = O(nlog2n)
