Giải thuật sắp xếp nhanh (Quick Sort)
Sắp xếp nhanh (Quick Sort) là gì?
Giải thuật sắp xếp nhanh (Quick Sort) là một giải thuật hiệu quả cao và dựa trên việc chia mảng dữa liệu thành các mảng nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được chọn gọi là phần tử chốt (Pivot): một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và mảng còn lại bao gồm các phần tử lớn hơn hoặc bằng phần tử chốt.
Tiến trình chia này diễn ra tiếp tục cho tới khi độ dài của các mảng con đều bằng 1. Giải thuật sắp xếp nhanh tỏ ra khá hiệu quả với các tập dữ liệu lớn khi mà độ phức tạp trường hợp trung bình và trường hợp xấu nhất là O(nlogn) với n là số phần tử.
Kỹ thuật chọn phần tử chốt trong giải thuật sắp xếp nhanh (Quick Sort)
Kỹ thuật chọn phần tử chốt ảnh hưởng khá nhiều đến khả năng rơi vào các vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử chốt (pivot) nằm ở trung vị của danh sách. Khi đó, sau log2(n) lần chia chúng ta sẽ đạt tới kích thước các mảng con bằng 1.
Dưới đây là các cách chọn phần tử chốt:
Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
Chọn phần tử đứng giữa danh sách làm phần tử chốt.
Chọn phần tử trung vị trong ba phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.
Chọn phần tử ngẫu nhiên làm phần tử chốt. Tuy nhiên cách này rất dễ dẫn đến khả năng rơi vào các trường hợp đặc biệt.
Minh họa cách chia trong giải thuật sắp xếp nhanh (Quick Sort)
Hình minh họa dưới đây minh họa cách tìm phần tử chốt trong mảng. Ở đây, chúng ta chọn phần tử chốt đứng ở cuối danh sách.
Phần tử chốt chia danh sách thành hai phần. Và sử dụng đệ qui, chúng ta tìm phần tử chốt cho các mảng con cho tới khi danh sách chỉ còn một phần tử.
Giải thuật phần tử chốt trong sắp xếp nhanh (Quick Sort)
Dựa vào cách chia danh sách trong giải thuật sắp xếp nhanh ở trên, chúng ta có thể viết một giải thuật như dưới đây.
Bước 1: Chọn phần tử chốt là phần tử có chỉ mục cao nhất (phần tử ở cuối danh sách) Bước 2: Khai báo hai biến để trỏ tới bên trái và bên phải của danh sách, ngoại trừ phần tử chốt Bước 3: Biến bên trái trỏ tới mảng con bên trái Bước 4: Biến bên phải trỏ tới mảng con bên phải Bước 5: Khi giá trị tại biến bên trái là nhỏ hơn phần tử chốt thì di chuyển sang phải Bước 6: Khi giá trị tại biến bên phải là lớn hơn phần tử chốt thì di chuyển sang trái Bước 7: Nếu không trong trường hợp cả bước 5 và bước 6 thì tráo đổi giá trị biến trái và phải Bước 8: Nếu left ≥ right, thì đây chính là giá trị chốt mới
Giải thuật phần tử chốt mẫu trong sắp xếp nhanh (Quick Sort)
Từ các bước trên, chúng ta có thể suy ra code mẫu cho giải thuật sắp xếp nhanh (Quick Sort) như sau:
Bắt đầu hàm partitionFunc(left, right, pivot) leftPointer = left -1 rightPointer = right while True thực hiện while A[++leftPointer] < pivot thực hiện //không làm điều gì kết thúc while while rightPointer > 0 && A[--rightPointer] > pivot thực hiện //không làm điều gì kết thúc while if leftPointer >= rightPointer break else Tráo đổi leftPointer,rightPointer kết thúc if kết thúc while Tráo đổi leftPointer,right return leftPointer Kết thúc hàm
Giải thuật sắp xếp nhanh (Quick Sort)
Sử dụng giải thuật phần tử chốt một cách đệ qui, chúng ta có thể kết thúc với các mảng con nhỏ hơn. Sau đó mỗi mảng con này có thể được xử lý với sắp xếp nhanh. Dưới đây, mình sử dụng giải thuật đệ qui cho sắp xếp nhanh:
Bước 1: Lấy phần tử chốt là phần tử ở cuối danh sách Bước 2: Chia mảng bởi sử dụng phần tử chốt Bước 3: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái Bước 4: Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải
Giải thuật mẫu cho Sắp xếp nhanh (Quick Sort)
Từ phần giải thuật trên, chúng ta có thể suy ra code mẫu cho giải thuật sử dụng đệ qui cho sắp xếp nhanh như sau:
Bắt đầu hàm quickSort(left, right) if right-left <= 0 return else pivot = A[right] partition = partitionFunc(left, right, pivot) quickSort(left,partition-1) quickSort(partition+1,right) kết thúc if Kết thúc hàm
Theo Tutorialspoint
Bài trước: Shell Sort trong cấu trúc dữ liệu và giải thuật
Bài tiếp: Cấu trúc dữ liệu đồ thị (Graph)
Bạn nên đọc
-
Công thức tính thể tích khối tròn xoay và ví dụ minh họa
-
Công thức tính diện tích hình bình hành, chu vi hình bình hành
-
Công thức tính diện tích hình chóp
-
Công thức tính diện tích xung quanh hình nón cụt, diện tích toàn phần hình nón cụt, thể tích hình nón cụt
-
Công thức tính diện tích hình hộp chữ nhật
-
Công thức tính diện tích hình quạt tròn
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:


Cũ vẫn chất
-
Mệnh đề HAVING trong SQL Server
Hôm qua -
Hàm SUM trong SQL Server
Hôm qua -
Hướng dẫn toàn tập Word 2016 (Phần 28): Cách trộn văn bản, trộn thư Mail Merge
Hôm qua -
Xoay sở hay xoay xở mới đúng chính tả? Có đến 90% người dùng bị sai
Hôm qua -
Căn chỉnh - Align trong CSS
Hôm qua -
Hướng dẫn toàn tập Word 2016 (Phần 27): Cách sử dụng Style
Hôm qua -
5 phần mềm VPN miễn phí tốt nhất cho PC
Hôm qua -
Che trở hay che chở đúng chính tả?
Hôm qua -
Cách sửa lỗi "We Couldn't Create a New Partition" trong Windows 10
Hôm qua -
Làm việc với File trong Python
Hôm qua