Quick Sort Phương pháp sắp xếp hiệu quả trong JavaScript

Quick Sort là một thuật toán sắp xếp hiệu quả sử dụng phương pháp chia để trị. Ý tưởng chính là chọn một phần tử làm "pivot", sau đó phân chia mảng thành hai phần sao cho các phần tử nhỏ hơn "pivot" nằm ở bên trái và các phần tử lớn hơn "pivot" nằm ở bên phải. Tiếp tục thực hiện đệ quy trên hai phần này cho đến khi toàn bộ mảng được sắp xếp.

Dưới đây là cách triển khai Quick Sort trong JavaScript:

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    let pivot = arr[Math.floor(arr.length / 2)];
    let left = [];
    let right = [];

    for (let i = 0; i < arr.length; i++) {
        if (i === Math.floor(arr.length / 2)) continue; // Bỏ qua phần tử pivot
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}

// Ví dụ sử dụng:
let array = [38, 27, 43, 3, 9, 82, 10];
console.log("Mảng ban đầu: " + array);
let sortedArray = quickSort(array);
console.log("Mảng sau khi sắp xếp: " + sortedArray);

Giải thích:

1. Hàm quickSort:

   • Nếu mảng có độ dài nhỏ hơn hoặc bằng 1, trả về chính mảng đó (vì nó đã được sắp xếp).
   • Chọn phần tử "pivot" ở giữa mảng.
   • Khởi tạo hai mảng left và right để lưu trữ các phần tử nhỏ hơn và lớn hơn "pivot".
   • Duyệt qua các phần tử trong mảng, so sánh từng phần tử với "pivot" và đẩy chúng vào mảng left hoặc right tương ứng.
   • Thực hiện đệ quy quickSort trên mảng left và right, sau đó kết hợp chúng lại với "pivot".

2. Dòng if (i === Math.floor(arr.length / 2)) continue;:

   • Bỏ qua phần tử "pivot" khi duyệt qua mảng.

3. Trả về kết quả:

   • Sử dụng toán tử spread để kết hợp kết quả của việc đệ quy trên left và right với "pivot" ở giữa.

Thời gian và không gian:

• Thời gian:
  • Trung bình và tốt nhất: O(n log n) vì mỗi lần chia mảng thành hai phần.
  • Xấu nhất: O(n^2) nếu mảng đã được sắp xếp hoặc có nhiều phần tử trùng lặp (có thể tránh bằng cách chọn pivot một cách thông minh hơn, chẳng hạn chọn pivot ngẫu nhiên hoặc "median-of-three").
• Không gian:
  • O(log n) cho trung bình và tốt nhất do sử dụng đệ quy (stack space).
  • O(n) cho xấu nhất khi mảng đã được sắp xếp hoặc có nhiều phần tử trùng lặp.

Quick Sort là một trong những thuật toán sắp xếp nhanh nhất cho các mảng lớn và không yêu cầu thêm bộ nhớ như Merge Sort. Tuy nhiên, cần cẩn thận với trường hợp xấu nhất và có thể tối ưu bằng cách chọn pivot thông minh.