Thuật toán sắp xếp đếm phân phối – Counting Sort

Giới thiệu

Thuật toán sắp xếp đếm phân phối (Counting Sort) là thuật toán sắp xếp các phần tử trong một mảng bằng cách đếm số lần xuất hiện của mỗi phần tử duy nhất trong mảng. Số đếm được lưu trữ trong một mảng phụ và việc sắp xếp được thực hiện bằng cách ánh xạ số đếm như một chỉ số của mảng phụ.

Ý tưởng thuật toán sắp xếp đếm phân phối

Bước 1

Tìm ra phần tử lớn nhất (giả sử là max ) từ mảng đã cho.

Bước 2

Khởi tạo một mảng count có độ dài là max+1 với tất cả các phần tử 0. Mảng này được sử dụng để lưu trữ số lượng các phần tử trong mảng.

Bước 3

Lưu trữ số lượng của từng phần tử tại chỉ mục tương ứng của chúng trong mảng count .

Ví dụ: Nếu số phần tử của 3 là 2 thì 2 được lưu ở vị trí thứ 3 của mảng count . Nếu phần tử 5 không xuất hiện trong mảng, thì 0 được lưu ở vị trí thứ 5.

Bước 4

Lưu trữ tổng số lượng của các phần tử trong mảng count . Nó sẽ giúp ta đặt chính xác các phần tử vào chỉ mục của mảng đã sắp xếp.

Bước 5

Tìm chỉ số của từng phần tử của mảng ban đầu trong mảng count . Đặt phần tử tại chỉ số được tính như trong hình dưới đây.

Bước 6

Sau khi đặt mỗi phần tử vào đúng vị trí của nó, ta giảm số lượng của mảng count đi một.

Thuật toán sắp xếp đếm phân phối

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1
Code language:PHP(php)

Cài đặt thuật toán sắp xếp đếm phân phối

function insertionSort(array) {
    var size = array.length;

    for (var step = 1; step < size; step++) {
      var key = array[step];
      var j = step - 1;

      // Compare key with each element on the left of it until an element smaller than
      // it is found.
      // For descending order, change key<array[j] to key>array[j].
      while (j >= 0 && key < array[j]) {
        array[j + 1] = array[j];
        --j;
      }

      // Place key at after the element just smaller than it.
      array[j + 1] = key;
    }
  }

var arr = [3, 5, -2, 14, -9, 30];
insertionSort(arr);
console.log(arr);

Code language:PHP(php)

Kết quả

[-9, -2, 3, 5, 14, 30]
Code language:JSON / JSON with Comments(json)

Đánh giá thuật toán sắp xếp đếm phân phối

Có 4 vòng lặp chính được sử dụng trong thuật toán sắp xếp đếm phân phối (Việc tìm giá trị lớn nhất có thể được thực hiện bên ngoài hàm).

Độ phức tạp thời gian:

Độ phức tạp tổng quát = O(max)+O(size)+O(max)+O(size) = O(max+size)

• Trường hợp xấu nhất: O(n+k)
• Trường hợp tốt nhất: O(n+k)
• Trường hợp trung bình: O(n+k)

Trong tất cả các trường hợp trên, độ phức tạp của thuật toán sắp xếp đếm phân phối là như nhau vì cho dù các phần tử được đặt trong mảng như thế nào thì thuật toán cũng trải qua n + k lần.

Không có phép so sánh nào được thực hiện, vì vậy thuật toán sắp xếp đếm phân phối tốt hơn so với các thuật toán có sử dụng phép so sánh. Tuy nhiên, nó sẽ thật tệ nếu mảng ban đầu có kích thước lớn.

Độ phức tạp không gian:

Độ phức tạp không gian của thuật toán sắp xếp đếm phân phối là O(max) vì phạm vi phần tử càng lớn thì độ phức tạp không gian càng lớn.

Ứng dụng của thuật toán sắp xếp đếm phân phối

Thuật toán sắp xếp đếm phân phối được sử dụng trong các trường hợp:

• Mảng có ít số nguyên khác nhau hơn số với kích thước (Có nhiều phần tử trùng trong 1 mảng)
• Độ phức tạp thuật toán là tuyến tính

Các bạn có thể tham khảo các bài viết hay về thuật toán sắp xếp trong JavaScript tại đây.

Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.