Sắp xếp theo cơ số là thuật toán sắp xếp không so sánh. Thuật toán sắp xếp này hoạt động trên các khóa số nguyên bằng cách nhóm các chữ số có cùng vị trí và giá trị. Cơ số là cơ sở của một hệ thống số. Như chúng ta biết rằng trong hệ thập phân, cơ số hoặc cơ số là 10. Vì vậy, để sắp xếp một số số thập phân, chúng ta cần hộp vị trí 10 để lưu trữ số.
Sự phức tạp của Kỹ thuật sắp xếp theo Radix
-
Độ phức tạp về thời gian:O (nk)
-
Độ phức tạp của không gian:O (n + k)
Input − The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output − Data after Sorting: 20 52 78 187 300 612 630 745 802 932
Thuật toán
radixSort (mảng, kích thước, maxDigit)
Đầu vào :Một mảng dữ liệu và tổng số trong mảng, đếm chữ số của số tối đa.
Đầu ra :Mảng đã sắp xếp.
Begin define 10 lists as pocket for i := 0 to max -1 do m = 10i+1 p := 10i for j := 0 to n-1 do temp := array[j] mod m index := temp / p pocket[index].append(array[j]) done count := 0 for j := 0 to radix do while pocket[j] is not empty array[count] := get first node of pocket[j] and delete it count := count +1 done done End
Mã mẫu
#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void radixSort(int *arr, int n, int max) {
int i, j, m, p = 1, index, temp, count = 0;
list<int> pocket[10]; //radix of decimal number is 10
for(i = 0; i< max; i++) {
m = pow(10, i+1);
p = pow(10, i);
for(j = 0; j<n; j++) {
temp = arr[j]%m;
index = temp/p; //find index for pocket array
pocket[index].push_back(arr[j]);
}
count = 0;
for(j = 0; j<10; j++) {
//delete from linked lists and store to array
while(!pocket[j].empty()) {
arr[count] = *(pocket[j].begin());
pocket[j].erase(pocket[j].begin());
count++;
}
}
}
}
int main() {
int n, max;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter the maximum digit of elements: ";
cin >> max;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Data before Sorting: ";
display(arr, n);
radixSort(arr, n, max);
cout << "Data after Sorting: ";
display(arr, n);
} Đầu ra
Enter the number of elements: 10 Enter the maximum digit of elements: 3 Enter elements: 802 630 20 745 52 300 612 932 78 187 Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932