Search…

Distribution Sort - Radix Sort

18/08/20203 min read
Distribution Sort - Radix Sort là thuật toán sắp xếp độ phức tạp thấp.

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:

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

IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024