Chương trình C cho Radix Sort

Một thuật toán sắp xếp là một thuật toán đặt các thành phần của một danh sách theo một thứ tự nhất định. Các thứ tự được sử dụng nhiều nhất là thứ tự số và thứ tự từ vựng.

Radix sort là một thuật toán sắp xếp không so sánh. Thuật toán sắp xếp theo cơ số là thuật toán được ưu tiên nhất cho danh sách chưa được sắp xếp.

Nó sắp xếp các phần tử bằng cách nhóm ban đầu các chữ số riêng lẻ của cùng một giá trị vị trí. Ý tưởng của Radix Sort là sắp xếp từng chữ số bắt đầu từ chữ số có nghĩa nhỏ nhất (LSD) đến chữ số có nghĩa nhất (MSD) , theo thứ tự tăng / giảm của chúng. Sắp xếp theo cơ số là một phương pháp nhỏ được sử dụng nhiều lần khi sắp xếp theo thứ tự bảng chữ cái một danh sách tên quá khổ. Cụ thể, danh sách tên ban đầu được sắp xếp 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 theo hai mươi sáu loại.

Hãy cùng chúng tôi xem lại hình minh họa sau để hiểu rõ ràng về hoạt động của thuật toán sắp xếp cơ số. Rõ ràng, số lần vượt qua / lặp lại phụ thuộc vào kích thước của số cá nhân cao nhất.

Trong ví dụ trên, cột chính 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.

Phân tích độ phức tạp của Radix Sort O (m.n).

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

Ở đây, chúng ta có xu hướng thấy rằng kích thước của các phím không quan trọng và thuật toán này có chất lượng tuyến tính O (n)

Thuật toán

 Radix_sort (list, n) shift =1for loop =1 to keyize do for entry =1 to n do bucketnumber =(list [entry] .key / shift) mod 10 append (bucket [bucketnumber], list [entry] ) list =mergebuckets () shift =shift * 10 

Ví dụ

Đây là Chương trình C để triển khai Sắp xếp theo Radix.

 #include  int get_max (int a [], int n) {int max =a [0]; for (int i =1; i  max) max =a [i]; return max;} void radix_sort (int a [], int n) {int bucket [10] [10], bucket_cnt [10]; int i, j, k, r, NOP =0, divisor =1, lar, pass; lar =get_max (a, n); while (lar> 0) {NOP ++; ấu trùng / =10; } for (pass =0; pass  
 Đầu ra 
  Nhập số mục cần sắp xếp 6 Nhập mục:567 789 121 212 563 562 Nhập sau chuyển 1:121 212 562 563 567 789 Nhập sau chuyển 2:212 121 562 563 567 789 Nhập sau 3:121 212 562 563 567 789 562 563 567 789