    
a
  
   

Chia  tr
Phân hoch
Phân tích trng hp xu nht
Phân hoch ngu nhiên
Phân tích
a
 xut bi C.A.R. Hoare, 1962
Da trên kthut Chia –  – Tr
Hiu qutrong thc t(tinh chnh)
a
Sp xp nhanh mng -phn ttng dn:
Chia: phân hoch mng thành 2 mng con da
trên phn tchtsao cho các phn tthuc
mng con bên trái ≤ và các phn tthuc
mng con bên phi≥
Tr: áp dng  quy sp xp 2 mng con
Gp: hin nhiên
Lu ý: phân hoch vi thi gian tuyn tính
!  " #$ 
Partition  
cht
for to do
if ≤ then


return
Duy trì