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

Thuật toán Sắp Xếp Nhanh ra đời từ năm 1960, do Tony Hoare phát triển. Ông tìm cách tối ưu hóa quá trình sắp xếp dữ liệu, sử dụng phương pháp chia để trị. Ý tưởng đơn giản: chọn một phần tử làm pivot, phân chia mảng thành hai phần. Từ đó, nó trở thành một trong những thuật toán sắp xếp hiệu quả nhất, được ứng dụng rộng rãi trong lập trình và khoa học máy tính.

Định Nghĩa

Bạn có thể hình dung Sắp Xếp Nhanh (Quick Sort) như một quy trình phân chia và chinh phục (divide and conquer). Nó chọn một giá trị trong mảng, gọi là “giá trị chốt” (pivot), và sau đó chia mảng thành hai phần dựa trên giá trị này.

Cách làm của Sắp Xếp Nhanh rất tinh tế. Khi chọn một giá trị chốt, nó so sánh từng phần tử còn lại với giá trị này. Những giá trị nhỏ hơn sẽ được đưa về bên trái, và những giá trị lớn hơn sẽ được đưa về bên phải.

Sau khi sắp xếp các giá trị xung quanh giá trị chốt, thuật toán này sẽ tái lặp quy trình với từng phần mảng bên trái chốt và bên phải chốt. Chính nhờ sự phân chia liên tục này mà mảng sẽ dần được sắp xếp hoàn chỉnh.

Điều đặc biệt là Sắp Xếp Nhanh hoạt động trực tiếp trên mảng ban đầu, không cần thêm bộ nhớ, và chính điều này giúp nó trở nên nổi bật so với các thuật toán khác.

Cách Thức

Bước đầu tiên là chọn một giá trị chốt. Bạn có thể chọn giá trị này theo nhiều cách, ví dụ chọn phần tử ở giữa, phần tử đầu tiên hoặc cuối cùng. Mục đích chỉ là chọn một giá trị đại diện cho cả mảng.

Tiếp theo, bạn sẽ chia mảng thành hai phần: những giá trị nhỏ hơn giá trị chốt sẽ được đưa về bên trái, và những giá trị lớn hơn sẽ được đưa về bên phải. Quá trình này tạo ra một sự phân chia rõ ràng trong mảng.

Sau khi chia xong, giá trị chốt được đặt vào vị trí chính xác của nó trong mảng. Lúc này, giá trị chốt sẽ ở vị trí mà nó sẽ nằm khi mảng được sắp xếp hoàn toàn.

Cuối cùng, thuật toán sẽ tiếp tục tái lặp quy trình trên hai phần mảng còn lại (bên trái và bên phải của giá trị chốt) cho đến khi mọi phần tử đều ở đúng vị trí.

Để 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

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ột mảng chứa các giá trị cần sắp xếp.
• Một hàm quickSort tự gọi lại chính nó (đệ quy) nếu mảng con có kích thước lớn hơn 1.
• Một hàm partition nhận vào một mảng con, di chuyển các giá trị xung quanh, hoán đổi phần tử chốt vào trong mảng con và trả về chỉ số nơi diễn ra lần chia mảng tiếp theo.

Mã TypeScript sẽ như sau:

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

// Hàm quickSort thực hiện sắp xếp mảng sử dụng thuật toán Quicksort
function quickSort(nums: number[], left: number = 0, right: number = nums.length - 1): number[] {
  // Nếu left < right, tức là mảng con có kích thước lớn hơn 1
  if (left < right) {
    // Tìm chỉ số của pivot sau khi phân chia mảng
    const pivotIndex = partition(nums, left, right);

    // Đệ quy sắp xếp mảng con bên trái của pivot
    quickSort(nums, left, pivotIndex - 1);
    // Đệ quy sắp xếp mảng con 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 thực hiện phân chia mảng và trả về vị trí của pivot
function partition(nums: number[], left: number, right: number): number {
  // Chọn phần tử cuối cùng của mảng con làm pivot
  const pivot = nums[right];

  // Đặt chỉ số i để theo dõi vị trí sẽ hoán đổi phần tử nhỏ hơn pivot
  let i = left - 1;

  // Lặp qua các phần tử trong mảng con
  for (let j = left; j < right; j++) {
    // Nếu phần tử tại vị trí j nhỏ hơn hoặc bằng pivot
    if (nums[j] <= pivot) {
      // Tăng chỉ số i lên
      i++;

      // Nếu i và j không trùng nhau, hoán đổi các phần tử tại i và j
      if (i !== j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    }
  }

  // Xác định vị trí mới cho pivot
  const pivotIndex = i + 1;

  // Nếu vị trí pivotIndex khác right, hoán đổi pivot vào đúng vị trí
  if (pivotIndex !== right) {
    [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];
  }

  // Trả về vị trí của pivot để tiếp tục phân chia mảng
  return pivotIndex;
}

Deno.test('test', () => {
  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

Về thời gian thực thi, Sắp Xếp Nhanh có độ phức tạp trung bình là O(n log n), bởi vì với mỗi lần phân chia, kích thước mảng bị giảm xuống một nửa. Điều này khiến thuật toán chạy hiệu quả với nhiều dữ liệu.

Tuy nhiên, trong trường hợp tệ nhất, khi các phần tử đã gần như sắp xếp sẵn hoặc nếu chọn pivot không tốt, độ phức tạp có thể lên đến O(n^2). Đây là lý do tại sao việc chọn pivot một cách thông minh là rất quan trọng.

Về bộ nhớ, Sắp Xếp Nhanh hoạt động tốt vì nó không yêu cầu bộ nhớ bổ sung cho mỗi lần sắp xếp mà thực hiện “in-place”, sử dụng chính mảng đầu vào để xử lý, do đó độ phức tạp không gian là O(log n).

Điều này có nghĩa là Sắp Xếp Nhanh lý tưởng khi bạn có mảng lớn và bộ nhớ hạn chế. Nó vừa hiệu quả, vừa tiết kiệm tài nguyên.

Toàn Cảnh

Sắp Xếp Nhanh là một phần của nhóm các thuật toán sắp xếp dựa trên phân chia và chinh phục, giống như Sắp Xếp Trộn. Tuy nhiên, Sắp Xếp Nhanh thường nhanh hơn trong thực tế vì nó không yêu cầu tạo ra các mảng bổ sung.

Trong ngữ cảnh rộng hơn, thuật toán này là một trong những giải pháp tối ưu khi bạn cần xử lý các tập dữ liệu lớn mà vẫn đảm bảo hiệu suất. Thường thì Sắp Xếp Nhanh là sự lựa chọn ưu tiên trong nhiều ngôn ngữ lập trình.

Sự phổ biến của nó còn nhờ vào tính chất “in-place” - không tiêu tốn nhiều bộ nhớ phụ, đặc biệt là khi cần sắp xếp trên các máy tính có tài nguyên hạn chế.

Vì vậy, hiểu rõ cách Sắp Xếp Nhanh vận hành và khi nào nên áp dụng là một kỹ năng quý giá cho lập trình viên.

Ứng Dụng

Sắp Xếp Nhanh không chỉ hữu ích cho việc sắp xếp dữ liệu trong lập trình. Nó còn được sử dụng trong các hệ thống xử lý dữ liệu lớn và hệ thống cơ sở dữ liệu, nơi hiệu suất là ưu tiên hàng đầu.

Một ví dụ thực tế là khi bạn tìm kiếm nhanh trên Google. Các thuật toán sắp xếp như Sắp Xếp Nhanh đóng vai trò trong việc sắp xếp và tìm kiếm thông tin một cách nhanh chóng và chính xác.

Trong thương mại điện tử, Sắp Xếp Nhanh giúp sắp xếp các sản phẩm theo giá, đánh giá hoặc xếp hạng để người dùng dễ dàng tìm thấy sản phẩm mong muốn.

Nó còn xuất hiện trong phân tích dữ liệu lớn, nơi các tập dữ liệu khổng lồ cần được sắp xếp để phục vụ việc ra quyết định nhanh chóng và chính xác.

Hiểu Lầm

Một hiểu lầm phổ biến về Sắp Xếp Nhanh là nó luôn nhanh nhất. Thực tế, với mảng đã sắp xếp hoặc gần như sắp xếp, Sắp Xếp Nhanh có thể hoạt động chậm hơn vì phải thực hiện nhiều phép so sánh hơn.

Nhiều người nghĩ rằng cách chọn pivot không quan trọng, nhưng thực tế việc chọn pivot thông minh (như chọn ngẫu nhiên hoặc lấy trung vị) có thể làm tăng hiệu quả của thuật toán rất nhiều.

Cũng có ý kiến cho rằng Sắp Xếp Nhanh phù hợp với mọi trường hợp sắp xếp, nhưng nếu bạn có nhiều giá trị trùng lặp, các thuật toán khác như Sắp Xếp Trộn hoặc Sắp Xếp Vun Đống có thể sẽ tốt hơn.

Cuối cùng, Sắp Xếp Nhanh không phải là lựa chọn tối ưu cho tất cả các mảng, đặc biệt là khi mảng có kích thước nhỏ.

Tóm Tắt

Sắp Xếp Nhanh là một thuật toán dựa trên nguyên lý phân chia và chinh phục, sử dụng giá trị chốt để chia mảng thành các phần nhỏ hơn, giúp sắp xếp dữ liệu nhanh và hiệu quả.

Nó thường có độ phức tạp thời gian trung bình là O(n log n) và không yêu cầu nhiều bộ nhớ, nên là lựa chọn tốt cho các tập dữ liệu lớn.

Ứng dụng của Sắp Xếp Nhanh rất rộng, từ xử lý dữ liệu lớn, thương mại điện tử, đến công nghệ tìm kiếm và trí tuệ nhân tạo.

Tuy nhiên, để tối ưu hóa Sắp Xếp Nhanh, bạn cần hiểu cách chọn pivot thông minh và áp dụng nó đúng tình huống - không phải mọi tập dữ liệu đều phù hợp với Sắp Xếp Nhanh.

Nguồn: Viễn Đinh - Cách Giải Sắp Xếp Nhanh