Radix Sort Là Gì

  -  

Khác với các thuật toán sắp xếp so sánh, thuật toán sắp xếp theo cơ số (Radix Sort) là một thuật toán sắp xếp không so sánh. Cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó nó còn có tên là Postmans sort.

Bạn đang xem: Radix sort là gì

Bạn đang xem: Radix sort là gì

Bài viết tham khảo: Danh sách các thuật toán sắp xếp phổ biến

Thuật toán này được thực hiện dựa trên ý tưởng nếu một danh sách đã được sắp xếp hoàn chỉnh thì từng phần tử cũng sẽ được sắp xếp hoàn chỉnh dựa trên giá trị của các phần tử đó. Thuật toán này yêu cầu danh sách cần được sắp xếp để có thể so sánh thứ tự các vị trí vì thế sắp xếp theo cơ số không giới hạn ở tập số nguyên (ta có thể dễ dàng đưa dạng xâu về cơ số nhị phân).

Phân loại: Thuật toán sắp xếpCấu trúc dữ liệu: ArrayPhức tạp thời gian: O(wn)Phức tạp không gian: O(w+n)

Độ phức tạp

Với một dãy n số, mỗi số có tối đa m chữ số, thuật toán thực hiện m lần các thao tác phân lô và ghép lô.Trong thao tác phân lô, mỗi phần tử chỉ được xét đúng một lần, khi ghép cũng vậy.Như vậy, chi phí cho việc thực hiện thuật toán hiển nhiên là O(2mn) = O(n)

Giải thích thuật toán sắp xếp theo cơ số

Ta biết rằng, để chuyển một khối lượng thư lớn đến tay người nhận ở nhiều địa phương khác nhau, bưư điện thường tổ chức một hệ thống phân loại thư phân cấp. Trước tiên, các thư đến cùng một tỉnh, thành phố sẽ được sắp chung vào một lô để gửi đến tỉnh thành tương ứng. Bưu điện các tỉnh thành này lại thực hiện công việc tương tự. Các thư đến cùng một quận, huyện sẽ được xếp vào chung một lô và gửi đến quận, huyện tương ứng. Cứ như vậy, các bức thư sẽ được trao đến tay người nhận một cách có hệ thông mà công việc sằp xếp thư không quá nặng nhọc.

Xem thêm: Diễn Viên Lục Tiểu Linh Đồng Dẻo Dai Ở Tuổi 62, Múa Gậy Điêu Luyện "Đúng Như" Tôn Ngộ Không

Mô phỏng lại qui trình trên, để sắp xếp dãy a1, a2, …, an giải thuật Radix Sort thực hiện như sau:

Các bước thực hiện thuật toán như sau:

Bước 1 : k cho biết chữ số dùng để phân loại hiện hànhk = 0; (k = 0: hàng đơn vị; k = 1: hàng chục) Bước 2 : Tạo các lô chứa các loại phần tử khác nhauKhởi tạo 10 lô B0, B1, .. , B9 rỗng;Bước 3 :For i = 1 .. n doÐặt ai vào lô Bt với t = chữ số thứ k của ai;Bước 4 :Nối B0, B1, .. , B9 lại (theo đúng trình tự) thành a.Bước 5 :k = k+1;Nếu k Ngược lại: Dừng

Cho dãy số a như sau:

701, 1725, 999, 9170, 3252, 4518, 7009, 1424, 428, 1239, 8425, 7013

Các bước tiến hành như sau:

Phân lô theo hàng đơn vị:

12

0701

11

1725

10

0999

9

9170

8

3252

7

4518

6

7009

5

1424

4

0428

3

1239

0999

2

8425

1725

4518

7009

1

7013

9170

0701

3252

7013

1424

8425

0428

1239

CS

B

0

1

2

3

4

5

6

7

8

9

Phân lô theo hàng chục:

12

0999

11

7009

10

1239

9

4518

8

0428

7

1725

6

8425

5

1424

4

7013

0428

3

3252

1725

2

0701

7009

4518

8425

1

9170

0701

7013

1424

1239

3252

9170

0999

CS

A

0

1

2

3

4

5

6

7

8

9

Phân lô theo hàng trăm:

12

0999

11

9170

10

3252

9

1239

8

0428

7

1725

6

8425

5

1424

4

4518

3

0428

2

7009

7013

3252

8425

1725

1

0701

7009

9170

1239

1424

4518

0701

0999

CS

B

0

1

2

3

4

5

6

7

8

9

Phân lô theo hàng ngàn:

12

0999

11

1725

10

0701

9

4518

8

0428

7

8425

6

1424

5

3252

4

1239

3

9170

0999

1725

2

7013

0701

1424

7013

1

7009

0428

1239

3252

4518

7009

8425

9170

CS

B

0

1

2

3

4

5

6

7

8

9

Lấy các phần tử từ các lô B0, B1, ., B9 nối lại thành a:

12

9170

11

8425

10

7013

9

7009

8

4518

7

3252

6

1725

5

1424

4

1239

3

0999

2

0701

1

0428

CS

B

0

1

2

3

4

5

6

7

8

9

Sắp xếp theo cơ số nhị phân

Giả sử chúng ta cần sắp xếp danh sách a, trong đó các phần tử là các số tự nhiên biểu diễn bằng 31 bit. Các bit được đánh số thứ tự từ phải sang trái bằng các số 0..30. Để đọc được bit thứ k của số tự nhiên x cần có một hàm GetBit(x,k). Hàm này có thể có sẵn trong ngôn ngữ lập trình, trong trường hợp không có sẵn nó có thể viết nhờ toán tử LShift (dịch trái) và toán tử AndBit. (Trong nhiều ngôn ngữ lập trình, từ khóa của toán tử AndBit trùng từ khóa với toán tử and theo nghĩa toán tử logic).

Function GetBit(Int: x,k)Return LShift(x,k) AndBit 1

Để sắp xếp (phân chia) danh sách theo bit thứ k của danh sách, ta tìm phần tử đầu tiên bên trái của danh sách có bit thứ k là 1 và phần tử đầu tiên bên phải có bit thứ k là 0 rồi đổi chỗ (Swap) cho nhau.

Xem thêm: Ngày 16 Tháng 4 Là Ngày Gì ? Xem Lịch Ngày 16 Tháng 4 Năm 2021

Bằng lời giải đệ quy, tiếp tục phân chia các danh sách con này theo bit thứ k-1.. cho đến bit thứ 0.

Xét ví dụ sau đây:

a=(2,6,3,7,4,5,1)Các số trong danh sách đều có thể biểu diễn bằng số nhị phân 3 bit. Bảng sau đây cho biểu diễn nhị phân của từng số trong danh sách

2637451
010110011111100101001

Với k = 2 việc phân chia theo bit thứ 2 tiến hành đổi chỗ a=6 cho a=1, và phân chia danh sách a thành hai danh sách a và a

2137456
010001011111100101110

Sau đó thuật toán đưa danh sách a vào stack và tiến hành phân chia danh sách a theo bit thứ k = 1, bằng cách đổi chỗ a = 2 cho a = 1,thành a và a

1237456
001010011111100101110

Tiếp theo là phân chia danh sách a theo bit thứ 0 thành a và a

1237456
001010011111100101110

Đến đây việc sắp xếp danh sách a hoàn thành. Thuật toán tiếp lấy a từ trong stack ra để sắp xếp theo cách phân chia như trên, lần lượt là quá trình phân chia như sau:

1235476
001010011101100111110
1234567
001010011100101110111

Viết thuật toán sắp xếp theo cơ số sử dụng C++

Sắp xếp một mảng sử dụng Sắp xếp theo cơ số sử dụng phương pháp phân lô:

#include #include #include #include #include using namespace std;// Radix Sort using base-10 radixtemplate void radixSort(InputIterator start, InputIterator end, OutputIterator output){const int BASE = 10; // Basestd::queue::value_type > bucket; // An array of buckets based on the baseunsigned size = end - start;// Get the maximum numbertypename std::iterator_traits::value_type max = *std::max_element(start, end); // O(n)// Copy from input to outputstd::copy(start, end, output); // O(n)// Iterative Radix Sort - if k is log BASE (max), then the complexity is O( k * n)for (unsigned power = 1; max != 0; max /= BASE, power *= BASE){ // Assign to bucketsfor (OutputIterator it = output; it != output + size; it++){unsigned bucketNumber = (unsigned)((*it / power) % BASE);bucket.push(*it); // O(1)}// Re-assembleOutputIterator it = output;for (int i = 0; i input = { 5, 10, 15, 20, 25, 50, 40, 30, 20, 10, 9524, 878, 17, 1, 99, 18785, 3649, 164, 94,123, 432, 654, 3123, 654, 2123, 543, 131, 653, 123, 533, 1141, 532, 213, 2241, 824, 1124, 42, 134, 411,491, 341, 1234, 527, 388, 245, 1992, 654, 243, 987 };vector output(input.size());radixSort(input.begin(), input.end(), output.begin());for (unsigned it : output){cout Sử dụng thuật toán sắp xếp theo cơ số Radix Sort đối với mảng số nguyên và chuỗi:

#include #include #include #include #include #include #include templateusing expr = std::integral_constant;//-----------------------------------------------------------------------------template class radix_sort{template void sort(I& idx, const S& slice) const{using A = std::array;A count = {};I prev = idx;for (auto i : prev)++count;A offset = { { 0 } };std::partial_sum(count.begin(), count.end() - 1, offset.begin() + 1);for (auto i : prev)idx++> = i;}public:template std::vector operator()(const D& data) const{std::vector idx(data.size());std::iota(idx.begin(), idx.end(), 0);if (data.size() (), data, digit));});}return idx;}};//-----------------------------------------------------------------------------struct int_view{templatesize_t size(const A& a) const { return sizeof(a); }template unsigned char at(expr, const E& elem, size_t pos) const{return (elem >> pos) & 0xFF;}};//-----------------------------------------------------------------------------struct array_view{templatesize_t size(const A& a) const { return a.size(); }template typename E::value_typeat(std::false_type, const E& elem, size_t pos) const{return elem;}template typename E::value_typeat(std::true_type, const E& elem, size_t pos) const{using T = typename E::value_type;return pos numbers(){return{ {162, 794, 311, 528, 165, 601, 262, 654, 689, 748,450, 83, 228, 913, 152, 825, 538, 996, 78, 442,106, 961, 4, 774, 817, 868, 84, 399, 259, 800,431, 910, 181, 263, 145, 136, 869, 579, 549, 144,853, 622, 350, 513, 401, 75, 239, 123, 183, 239,417, 49, 902, 944, 490, 489, 337, 900, 369, 111,780, 389, 241, 403, 96, 131, 942, 956, 575, 59,234, 353, 821, 15, 43, 168, 649, 731, 647, 450,547, 296, 744, 188, 686, 183, 368, 625, 780, 81,929, 775, 486, 435, 446, 306, 508, 510, 817, 794} };}std::vectorstrings(){return{"subdivides","main street","pants","impaled decolonizing","argillaceous","axial satisfactoriness","temperamental","hypersensitiveness","bears","hairbreadths","creams surges","unlaboured","hoosier","buggiest","mauritanians","emanators","acclaiming","zouaves dishpan","traipse","solarisms","remunerativeness","solubilizing","chiseled","jugular","ooziness","toastier","baud","suffixed","powerless tiding","disassimilated","gasps","flirtier","uh"};}//-----------------------------------------------------------------------------templatevoid test(G generate, S sort){auto data = generate();auto idx = sort(data);std::cout ());test(strings, radix_sort());getchar();return 0;}Sắp xếp theo cơ số Radix Sort sử dụng cơ số nhị phân trong C++:

#include #include #include #include #include#include#include using namespace std;// Radix sort comparator for 32-bit two"s complement integersclass radix_test{const int bit; // bit position to examinepublic:radix_test(int offset) : bit(offset) {} // constructorbool operator()(int value) const // function call operator{if (bit == 31) // sign bitreturn value = 0){int *mid = std::partition(first, last, radix_test(msb));msb--; // decrement most-significant-bitmsd_radix_sort(first, mid, msb); // sort left partitionmsd_radix_sort(mid, last, msb); // sort right partition}}int main(int argc, char *argv){int data = { 170, 45, 75, -90, -802, 24, 2, 66 };lsd_radix_sort(data, data + 8);// msd_radix_sort(data, data + 8);std::copy(data, data + 8, std::ostream_iterator(std::cout, " "));system("PAUSE");return EXIT_SUCCESS;}