STDIO Sắp xếp là quá trình biến đổi danh sách các đối tượng thành một danh sách thoả mãn một thứ tự nào đó. Thuật toán sắp xếp đóng vai trò quan trọng và được ứng dụng nhiều vào trong lập trình. Trong số đó, Radix Sort là thuật toán hay, độ phức tạp thấp và sử dụng nhiều trong thực tiễn.
Nội dung bài viết

Giới thiệu

Sắp xếp là quá trình biến đổi danh sách các đối tượng thành một danh sách thoả mãn một thứ tự nào đó. Thuật toán sắp xếp đóng vai trò quan trọng và được ứng dụng nhiều vào trong lập trình. Trong số đó, Radix Sort là thuật toán hay, độ phức tạp thấp và được sử dụng nhiều trong thực tiễn.

Tiền đề bài viết

Thuật toán sắp xếp Radix Sort là một kiến thức hay tôi học được từ anh La Kiến Vinh. Tôi muốn chia sẻ kiến thức về thuật toán Radix Sort nhằm giúp các bạn có cái nhìn trực quan hơn và ứng dụng hiệu quả vào trong công việc.

Đối tượng hướng đến

Bài viết hướng đến các bạn có kiến thức cơ bản lập trình và muốn tìm hiểu về các giải thuật sắp xếp.

Khái niệm

Radix sort là một thuật toán sắp xếp tiếp cận theo một hướng hoàn toàn khác. Nếu như trong các thuật toán sắp xếp khác, 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 theo nguyên tắc phân loại thư của bưu điện (Postman’s sort). Radix sort không hề quan tâm đến việc so sánh giá trị của 2 phần tử mà bản thân việc phân loại và thứ tự phân loại sẽ tạo ra thứ tự cho các phần tử.

Ý tưởng

Giả sử mỗi phần tử ai trong dãy a0, a1, …, an-1 là một số nguyên có tối đa m chữ số. Phân loại các phần tử này lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, …, tương tự việc phân loại thư theo tỉnh thành, quận huyện, phường xã, …

Ví dụ

Ta có mảng A cần sắp xếp gồm các phần tử sau:

964

354

368

128

495

121

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

 

121

 

 

 

 

 

 

 

 

 

495

 

 

 

 

 

 

 

 

 

128

 

 

 

 

 

 

 

 

 

368

 

 

 

 

 

 

 

 

 

354

 

 

 

354

 

 

 

128

 

964

121

 

 

964

495

 

 

368

 

A

1

2

3

4

5

6

7

8

9

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

128

 

 

 

 

 

 

 

 

 

368

 

 

 

 

 

 

 

 

 

495

 

 

 

 

 

 

 

 

 

354

 

 

 

 

 

 

 

 

 

964

 

128

 

 

 

368

 

 

 

121

 

121

 

 

354

964

 

 

495

A

1

2

3

4

5

6

7

8

9

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

495

 

 

 

 

 

 

 

 

 

368

 

 

 

 

 

 

 

 

 

964

 

 

 

 

 

 

 

 

 

354

 

 

 

 

 

 

 

 

 

128

128

 

368

 

 

 

 

 

 

121

121

 

354

495

 

 

 

 

964

A

1

2

3

4

5

6

7

8

9

 

Mảng sau khi đươc sắp xếp:

121

128

354

368

495

964

Hiện thực

void RadixSort(int *a, int n)
{
		int i, b[MAX], m = a[0], exp = 1;
		for (i = 0; i < n; i++)
		{
			if (a[i] > m)
				m = a[i];
		}
		while (m / exp > 0)
		{
			int bucket[10] ={  0 };
			for (i = 0; i < n; i++)
				bucket[a[i] / exp % 10]++;
			for (i = 1; i < 10; i++)
				bucket[i] += bucket[i - 1];
			for (i = n - 1; i >= 0; i--)
				b[--bucket[a[i] / exp % 10]] = a[i];
			for (i = 0; i < n; i++)
				a[i] = b[i];
			exp *= 10;
		}
}

Download demo

STDIO_RadixSort

THẢO LUẬN
ĐÓNG