I. Định nghĩa thuật toán sắp xếp nhanh Quick sort

So với thuật toán sắp xếp nổi bọt (bubble sort), thuật toán sắp xếp nhanh có tốc độ nhanh hơn. Thay vì sắp xếp từng cặp phần tử như bubble sort, chúng ta chia dữ liệu thành hai danh sách, sau đó so sánh từng phần tử trong danh sách với một phần tử được chọn làm "phần tử chốt". Mục tiêu của chúng ta là đặt phần tử chốt vào vị trí đúng của nó.

II. Miêu tả thuật toán sắp xếp nhanh Quick sort

Chắc hẳn bạn vẫn còn khá mông lung với thuật toán, để giúp bạn hiểu rõ hơn, chúng ta hãy cùng đến với một trò chơi "hành quân" sau:

Xét một dãy số như sau:

6,1,2,7,9,3,4,5,10,8

Yêu cầu là sắp xếp dãy trên theo thứ tự không giảm từ trái qua phải.

Chọn phần tử chốt là số 6, ta sẽ xét hai "quân lính" là quân lính A và quân lính B đặt ở hai đầu của dãy số (quân A ở vị trí đầu tiên bên trái, quân B ở vị trí cuối cùng bên phải). Luật hành quân như sau: quân B đi trước, bắt đầu di chuyển về bên trái và dừng lại khi gặp phần tử có giá trị nhỏ hơn giá trị của phần tử chốt, ở đây quân B dừng lại ở vị trí số 5. Tiếp theo là lượt của quân A, quân A di chuyển về bên phải và dừng lại khi gặp phần tử có giá trị lớn hơn giá trị của phần tử chốt, ở đây quân A dừng lại ở vị trí số 7. Lúc này ta đổi chỗ hai số ở vị trí của quân A và quân B, sau đó hai quân A và B trở về vị trí ban đầu, ta thu được dãy số sau:

6, 1, 2, 5, 9, 3, 4, 7, 10, 8

Tiếp tục quá trình hành quân như trên, lượt này ta cần đổi chỗ hai số 4 và 9 cho nhau, ta được dãy số:

6, 1, 2, 5, 4, 3, 9, 7, 10, 8

Đến lượt hành quân tiếp theo, quân B dừng lại ở vị trí số 3, nhưng quân A chưa tìm được số nào lớn hơn 6 đã gặp phải quân B. Vì vậy, lượt hành quân này coi là thất bại và ta đổi chỗ số 3 với phần tử chốt là số 6. Ta thu được:

3, 1, 2, 5, 4, 6, 9, 7, 10, 8

Lúc này, chúng ta quan sát phần tử chốt (số 6): sau loạt hành quân đầu tiên, tất cả các phần tử nằm bên trái phần tử chốt đều nhỏ hơn nó, và tất cả các phần tử nằm bên phải phần tử chốt đều lớn hơn nó. Như vậy, ta đã đặt số 6 vào đúng vị trí của nó.

Tiếp theo, dãy được chia thành hai dãy nhỏ hơn là dãy bên trái số 6 và dãy bên phải số 6. Ta tiếp tục thực hiện luật hành quân như trên đối với hai dãy này và sẽ thu được các phần tử chốt khác ở đúng vị trí và xuất hiện các dãy con có độ dài ngắn hơn. Tiếp tục quá trình cho đến khi hoàn thành, ta sẽ thu được dãy có thứ tự như mong muốn.

III. Thuật toán sắp xếp nhanh Quick sort tham khảo

• Thuật toán sắp xếp nhanh C++: