Cách Giải Sắp Xếp Phân Phối (Counting Sort), Dể Hiểu

Thuật toán Sắp Xếp Phân Phối có nguồn gốc từ một bài báo của Harold H. Seward vào năm 1921, trong đó ông mô tả một “máy phân loại thẻ” sử dụng phương pháp này để sắp xếp thẻ đục lỗ. Đến những năm 1930, R. A. Fisher và Frank Yates đã phát triển một thuật toán tương tự để đếm và sắp xếp mẫu trong các nghiên cứu sinh thái, góp phần vào sự phát triển của thuật toán này trong lĩnh vực khoa học máy tính.

Định Nghĩa

Sắp Xếp Phân Phối (Counting Sort) là một thuật toán sắp xếp không so sánh, được sử dụng để sắp xếp các phần tử trong một mảng có giá trị là các số nguyên không âm. Thay vì so sánh các phần tử, thuật toán này sử dụng một mảng phụ để đếm số lần xuất hiện của mỗi phần tử trong mảng cần sắp xếp.

Để thực hiện Sắp Xếp Phân Phối, ta cần một mảng phụ (gọi là mảng đếm) với độ dài đủ lớn để chứa số lượng các giá trị có thể xảy ra trong mảng đầu vào. Sau khi đếm xong số lần xuất hiện của từng giá trị, thuật toán sẽ tái tạo lại mảng sắp xếp bằng cách đặt các giá trị theo thứ tự, dựa trên số lần xuất hiện của chúng.

Điều thú vị của Sắp Xếp Phân Phối là, mặc dù về lý thuyết, nó không phải là một thuật toán so sánh, nhưng nó lại có thể thực hiện sắp xếp rất nhanh trong những trường hợp mà các giá trị trong mảng không quá lớn và không có sự phân bố quá rộng.

Tuy nhiên, thuật toán này không phải là một giải pháp phù hợp cho mọi trường hợp, đặc biệt là khi các giá trị trong mảng có phạm vi quá lớn hoặc có nhiều giá trị trùng lặp trong mảng cần sắp xếp.

Cách Giải

Thuật toán Sắp Xếp Phân Phối hoạt động trên nguyên tắc đếm số lần xuất hiện của các phần tử trong mảng. Sau đây là cách giải chi tiết:

Tạo một mảng mới để đếm số lần xuất hiện của các giá trị khác nhau trong mảng. Mảng này sẽ có chỉ số tương ứng với giá trị của các phần tử trong mảng cần sắp xếp.
Duyệt qua mảng cần sắp xếp. Với mỗi giá trị, ta sẽ tăng giá trị tại chỉ số tương ứng trong mảng đếm lên 1.
Sau khi đã đếm xong tất cả các phần tử, ta sẽ duyệt qua mảng đếm để tạo ra mảng đã sắp xếp. Mỗi chỉ số trong mảng đếm sẽ cho biết số lượng phần tử có giá trị tương ứng, và ta sẽ tạo các phần tử trong mảng kết quả dựa vào số lần xuất hiện này.
Với mỗi giá trị trong mảng đếm, ta sẽ tạo đúng số lượng phần tử tương ứng với chỉ số của giá trị trong mảng đếm.

Bạn thấy đó, thuật toán này rất hiệu quả khi làm việc với các mảng có giá trị phần tử nằm trong một phạm vi nhỏ, giúp tiết kiệm thời gian so với các thuật toán sắp xếp so sánh thông thường.

Triển Khai

Để triển khai thuật toán Sắp Xếp Phân Phối 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 countingSort nhận vào một mảng các số nguyên.
Một mảng bên trong hàm để giữ số lần xuất hiện của các giá trị.
Một vòng lặp bên trong hàm để đếm và loại bỏ các giá trị, bằng cách tăng giá trị phần tử trong mảng đếm.
Một vòng lặp bên trong hàm để tái tạo lại mảng dựa trên mảng đếm, sao cho các phần tử xuất hiện theo đúng thứ tự.

Một điều nữa: Chúng ta cần tìm giá trị lớn nhất trong mảng, để mảng đếm có thể được tạo với kích thước chính xác. Ví dụ, nếu giá trị lớn nhất là 5, mảng đếm phải có tổng cộng 6 phần tử, để có thể đếm tất cả các số nguyên không âm có thể là 0, 1, 2, 3, 4 và 5.

Mã TypeScript sẽ trông như thế này:

function countingSort(nums: number[]): number[] {
  // Nếu mảng chỉ có 1 phần tử hoặc ít hơn, trả về mảng vì không cần sắp xếp
  if (nums.length <= 1) return nums;

  // Tìm giá trị lớn nhất trong mảng để xác định kích thước mảng đếm
  const max = Math.max(...nums);

  // Tạo một mảng đếm có kích thước (max + 1) và khởi tạo tất cả các phần tử bằng 0
  const count = new Array<number>(max + 1).fill(0);

  // Duyệt qua từng phần tử trong mảng đầu vào và tăng giá trị tại vị trí tương ứng trong mảng đếm
  for (const num of nums) {
    count[num]++;
  }

  // Tạo mảng mới để lưu trữ các giá trị đã sắp xếp
  const sortedNums: number[] = [];

  // Duyệt qua mảng đếm để tái tạo lại mảng đã sắp xếp
  for (let i = 0; i < count.length; i++) {
    // Khi giá trị tại vị trí i trong mảng đếm lớn hơn 0,
    while (count[i] > 0) {
      // Thêm i vào mảng đã sắp xếp và giảm số đếm tại vị trí i
      sortedNums.push(i);

      // Giảm giá trị tại vị trí tương ứng trong mảng đếm
      count[i]--;
    }
  }

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

Big O

Trong trường hợp tốt nhất, độ phức tạp thời gian của Sắp Xếp Phân Phối là O(n) khi tất cả các giá trị đều nằm trong một khoảng hẹp và không có sự phân bố bất thường.

Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán này có thể trở thành O(n^2) nếu dải giá trị quá lớn so với số lượng phần tử cần sắp xếp.

Trong trường hợp trung bình, độ phức tạp thời gian của Sắp Xếp Phân Phối là O(n+k), với n là số lượng phần tử của dãy số và k là giá trị lớn nhất trong dãy số.

Sắp Xếp Phân Phối rất hiệu quả khi phạm vi giá trị k không quá lớn so với số lượng phần tử n. Nếu k lớn hơn nhiều so với n, thuật toán có thể trở nên không hiệu quả do yêu cầu bộ nhớ lớn.

Độ phức tạp không gian của thuật toán này là O(k), vì thuật toán yêu cầu không gian bộ nhớ phụ thêm để lưu trữ mảng đếm, nơi k là phạm vi của các giá trị.

Toàn Cảnh

Sắp Xếp Phân Phối không phải là một thuật toán sắp xếp chung, mà chỉ hiệu quả trong những tình huống nhất định. Thường thì, thuật toán này được sử dụng trong các trường hợp mà các phần tử cần sắp xếp có giá trị trong một phạm vi nhỏ.

Thuật toán này là một giải pháp tuyệt vời khi làm việc với các số nguyên không âm hoặc dữ liệu có giá trị thuộc một phạm vi cụ thể, như các bài toán sắp xếp trong các hệ thống cơ sở dữ liệu hay phân tích thống kê.

Tuy nhiên, Sắp Xếp Phân Phối không phù hợp với các trường hợp mà giá trị phần tử có phạm vi quá rộng hoặc khi các phần tử có giá trị âm. Để giải quyết những trường hợp này, các thuật toán sắp xếp khác như Sắp Xếp Nhanh hay Sắp Xếp Trộn thường được ưu tiên.

Mặc dù thuật toán có thể thực hiện sắp xếp nhanh, nhưng cần lưu ý rằng nếu dữ liệu không đáp ứng được các yêu cầu của Sắp Xếp Phân Phối (ví dụ như có quá nhiều giá trị khác nhau hoặc có giá trị âm), nó có thể không phải là lựa chọn tối ưu.

Ứng Dụng

Sắp Xếp Phân Phối có thể được áp dụng trong nhiều tình huống thực tế, đặc biệt là trong các bài toán yêu cầu xử lý dữ liệu với số lượng phần tử lớn nhưng giá trị phần tử lại nằm trong một phạm vi nhỏ.

Ví dụ, trong các hệ thống quản lý cơ sở dữ liệu hoặc xử lý thông tin mà dữ liệu cần được sắp xếp theo một trường giá trị số, Sắp Xếp Phân Phối có thể tiết kiệm được nhiều thời gian so với các thuật toán so sánh truyền thống như Sắp Xếp Nhanh hay Sắp Xếp Trộn.

Một ứng dụng khác của thuật toán này là trong các hệ thống phân tích thống kê, nơi dữ liệu đầu vào có thể được giới hạn trong một phạm vi nhất định và việc sắp xếp chúng cần được thực hiện nhanh chóng để rút ra các kết quả.

Đối với các hệ thống nhúng hoặc các ứng dụng đòi hỏi tốc độ xử lý nhanh và bộ nhớ hạn chế, Sắp Xếp Phân Phối cũng là một lựa chọn phù hợp, vì thuật toán này có thể hoạt động nhanh trong các điều kiện có giới hạn về không gian bộ nhớ.

Hiểu Lầm

Một hiểu lầm phổ biến về Sắp Xếp Phân Phối là nó chỉ áp dụng cho các số nguyên. Mặc dù đúng rằng thuật toán này hoạt động tốt nhất với các giá trị nguyên, nhưng nó cũng có thể được điều chỉnh để làm việc với các kiểu dữ liệu khác thông qua việc ánh xạ chúng về các chỉ số nguyên.

Một hiểu lầm khác là cho rằng Sắp Xếp Phân Phối luôn nhanh hơn các thuật toán khác. Thực tế thì tốc độ của nó phụ thuộc vào dải giá trị và kích thước dữ liệu. Trong trường hợp dải quá lớn, nó có thể trở nên kém hiệu quả hơn.

Nhiều người cũng nghĩ rằng Sắp Xếp Phân Phối không thể xử lý dữ liệu bị trùng lặp. Tuy nhiên, thực tế thì thuật toán này rất tốt trong việc quản lý và xử lý các phần tử trùng lặp.

Cuối cùng, hãy nhớ rằng Sắp Xếp Phân Phối không phải lúc nào cũng là lựa chọn tốt nhất cho mọi tình huống. Việc hiểu rõ ngữ cảnh sử dụng sẽ giúp bạn quyết định khi nào nên áp dụng nó.

Tóm Tắt

Sắp Xếp Phân Phối là một thuật toán mạnh mẽ và hiệu quả cho việc sắp xếp dữ liệu nguyên trong khoảng giá trị hẹp.

Nó hoạt động dựa trên nguyên tắc đếm và không yêu cầu so sánh trực tiếp giữa các phần tử.

Với độ phức tạp thời gian O(n + k), nó phù hợp cho những bài toán yêu cầu tốc độ và hiệu suất cao.

Cuối cùng, hãy nhớ rằng sự lựa chọn đúng đắn giữa các thuật toán sẽ giúp bạn tối ưu hóa quy trình làm việc và nâng cao hiệu quả trong lập trình.

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