Tìm hiểu về RADIX SORT

Radix Sort là 1 trong những thuật toán sắp xếp được sử dụng phổ biến hiện nay. Để sắp xếp những thẻ thư viện, người ta tạo ra nhiều lô các thẻ theo thứ tự alphabet, mỗi lô chứa những tác giả có kí tự bắt đầu tên của họ trùng nhau. Và tương tự như thế các lô được sắp xếp dựa

 

vào chữ cái thứ 2, thứ 3,…..trong tên của họ. Quá trình này tiếp diễn đến khi số lần các lô được chia vào những chồng nhỏ hơn bằng với số chữ cái của tên dài nhất. Tuy nhiên để sắp xếp chính xác các thẻ thư viện thì thuật toán sắp xếp mỗi lô dựa vào chữ cái thứ i như trên phải ổn định (stable). Một thuật toán sắp xếp được gọi là sắp xếp ổn định nếu sau khi tiến hành sắp xếp vị trí tương đối giữa các phần tử bằng nhau không bị thay đổi. Tư tưởng của Radix Sort cũng tương tự như việc sắp xếp những thẻ thư viện trên.

Trên máy tính, đôi khi tư tưởng của Radix Sort được sử dụng để sắp xếp các mẫu tin (record) trong bảng dữ liệu theo nhiều trường (field). Ví dụ như chúng ta muốn sắp xếp các ngày theo ba khóa: năm, tháng và ngày. Theo cách làm thông thường, ta sẽ so sánh các năm với nhau, nếu có sự trùng năm thì so sánh tiếp tới tháng và nếu lại có sự trùng tháng thì so sánh tới ngày. Với tư tưởng của Radix Sort thì ta có thể thực hiện sắp xếp bảng tin 3 lần với một thuật toán sắp xếp ổn định.

Chi tiết xem tệp đính kèm!

Tệp đính kèm: http://www.mediafire.com/?211qnt8z120gzku

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s