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

NỘI DUNG BÀI VIẾT

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.

Thuật toán sắp xếp đếm phân phối - Counting Sort — 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 lặp lại các phần tử, tính toán về số lần mỗi phần tử xuất hiện trong mảng đầu vào. Sau đó, nó thực hiện một phép tính tổng (từ vòng lặp thứ hai) để xác định với mỗi phần tử, vị trí bắt đầu trong mảng đầu ra của các phần tử đó. Cuối cùng, nó lặp lại các phần tử một lần nữa, di chuyển từng phần tử vào vị trí đã sắp xếp.

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

function countingSort(arr, min, max)
  {
    var i, z = 0, count = [];
 
    for (i = min; i <= max; i++) {
        count[i] = 0;
    }
 
    for (i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }
 
    for (i = min; i <= max; i++) {
        while (count[i]-- > 0) {
            arr[z++] = i;
        }
    }
 return arr;
}

var arr = [3, 0, 2, 5, 4, 1];
console.log(countingSort(arr, 0, 5));Code language: JavaScript (javascript)

Kết quả

[-10 -5 -3 -1 0 5 8 10]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:

Vòng lặp	Độ phức tạp thời gian
1	O(max)
2	O(size)
3	O(max)
4	O(size)

Độ 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ảm ơn bạn đã theo dõi bài viết!

Các bạn có thể tham khảo các bài viết hay về 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.

TỔNG HỢP TÀI LIỆU HỌC LẬP TRÌNH CƠ BẢN CHO NGƯỜI MỚI BẮT ĐẦU
KHOÁ HỌC BOOTCAMP JAVA/JAVASCRIPT/PHP TRỞ THÀNH LẬP TRÌNH VIÊN TRONG 5-6 THÁNG

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

Giới thiệu