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.

không có đk If như của thầy thì trường hợp 1 pt k=L thì đệ quy thế nào?

Bản quyền mô phỏng của Khoa học Máy tính
Computer Science
Faculty of Information Technology - Hanoi National University of Education

Nếu bạn không thấy mô phỏng hiện ra, nghĩa là máy bạn chưa cài java. Bạn
phải thực hiện cài java vào máy bằng cách nhấn vào đường link sau:
[You must be registered and logged in to see this link.]
Sau đó cứ việc nháy OK để java cài vào máy.

Tất cả các trang mô phỏng cơ sở, sẽ được viết theo dạng java cho nó nhẹ, nên bạn hãy cài java để xem nhé!

Hiện tại tôi có thể hướng dẫn các bạn mô phỏng bằng Flash nhưng không có
thời gian nhiều. Chắc là nếu thi đỗ được, chúng ta sẽ làm lại toàn bộ
mô phỏng dạng này bằng flash cho đẹp.

Đường link tham khảo các bài viết bằng sử dụng Flash căn bản (nếu không
hiện tiếng Việt, xin chọn từ thựcđơn View, codepage ISO8859-1 (cái này
tôi viết lâu rồi, từ hồi chưa chuẩn hoá unicode):
[You must be registered and logged in to see this link.]

Nháy tham khảo: [You must be registered and logged in to see this link.]
Giáo trình sử dụng: [You must be registered and logged in to see this link.]

Chào Anh!
Anh có thể giải thích khi ta chọn phần tử chốt giữa a[r], a[l] và a[(l+r)/2] thì có gì khác nhau, tốt xấu như thế nào, trường hợp nào thì nên chọn vị trí chốt nào tương ứng ? cám ơn Anh!