Quick Sort - “Chia Để Trị” Trong Sắp Xếp
Quick Sort là một thuật toán sắp xếp “nhanh như chớp” và cực kỳ hiệu quả. Nó là một trong những thuật toán được sử dụng rộng rãi nhất hiện nay, đặc biệt là trong các ứng dụng cần xử lý lượng dữ liệu lớn. Quick Sort dựa trên nguyên tắc “chia để trị” (divide and conquer) - một chiến lược mạnh mẽ giúp giải quyết vấn đề phức tạp bằng cách chia nhỏ nó thành các bài toán con đơn giản hơn, xử lý từng bài toán con, rồi tổng hợp lại để có kết quả cuối cùng.
Quick Sort Hoạt Động Như Thế Nào?
Cơ bản, Quick Sort hoạt động như sau:
- Chọn “Chốt” (Pivot): Đầu tiên, thuật toán chọn một phần tử trong mảng làm “chốt” (pivot).
- Phân Vùng (Partition): Tiếp theo, các phần tử còn lại trong mảng sẽ được phân thành hai nhóm:
- Nhóm 1: Gồm các phần tử nhỏ hơn pivot.
- Nhóm 2: Gồm các phần tử lớn hơn hoặc bằng pivot.
- Đệ Quy (Recursion): Thuật toán sẽ lặp lại quá trình trên (chọn pivot và phân vùng) cho từng nhóm (nhóm 1 và nhóm 2) một cách đệ quy, cho đến khi mỗi nhóm chỉ còn một phần tử hoặc không còn phần tử nào. Khi đó, mảng đã được sắp xếp.
Triển Khai Quick Sort Bằng JavaScript
Để hiểu rõ hơn, hãy cùng xem cách triển khai Quick Sort bằng JavaScript:
function quickSort(arr) {
if (arr.length <= 1) {
return arr; // Nếu mảng chỉ có 0 hoặc 1 phần tử thì nó đã được sắp xếp
}
const pivot = arr[arr.length - 1]; // Chọn phần tử cuối cùng làm pivot (có thể chọn phần tử khác)
const left = []; // Mảng con chứa các phần tử nhỏ hơn pivot
const right = []; // Mảng con chứa các phần tử lớn hơn hoặc bằng pivot
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// Đệ quy sắp xếp hai mảng con và ghép lại với pivot ở giữa
return [...quickSort(left), pivot, ...quickSort(right)];
}
// Kiểm tra
const array = [7, 2, 1, 6, 8, 5, 3, 4];
const sortedArray = quickSort(array);
console.log(sortedArray); // Kết quả: [1, 2, 3, 4, 5, 6, 7, 8]
Giải thích code:
- Hàm quickSort(arr) nhận vào một mảng arr cần sắp xếp.
- Nếu mảng chỉ có 0 hoặc 1 phần tử, nó đã được sắp xếp, nên trả về luôn.
- Chọn phần tử cuối cùng của mảng làm pivot.
- Tạo hai mảng con left và right để chứa các phần tử nhỏ hơn và lớn hơn hoặc bằng pivot.
- Dùng vòng for để duyệt qua các phần tử của mảng (trừ pivot), và đưa chúng vào left hoặc right tương ứng.
- Đệ quy gọi lại hàm quickSort cho left và right, sau đó ghép kết quả lại với pivot ở giữa, sử dụng cú pháp spread …
- Điều Chỉnh và Ứng Dụng
Với cách triển khai trên, bạn đã có thể sắp xếp các mảng số nguyên theo thứ tự tăng dần. Tuy nhiên, bạn hoàn toàn có thể điều chỉnh code để sắp xếp giảm dần, hoặc sắp xếp các đối tượng dựa trên một thuộc tính nào đó.
Kết:
Quick Sort là một công cụ mạnh mẽ mà bất kỳ lập trình viên nào cũng nên biết. Với độ phức tạp trung bình là O(n log n), Quick Sort rất phù hợp cho các ứng dụng xử lý dữ liệu lớn. Hy vọng bài viết này đã giúp bạn hiểu rõ hơn về thuật toán Quick Sort và cách triển khai nó trong JavaScript. Hãy thử áp dụng nó vào các dự án của bạn và tối ưu hóa hiệu suất sắp xếp nhé!
P/S: Bạn cũng có thể luyện tập với Javascript Quick Sort solution :<