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)