Distribution Sort - Radix Sort

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.

Thuật toán Radix Sort

Radix Sort là thuật toán sắp xếp tiếp cận theo một hướng hoàn toàn khác 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 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ụ

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

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

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

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

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

Hiện thực hàm Radix Sort

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;
	}
}

Code mẫu Radix Sort

#include <iostream>
using namespace std;

#define MAX 5

void printArray(int *a, int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << "\t";
}

void radixSort(int *a, int n)
{
	int b[MAX], m = a[0], exp = 1;

	for (int i = 0; i < n; i++)
		if (a[i] > m)
			m = a[i];

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

int main()
{
	int arr[MAX] = {25, 5, 9, 10, 6};
	int i, n;

	cout << endl << "Before sort  : ";
	printArray(&arr[0], n);

	RadixSort(&arr[0], n);

	cout << endl << "After sort : ";
	printArray(&arr[0], n);

	return 0;
}

Bài chung Series

• Distribution Sort - Bucket Sort
• Distribution Sort - Radix Sort
• Distribution Sort - Counting Sort