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.
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
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
