DAA - Sắp xếp theo Radix

Radix sortlà một phương pháp nhỏ mà nhiều người sử dụng một cách trực giác khi sắp xếp theo thứ tự bảng chữ cái một danh sách lớn các tên. Cụ thể, danh sách tên được sắp xếp đầu tiên theo chữ cái đầu tiên của mỗi tên, tức là các tên được sắp xếp thành 26 lớp.

Theo trực giác, người ta có thể muốn sắp xếp các số theo chữ số có nghĩa nhất của chúng. Tuy nhiên, sắp xếp Radix hoạt động phản trực giác bằng cách sắp xếp trên các chữ số có nghĩa nhỏ nhất trước. Trong lần vượt qua đầu tiên, tất cả các số được sắp xếp theo chữ số có nghĩa nhỏ nhất và được kết hợp trong một mảng. Sau đó, trong lần vượt qua thứ hai, toàn bộ các số được sắp xếp lại trên các chữ số có nghĩa nhỏ nhất thứ hai và được kết hợp trong một mảng, v.v.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Phân tích

Mỗi phím được xem một lần cho mỗi chữ số (hoặc chữ cái nếu các phím là chữ cái) của phím dài nhất. Do đó, nếu khóa dài nhất cóm chữ số và có n phím, sắp xếp cơ số có thứ tự O(m.n).

Tuy nhiên, nếu chúng ta nhìn vào hai giá trị này, kích thước của các phím sẽ tương đối nhỏ khi so sánh với số lượng phím. Ví dụ, nếu chúng ta có khóa sáu chữ số, chúng ta có thể có hàng triệu bản ghi khác nhau.

Ở đây, chúng tôi thấy rằng kích thước của các khóa không đáng kể và thuật toán này có độ phức tạp tuyến tính O(n).

Thí dụ

Ví dụ sau đây cho thấy cách sắp xếp Radix hoạt động trên bảy số có 3 chữ số.

Đầu vào	1 lần vượt qua	2 nd đèo	3 thứ đèo
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

Trong ví dụ trên, cột đầu tiên là đầu vào. Các cột còn lại hiển thị danh sách sau khi sắp xếp liên tiếp ở vị trí các chữ số ngày càng có nghĩa. Mã cho sắp xếp Radix giả định rằng mỗi phần tử trong một mảngA của n yếu tố có d chữ số, chữ số ở đâu 1 là chữ số bậc thấp nhất và d là chữ số bậc cao nhất.