02/10/2018, 14:18

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

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.

Test mẫu:

InputOutput
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ánhInterchange sortQuicksortCounting sort
Độ phức tạpO(10^12)O(10^6 log2 10^6)O(10^9) – không thể lưu trữ
Thời gian thực hiệnQuá 1 giâyĐạt yêu cầuKhô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ánhInterchange sortQuicksortCounting sort
Độ phức tạpO(10^16)O(10^7 log2 10^7)O(10^7)
Thời gian thực hiệnQuá 1 giâyQuá 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

DD012345678
i000000000

Bước 2:

DD012345678
i010000000

Bước 3:

DD012345678
i010010000

Bước 4:

DD012345678
i011010000

Bước 5:

DD012345678
i011010010

Bước 6:

DD012345678
i011010011

Bước 7:

DD012345678
i012010011

Bước 8:

DD012345678
i022010011

Bước 9:

DD012345678
i022110011

Bước 10:

DD012345678
i022110012

Bước 11:

DD012345678
i022110112

Bước 12:

DD012345678
i023110112

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.

0