Thuật toán sắp xếp: RADIX SORT

Ý tưởng

Radix Sort dựa trên nguyên tắc phân loại thư của bưu điện. Nó không quan tâm đến việc so sánh giá trị của phần tử và bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử.

Giải thuật thực hiện như sau:

  • Trước tiên, ta giả sử mỗi phần tử ai trong dãy a1, a2, …., an là một số nguyên có tối đa m chữ số.
  • Phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm…

 

Giải thuật

            Bước 1: // k cho biết chữ số dùng để phân loại hiện hành.

                        k = 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 nhau.

                        Khở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 3:  Nối B0, B1,…, B9 lại theo đúng trình tự thành a.

Bước 4k = k + 1.

                           Nếu k < m: lặp lại bước 2.

                           Ngược lại: Dừng   

Ví dụ

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

 

  • Phân loại theo hàng đơn vị

 

1

2

3

4

5

6

7

8

9

10

11

12

B0

9170

 

 

 

 

 

 

 

 

 

 

 

B1

701

 

 

 

 

 

 

 

 

 

 

 

B2

3252

 

 

 

 

 

 

 

 

 

 

 

B3

7013

 

 

 

 

 

 

 

 

 

 

 

B4

1424

 

 

 

 

 

 

 

 

 

 

 

B5

1725

8425

 

 

 

 

 

 

 

 

 

 

B6

 

 

 

 

 

 

 

 

 

 

 

 

B7

 

 

 

 

 

 

 

 

 

 

 

 

B8

4518

428

 

 

 

 

 

 

 

 

 

 

B9

999

7009

1239

 

 

 

 

 

 

 

 

 

            Sau khi nối:

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

 

  • Phân loại theo hàng chục

 

1

2

3

4

5

6

7

8

9

10

11

12

B0

701

7009

 

 

 

 

 

 

 

 

 

 

B1

7013

4518

 

 

 

 

 

 

 

 

 

 

B2

1424

1725

8425

428

 

 

 

 

 

 

 

 

B3

1239

 

 

 

 

 

 

 

 

 

 

 

B4

 

 

 

 

 

 

 

 

 

 

 

 

B5

3252

 

 

 

 

 

 

 

 

 

 

 

B6

 

 

 

 

 

 

 

 

 

 

 

 

B7

9170

 

 

 

 

 

 

 

 

 

 

 

B8

 

 

 

 

 

 

 

 

 

 

 

 

B9

999

 

 

 

 

 

 

 

 

 

 

 

            Sau khi nối:

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

 

  • Phân loại theo hàng trăm

 

1

2

3

4

5

6

7

8

9

10

11

12

B0

7009

7013

 

 

 

 

 

 

 

 

 

 

B1

9170

 

 

 

 

 

 

 

 

 

 

 

B2

1239

3252

 

 

 

 

 

 

 

 

 

 

B3

 

 

 

 

 

 

 

 

 

 

 

 

B4

1424

8425

428

 

 

 

 

 

 

 

 

 

B5

4518

 

 

 

 

 

 

 

 

 

 

 

B6

 

 

 

 

 

 

 

 

 

 

 

 

B7

701

1725

 

 

 

 

 

 

 

 

 

 

B8

 

 

 

 

 

 

 

 

 

 

 

 

B9

999

 

 

 

 

 

 

 

 

 

 

 

            Sau khi nối:

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

 

  • Phân loại theo hàng ngàn

 

1

2

3

4

5

6

7

8

9

10

11

12

B0

428

701

999

 

 

 

 

 

 

 

 

 

B1

1239

1424

1725

 

 

 

 

 

 

 

 

 

B2

 

 

 

 

 

 

 

 

 

 

 

 

B3

3252

 

 

 

 

 

 

 

 

 

 

 

B4

4518

 

 

 

 

 

 

 

 

 

 

 

B5

 

 

 

 

 

 

 

 

 

 

 

 

B6

 

 

 

 

 

 

 

 

 

 

 

 

B7

7009

7013

 

 

 

 

 

 

 

 

 

 

B8

8425

 

 

 

 

 

 

 

 

 

 

 

B9

9170

 

 

 

 

 

 

 

 

 

 

 

            Sau khi nối:

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

 

 

Kết quả

 

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

 

Chủ đề liên quan
Thuật toán sắp xếp: RADIX SORT

Cùng chuyên mục

Xem nhiều hôm nay