Viễn Đinh

Viễn Đinh

Khá Hơn 0,5% Mỗi Ngày

Cách Giải Sắp Xếp Nhanh (Quick Sort), Dể Hiểu

Sắp Xếp Nhanh, là một trong những thuật toán sắp xếp hiệu quả nhất, được phát triển bởi nhà khoa học máy tính Tony Hoare vào năm 1959. Thuật toán này sử dụng phương pháp chia để trị để sắp xếp các phần tử trong một mảng.

Định Nghĩa

Sắp Xếp Nhanh (Quick Sort) là một thuật toán phân chia và chinh phục. Nghĩa là nó chia nhỏ vấn đề lớn (sắp xếp một mảng lớn) thành các vấn đề nhỏ hơn (sắp xếp từng phần của mảng), rồi kết hợp lại để hoàn tất. Bằng cách chọn một phần tử làm “chốt” (pivot), nó chia mảng thành hai phần: một phần có các giá trị nhỏ hơn chốt, phần kia lớn hơn.

Đến đây, có lẽ bạn đã hình dung được. Sau khi đã chia, thuật toán lặp lại quá trình này cho từng phần của mảng cho đến khi mọi phần đều được sắp xếp. Cứ thế, tất cả phần tử của mảng sẽ được đưa vào đúng vị trí, tạo nên một mảng hoàn toàn sắp xếp.

Cái hay của Sắp Xếp Nhanh là tốc độ và tính linh hoạt. Nó không cần thêm nhiều bộ nhớ như một số thuật toán khác và hoạt động nhanh hơn trong nhiều tình huống. Sự phân chia chính là chìa khóa ở đây—khi chia càng nhiều, mảng sẽ càng gần với thứ tự mà ta mong muốn.

Cuối cùng, điều quan trọng là Sắp Xếp Nhanh hoạt động một cách rất hiệu quả trong thực tế, dù có thể mất nhiều bước hơn nếu bạn chọn chốt không tốt. Nhưng khi đã chọn đúng, thời gian thực hiện của nó sẽ rất ngắn.

Để dể hình dung hơn, bạn có thể xem diễn họa của thuật toán Sắp Xếp Nhanh tại đây: https://youtu.be/WprjBK0p6rw

Bản Chất

Đầu tiên, bạn cần chọn một phần tử làm chốt. Thường thì sẽ lấy phần tử ở giữa hoặc đầu mảng, nhưng việc chọn chốt có thể linh động tùy từng trường hợp. Điều này là bước đầu tiên để tạo nên sự phân chia trong mảng.

Tiếp theo, bạn duyệt qua các phần tử còn lại, so sánh chúng với chốt. Phần tử nào nhỏ hơn chốt thì chuyển về bên trái, lớn hơn thì chuyển sang bên phải. Vậy là bạn đã có hai phần mảng mới: một bên nhỏ hơn chốt, bên còn lại lớn hơn.

Sau khi đã phân chia, bạn lặp lại quá trình với từng phần mảng đã chia. Mỗi phần lại tiếp tục được chọn chốt và chia tiếp. Quy trình cứ thế diễn ra cho đến khi mỗi phần của mảng chỉ còn một phần tử hoặc trống hoàn toàn.

Kết quả cuối cùng là một mảng đã được sắp xếp từ đầu đến cuối. Sắp Xếp Nhanh hoạt động nhờ việc chia để trị, tận dụng sự phân chia để tạo trật tự dần dần.

Triển Khai

Để viết một hàm quickSort nhằm chia mảng thành các mảng con nhỏ hơn và nhỏ hơn nữa, ta sử dụng đệ quy. Điều này có nghĩa là hàm quickSort phải tự gọi lại chính nó với các mảng con nằm bên trái và bên phải của phần tử chốt (pivot).

Để triển khai thuật toán Quicksort trong một ngôn ngữ lập trình, chúng ta cần:

Mã TypeScript sẽ như sau:

import { expect } from 'jsr:@std/expect';

function quickSort(nums: number[], left: number = 0, right: number = nums.length - 1): number[] {
  // Kiểm tra điều kiện dừng của đệ quy: nếu left >= right, đoạn này đã sắp xếp xong
  if (left < right) {
    // Phân đoạn mảng và tìm vị trí của pivot
    const pivotIndex = partition(nums, left, right);

    // Sắp xếp phần bên trái của pivot
    quickSort(nums, left, pivotIndex - 1);

    // Sắp xếp phần bên phải của pivot
    quickSort(nums, pivotIndex + 1, right);
  }

  // Trả về mảng đã sắp xếp
  return nums;
}

// Hàm partition chọn một phần tử làm pivot và sắp xếp các phần tử xung quanh nó
function partition(nums: number[], left: number, right: number): number {
  // Chọn phần tử cuối cùng trong đoạn làm pivot
  const pivot = nums[right];

  // Khởi tạo chỉ số i để đánh dấu vị trí phần tử cuối cùng <= pivot
  let i = left - 1;

  // Duyệt qua các phần tử từ left đến right - 1 để sắp xếp quanh pivot
  for (let j = left; j < right; j++) {
    // Nếu phần tử hiện tại nhỏ hơn hoặc bằng pivot, hoán đổi nó về vị trí "nhỏ hơn pivot"
    if (nums[j] <= pivot) {
      // Tăng chỉ số i để mở rộng vùng các phần tử nhỏ hơn hoặc bằng pivot
      i++;

      // Hoán đổi phần tử tại nums[i] và nums[j] để đảm bảo các phần tử nhỏ hơn pivot nằm bên trái
      if (j !== i) {
        [nums[j], nums[i]] = [nums[i], nums[j]];
      }
    }
  }

  // Đưa pivot về vị trí chính xác (i + 1) bằng cách hoán đổi với phần tử tại nums[right]
  if (i + 1 !== right) {
    [nums[right], nums[i + 1]] = [nums[i + 1], nums[right]];
  }

  // Trả về vị trí cuối cùng của pivot sau khi đã phân chia mảng
  return i + 1;
}

Deno.test('standard array', () => {
  const input = [3, 15, 7, 1, 12, 19, 5, 8, 2, 10];
  const output = input.toSorted((a, b) => a - b);
  expect(quickSort(input)).toStrictEqual(output);
});

Big O

Nói về độ phức tạp, Sắp Xếp Nhanh thường đạt hiệu suất rất tốt, ở mức O(n log n) trong trường hợp trung bình. Điều này nhờ vào cách nó chia mảng thành các phần nhỏ hơn mỗi lần phân chia.

Độ phức tạp thời gian của Sắp Xếp Nhanh.
Độ phức tạp thời gian của Sắp Xếp Nhanh.

Tuy nhiên, có một nhược điểm khi chốt được chọn không lý tưởng (chẳng hạn, luôn chọn phần tử lớn nhất hoặc nhỏ nhất của mảng). Trong trường hợp này, Sắp Xếp Nhanh có thể trở nên chậm, đạt O(n²), vì sẽ mất nhiều lần phân chia hơn.

Bất kể vậy, ngay cả khi xấu nhất, Sắp Xếp Nhanh vẫn thường nhanh hơn các thuật toán sắp xếp đơn giản hơn như Sắp Xếp Chèn hoặc Sắp Xếp Chọn trong hầu hết các trường hợp thực tế.

Điểm đáng lưu ý là Sắp Xếp Nhanh không yêu cầu bộ nhớ phụ như một số thuật toán khác, làm cho nó rất thích hợp khi bạn cần tiết kiệm tài nguyên bộ nhớ.

Toàn Cảnh

Trong bối cảnh lớn hơn, Sắp Xếp Nhanh thuộc về nhóm thuật toán sắp xếp dựa trên so sánh, giống như Sắp Xếp ChènSắp Xếp Chọn. Nhưng so với chúng, Sắp Xếp Nhanh linh hoạt và tối ưu hơn nhiều trong đa số các trường hợp.

Thuật toán này được ứng dụng rộng rãi trong các hệ thống đòi hỏi tốc độ xử lý cao, từ cơ sở dữ liệu đến hệ thống phân tích dữ liệu. Sự phân chia thông minh giúp nó xử lý khối lượng dữ liệu khổng lồ một cách nhanh chóng.

Khi kết hợp với các thuật toán khác, Sắp Xếp Nhanh có thể tăng cường hiệu quả cho hệ thống. Ví dụ, khi kết hợp với thuật toán Sắp Xếp Trộn, bạn có thể xử lý các trường hợp ngoại lệ mà một thuật toán đơn lẻ khó tối ưu được.

Nhờ sự phổ biến và hiệu suất, Sắp Xếp Nhanh là công cụ quan trọng cho các lập trình viên và kỹ sư dữ liệu trong nhiều lĩnh vực.

Ứng Dụng

Giả sử bạn có một danh sách sản phẩm trên trang web, bạn muốn sắp xếp chúng theo giá để khách hàng có trải nghiệm dễ dàng hơn. Sắp Xếp Nhanh có thể giúp bạn sắp xếp các sản phẩm một cách nhanh chóng.

Trong hệ thống ngân hàng, sắp xếp giao dịch tài chính theo thời gian hoặc giá trị là một ứng dụng khác của Sắp Xếp Nhanh. Nó giúp tổ chức dữ liệu rõ ràng và hiệu quả.

Trong máy học, dữ liệu thường cần được sắp xếp trước khi áp dụng các thuật toán phân tích. Sắp Xếp Nhanh có thể giúp chuẩn bị dữ liệu với tốc độ cao.

Còn trong các trò chơi điện tử, các thuật toán sắp xếp như Sắp Xếp Nhanh được dùng để tối ưu thứ tự các sự kiện hoặc tính điểm.

Hiểu Lầm

Một hiểu lầm phổ biến về Sắp Xếp Nhanh là tưởng nó luôn nhanh hơn các thuật toán khác. Thực tế là khi chọn chốt không tối ưu, thuật toán có thể trở nên kém hiệu quả.

Một nhược điểm khác là khi mảng đã gần như sắp xếp, Sắp Xếp Nhanh có thể không hoạt động tốt. Trong trường hợp đó, thuật toán Merge Sort có thể là một lựa chọn tốt hơn.

Có người nghĩ Sắp Xếp Nhanh luôn đòi hỏi nhiều bộ nhớ. Sự thật là nó tiêu thụ bộ nhớ thấp hơn so với nhiều thuật toán khác nhờ không cần mảng phụ.

Cuối cùng, nếu không hiểu rõ về cách chọn chốt, người mới dễ chọn sai và làm chậm quá trình sắp xếp.

Tóm Tắt

Sắp Xếp Nhanh là một trong những thuật toán sắp xếp nhanh nhất và hiệu quả nhất, với sức mạnh từ sự phân chia và tinh gọn.

Bằng cách chia nhỏ mảng và sắp xếp từng phần, nó tạo nên một mảng hoàn chỉnh trong thời gian ngắn. Đây là một minh chứng cho việc đơn giản hóa vấn đề phức tạp.

Khi chọn chốt đúng, thuật toán sẽ đạt tốc độ tối ưu, nhưng nếu chọn sai, nó có thể chậm hơn. Việc hiểu rõ bản chất của thuật toán giúp bạn linh hoạt và sáng tạo hơn khi áp dụng nó.

Cuối cùng, Sắp Xếp Nhanh không chỉ là một công cụ sắp xếp mà còn là một ví dụ về sức mạnh của tư duy chia để trị trong lập trình và giải quyết vấn đề.