1 [Hướng dẫn]Thuật toán sắp xếp phân đoạn Tue May 31, 2011 9:41 pm
Admin
Quản trị viên
Bài toán:
Khi đầu bài cho dãy X1, X2, ..., Xn yêu cầu sắp xếp các phần tử theo thứ tự.
Nếu yêu cầu sắp xếp không tăng → phải hiểu là sau khi sắp xếp xong X'1 ≥ X'2 ≥ X'3 ≥... ≥ X'n
Nếu yêu cầu sắp xếp không giảm → phải hiểu là sau khi sắp xếp
xong X'1 ≤ X'2 ≤ X'3 ≤... ≥ X'n
trong đó X'i là X mới.
Giải quyết bài toán theo phương pháp sắp xếp theo phân đoạn.
[You must be registered and logged in to see this link.]
* Phân tích:
- Chọn một khoá ngẫu nhiên làm chốt. Mọi phần tử nhỏ hơn giá trị của chốt được xếp vào vị trí trước chốt, mọi phần tử lớn hơn chốt được xếp vào sau chốt.
- So sánh các phần tử trong dãy với chốt, đổi vị trí cho nhau nếu lớn hơn chốt mà nằm trước chốt và nhỏ hơn chốt mà nằm sau chốt.
- Khi việc đổi chỗ thực hiện xong thì dãy khoá phân làm 2 đoạn.
+ Một đoạn gồm các khoá nhỏ hơn chốt.
+ Một đoạn gồm các khoá lớn hơn chốt
+Khoá chốt ở giữa 2 đoạn cũng là vị trí thực của nó.
- Quá trình lặp lại với 2 đoạn nhỏ, đén khi gặp 1 đoạn chỉ gồm 2 phần tử.
* Ví dụ:
* Giải thuật sắp xếp:
Proc Quick_sort (l, k: chỉ số trên dưới)
1. temp ; Xk; i = l; j = k;
2. while i <= j do
a. while (i ≤ j) & Xi ≤ temp do i ++
b. while (i ≤ j) & Xj ≥ temp do j--
c. if i < j then Đổi chỗ (Xi, Xj)
3. Đổi chỗ (Xk, Xj)
4. Quick_sort (l, j - 1);
Quick_sort ( j+1, k)
End
Ở đây phần 4 gọi đệ quy 2 lần khác nhau. Cần học và nắm rõ thuật sắp xếp này.
Khi đầu bài cho dãy X1, X2, ..., Xn yêu cầu sắp xếp các phần tử theo thứ tự.
Nếu yêu cầu sắp xếp không tăng → phải hiểu là sau khi sắp xếp xong X'1 ≥ X'2 ≥ X'3 ≥... ≥ X'n
Nếu yêu cầu sắp xếp không giảm → phải hiểu là sau khi sắp xếp
xong X'1 ≤ X'2 ≤ X'3 ≤... ≥ X'n
trong đó X'i là X mới.
Giải quyết bài toán theo phương pháp sắp xếp theo phân đoạn.
[You must be registered and logged in to see this link.]
* Phân tích:
- Chọn một khoá ngẫu nhiên làm chốt. Mọi phần tử nhỏ hơn giá trị của chốt được xếp vào vị trí trước chốt, mọi phần tử lớn hơn chốt được xếp vào sau chốt.
- So sánh các phần tử trong dãy với chốt, đổi vị trí cho nhau nếu lớn hơn chốt mà nằm trước chốt và nhỏ hơn chốt mà nằm sau chốt.
- Khi việc đổi chỗ thực hiện xong thì dãy khoá phân làm 2 đoạn.
+ Một đoạn gồm các khoá nhỏ hơn chốt.
+ Một đoạn gồm các khoá lớn hơn chốt
+Khoá chốt ở giữa 2 đoạn cũng là vị trí thực của nó.
- Quá trình lặp lại với 2 đoạn nhỏ, đén khi gặp 1 đoạn chỉ gồm 2 phần tử.
* Ví dụ:
* Giải thuật sắp xếp:
Proc Quick_sort (l, k: chỉ số trên dưới)
1. temp ; Xk; i = l; j = k;
2. while i <= j do
a. while (i ≤ j) & Xi ≤ temp do i ++
b. while (i ≤ j) & Xj ≥ temp do j--
c. if i < j then Đổi chỗ (Xi, Xj)
3. Đổi chỗ (Xk, Xj)
4. Quick_sort (l, j - 1);
Quick_sort ( j+1, k)
End
Ở đây phần 4 gọi đệ quy 2 lần khác nhau. Cần học và nắm rõ thuật sắp xếp này.