Đồ án: Tìm hiểu và cài đặt thuật toán Counting sort
Tên Đồ Án: Tìm hiểu thuật toán Counting sort 1. Ý nghĩa của đồ án Sắp xếp là một trong những thuật toán mà bất kì lập trình viên nào cũng phải trải qua trong quá trình học tập của mình. Trong số đó COUNTING SORT – Sắp xếp bằng phương pháp đếm phân phối là một trong những thuật ...
Tên Đồ Án: Tìm hiểu thuật toán Counting sort
1. Ý nghĩa của đồ án
Sắp xếp là một trong những thuật toán mà bất kì lập trình viên nào cũng phải trải qua trong quá trình học tập của mình. Trong số đó COUNTING SORT – Sắp xếp bằng phương pháp đếm phân phối là một trong những thuật toán hay có thể rút ngắn được thời gian của quá trình thực hiện thuật toán, việc cài đặt thuật toán khá đơn giản, có tính ứng dụng cao nên chúng tôi muốn chia sẽ đến tất cả các bạn. Đồ án hướng tới những bạn đam mê lập trình và đang trong quá trình tìm hiểu, học tập các giải thuật.
2. Nội dung đồ án:
a. Mô tả các yêu cầu của đồ án
Hiểu được thuật toán và tầm quan trọng của thuật toán.
Cài đặt, phân tích và ứng dụng được thuật toán.
b. Mô tả ý tưởng của phương pháp/thuật toán để giải quyết
Counting Sort là thuật toán sắp xếp bằng cách lập bảng thống kê các giá trị số nguyên.
c. Mô tả các phương pháp/thuật toán để giải quyết.
– Xây dựng mảng dd[i] với dd[i] là số lần xuất hiện của số nguyên i.
– Gọi GTMAX là giá trị lớn nhất của số nguyên cần sắp xếp, N là số lương phần tử cần sắp xếp.
Bước 1: dd[i]=0, với i=0..GTMAX.
Bước 2: Duyệt qua các số cần sắp xếp, với mỗi số có giá trị i thực hiện đếm: dd[i]=dd[i]+1;
Bước 3: Kết thúc, và sử dụng theo nhu cầu.
Độ phức tạp thuật toán: O(max(GTMAX, N))
d. Cài đặt/Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <bits/stdc++.h> using namespace std; const long GTMAX = 1000000; long dd[GTMAX + 1]; int main() { long n, x; for (long i = 0; i <= GTMAX; i++) dd[i] = 0; cin >> n; for (long i = 0; i<n; i++) { cin >> x; dd[x]++; } for (long i = 0; i <= GTMAX; i++) for (long j = 1; j <= dd[i]; j++) cout << i << " "; return 0; } |
Code trên chỉ xử lí cho số nguyên dương có giá trị nhỏ hơn 10^6, tuy nhiên nếu muốn sắp xếp số âm, thì có thể làm tương tự theo ý tưởng đánh dấu trên, dù vậy, dường như trong c++ không cho hỗ trợ truy xuất mảng có chỉ số âm, nên ta có thể tạo thêm mảng để đánh dấu số âm và lọc ra 2 mảng số âm, số dương ngay từ lúc đếm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <bits/stdc++.h> using namespace std; const long GTMAX = 1000000; long dd[GTMAX + 1]; //dd cho số dương long dda[GTMAX + 1]; // dd cho số âm int main() { long n, x; for (long i = 0; i <= GTMAX; i++) { dd[i] = 0; dda[i] = 0; } cin >> n; for (long i = 0; i<n; i++) { cin >> x; if (x >= 0) dd[x]++; else dda[abs(x)]++; } for (long i = GTMAX; i>0; i--) for (long j = 1; j <= dda[i]; j++) cout << -i << " "; for (long i = 0; i <= GTMAX; i++) for (long j = 1; j <= dd[i]; j++) cout << i << " "; return 0; 33. } |
Test mẫu:
| Input | Output |
| 7 5 2 -2 -1 4 -2 0 | -2 -2 -1 0 2 4 5 |
e. Đánh giá ưu, nhược điểm và so sánh:
Nhược điểm:
– Chỉ sắp xếp được cho số nguyên.
– Phải biết miền giá trị của số nguyên.
– Miền giá trị lớn quá 10^7 sẽ không thể tạo mảng dd để lưu trữ.
Ưu điểm:
– Cài đặt đơn giản.
– Độ phức tạp thuật toán phụ thuộc vào miền giá trị.
So sánh:
Ví dụ 1:
– Giả sử số lượng phần tử cần sắp xếp là 10^6, và giá trị phần tử lớn nhất là 10^9.
| So sánh | Interchange sort | Quicksort | Counting sort |
| Độ phức tạp | O(10^12) | O(10^6 log2 10^6) | O(10^9) – không thể lưu trữ |
| Thời gian thực hiện | Quá 1 giây | Đạt yêu cầu | Không thực hiện được |
Ví dụ 2:
– Giả sử số lượng phần tử cần sắp xếp là 10^8, và giá trị phần tử lớn nhất là 10^7.
| So sánh | Interchange sort | Quicksort | Counting sort |
| Độ phức tạp | O(10^16) | O(10^7 log2 10^7) | O(10^7) |
| Thời gian thực hiện | Quá 1 giây | Quá 1 giây | Đạt yêu cầu |
– Như vậy, tùy vào độ lớn dữ liệu mà ta lựa chọn thuật toán sắp xếp cho phù hợp
f. Kết quả thử nghiệm
Ví dụ:
Cho dãy cần sắp xếp: 1, 4, 2, 7, 8, 2, 1, 3, 8, 6, 2
Bước 1: Khởi tạo mảng dd
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Bước 2:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Bước 3:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
Bước 4:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
Bước 5:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
Bước 6:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
Bước 7:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 1 | 2 | 0 | 1 | 0 | 0 | 1 | 1 |
Bước 8:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 2 | 2 | 0 | 1 | 0 | 0 | 1 | 1 |
Bước 9:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 2 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
Bước 10:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 2 | 2 | 1 | 1 | 0 | 0 | 1 | 2 |
Bước 11:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 2 | 2 | 1 | 1 | 0 | 1 | 1 | 2 |
Bước 12:
| DD | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| i | 0 | 2 | 3 | 1 | 1 | 0 | 1 | 1 | 2 |
Như vậy kết quả sau khi sắp xếp là: 1, 1, 2, 2, 2, 3, 4, 6, 7, 8, 8.
