Đồ á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 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

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

#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:

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.

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.

– 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

Bước 2:

Bước 3:

Bước 4:

Bước 5:

Bước 6:

Bước 7:

Bước 8:

Bước 9:

Bước 10:

Bước 11:

Bước 12:

Như vậy kết quả sau khi sắp xếp là: 1, 1, 2, 2, 2, 3, 4, 6, 7, 8, 8.

4. Tài liệu tham khảo

Các tài liệu tham khảo liên quan được sử dụng trong đồ án:

• https://www.stdio.vn/articles/read/474/distribution-sort-counting-sort
• https://en.wikipedia.org/wiki/Counting_sort
• ….

5. Tải dữ liệu đồ án

Bạn có thể tải file báo cáo dành cho đồ án này tại link dưới đây:

https://drive.google.com/open?id=0ByRwQNO5GTcdOHU5RnBIbEgzMVE