Quick Sort
ế
Ý t Gi ả
ự
ắ ầ a1, a2 ..., aN d a trên vi c ệ ầ
: ngưở i thu t QuickSort s p x p dãy ậ phân ho ch dãy ban đ u thành 3 ph n : ạ ầ ầ ầ
• Ph n 1: G m các ph n t ồ • Ph n 2: G m các ph n t ồ • Ph n 3: G m các ph n t ồ v i x là giá tr c a m t ph n t ị ủ ớ ệ
ộ Sau khi th c hi n phân ho ch, dãy ban đ u đ ầ c phân thành 3 ầ ử ầ ử ầ ử ầ ử ạ ơ x có giá tr bé h n ị x có giá tr b ng ị ằ có giá tr l n h n ơ x ị ớ tùy ý trong dãy ban đ u. ầ ượ ự
• 1. ak ≤ x , v i k = 1 .. j ớ • 2. ak = x , v i k = j+1 .. i-1 ớ • 3. ak ‡ x , v i k = i..N ớ Ak=x
đo n:ạ
Ak <=x Ak>=x
: đã có th t ạ ế ạ ứ ự
Đo n th 2 đã có th t ứ N u các đo n 1 và 3 ch có 1 ph n t à khi đó dãy con ban đ u đã đ c s p. ầ ử ượ ắ
. ứ ự ỉ ầ Ak=x Ak>=x
Ak <=x
. ứ ự
thì dãy ban đ u ch ạ ạ ế ầ ử ầ ỉ
ứ ự
t ti n hành vi c phân ng pháp phân ho ch dãy ban ừ ệ ạ
Đo n th 2 đã có th t ứ N u các đo n 1 và 3 có nhi u h n 1 ph n t ơ ề c s p. khi các đo n 1, 3 đ có th t ượ ắ ạ Đ s p x p các đo n 1 và 3, ta l n l ầ ượ ế ạ ế ể ắ ho ch t ng dãy con theo cùng ph ươ ạ đ u v a trình bày … ầ ừ
Ví Dụ
Cho dãy số a:
12 2 8
5
1
6
4
15
x = a[3] = 5
Phân hoạch đoạn l =0, r = 7:
12
2
8
5
1
6
4
15
l=0
r=7
Ví Dụ
4
2
8
5
1
6
12
15
i = 0
j = 6
l=0
r=7
4
2
8
5
1
6
12
15
i = 1
i = 2
l=0
r=7
j = 3
j = 5
j = 4
Quick Sort – Ví Dụ
Phân hoạch đoạn l = 0, r = 2:
4
2
1
5
8
6
12
15
l = 0
r =3
i = 0
j = 2
Ví Dụ
Phân hoạch đoạn l =4, r = 7:
1
2
4
5
8
6
12
15
r =7
l = 4 i = 4
j = 6
j = 6
j = 7
1
2
4
5
8
12
15
6 i = 4
r =7
l = 4
Ví Dụ
Phân hoạch đoạn l =6, r = 7:
1
2
4
5
6
8
12
15
Ví Dụ
Phân hoạch đọan [0,7]
i 0
1
2
4
5
6
3
j 7
5 5
12
2
8
1
6
4
15
X
right
left
Ví Dụ
Phân hoạch đọan [0,7]
X
5
i 1
2
3
4
j 5
0
6
7
2
8
5
1
6
4
12
15
right
left
Ví Dụ
Phân hoạch đọan [0,2]
1
j 2
3
i 4
5
0
6
7
2
1
5
8
6
4
12
15
right
left
Phân hoạch đọan [0,2]
1 j 2 i 0 3 4 5 6 7
2 2 1 4 5 8 6 12 15
X
right left
Ví Dụ
Phân hoạch đọan [4,7]
0
1
2
3
i 4
6
5
j 7
1
2
4
5
8
12
15
6 6
X
right
left
Ví Dụ
Phân hoạch đọan [5,7]
0
1
2
3
j 4
6
7
i 5
1
2
4
5
6
12
15
8
right
left
Ví Dụ
Phân hoạch đọan[5,7]
0 1 2 3 4 6 j 7 i 5
1 2 4 5 6 12 12 15 8
right left
Ví Dụ
0
1
2
3
4
5
6
7
1
2
4
5
6
8
12
15
Gi
i Thu t Quick Sort
ả
ậ
ầ ử
//dãy đã đ K t thúc; : N u ế left ≥ right //dãy có ít h n 2 ph n t ướ B c 1 ế ơ c s p x p ế
: Phân ho ch dãy ạ ượ ắ aleft … aright thành các đo n: ạ aleft..
ướ B c 2 aj, aj+1.. ai-1, ai.. aright
Đo n 1 ạ
Đo n 2ạ
Đo n 3: ạ
: S p x p đo n 1 ướ B c 3 ắ ế
£ x : aj+1.. ai-1 = x ai.. aright ‡ x ạ : aleft.. aj ạ : ai.. aright
: S p x p đo n 3 i Thu t Quick Sort
B c 4 ướ Gi ả
ắ ế ậ
: Ch n tùy ý m t ph n t a[k] trong dãy là giá tr m c ( l ầ ử ộ ọ ị ố
ướ B c 1 ≤ k ≤ r):
ướ B c 2 : Phát hi n và hi u ch nh c p ph n t ệ ầ ử ỉ
x = a[k]; i = l; j = r; ệ a[i], a[j] n m sai ch : ằ ặ ỗ
Swap(a[i],a[j]);
B c 2a ướ B c 2b ướ ướ B c 2c : N u i < j: ế c l Ng ượ ạ
i B c 2. ướ B c 3
: Trong khi (a[i]
Quick Sort Cài đ tặ void QuickSort(int a[], int left, int right) {
i, j, x;
int x = a[(left+right)/2]; i = left; j = right; do { while(a[i] < x) i++; while(a[j] > x) j--;
if(i <= j)
{
Swap(a[i],a[j]);
i++ ; j--; }
} while(i <= j);
if(left QuickSort(a, left, j); if(i } QuickSort(a, i, right);
