Thuật toán sắp xếp theo cơ số (Radix Sort)

Trong bài viết này, ta sẽ cùng tìm hiểu về cách hoạt động của thuật toán sắp xếp theo cơ số. Ngoài ra, ta sẽ triển khai ví dụ về sắp xếp dựa theo cơ số được viết bằng ngôn ngữ lập trình C.

Thuật toán sắp xếp theo cơ số

Sắp xếp dựa trên cơ số là một kỹ thuật sắp xếp các phần tử bằng cách nhóm các chữ số riêng lẻ của một giá trị có cùng một vị trí. Sau đó, sắp xếp các phần tử theo thứ tự tăng hoặc giảm.

Giả sử, chúng ta có một mảng gồm 8 phần tử. Đầu tiên, chúng ta sẽ sắp xếp các phần tử dựa trên giá trị của vị trí đơn vị. Sau đó, chúng ta sẽ sắp xếp các phần tử dựa trên giá trị của vị trí thứ mười. Quá trình này tiếp tục cho đến vị trí cuối cùng.

Giả sử ta có mảng ban đầu là [121, 432, 564, 23, 1, 45, 788]. Nó được sắp xếp theo cơ số như trong hình bên dưới.

Cách thức hoạt động của thuật toán sắp xếp theo cơ số

Bước 1: Tìm phần tử lớn nhất trong mảng, được gọi là biến max. Gọi X là số chữ số trong biến max. X có thể tính toán được bởi vì chúng ta phải đi qua tất cả các vị trí quan trọng của tất cả các phần tử. Trong mảng [121, 432, 564, 23, 1, 45, 788], chúng ta có số lớn nhất là 788. Nó có 3 chữ số. Do đó, vòng lặp sẽ lên đến chữ số hàng trăm.
Bước 2: Bây giờ, ta lần lượt đi qua từng vị trí quan trọng.
- Sử dụng bất kỳ kỹ thuật sắp xếp ổn định nào để sắp xếp các chữ số tại mỗi vị trí quan trọng. Chúng ta đã sử dụng sắp xếp đếm cho việc này.
- Sắp xếp các phần tử dựa trên các chữ số hàng đơn vị (X = 0).

- Sử dụng sắp xếp đếm để sắp xếp các phần tử dựa trên vị trí
Bước 3: Bây giờ, ta sẽ sắp xếp các phần tử dựa trên các chữ số ở hàng chục.

Bước 4: Cuối cùng, sắp xếp các phần tử dựa trên các chữ số ở vị trí hàng trăm.

Thuật toán sắp xếp dựa theo cơ số được triển khai như sau:

Hàm thực hiện sắp xếp theo cơ số với tham số đầu vào là (mảng cần sắp xếp)
  Gán d = số lượng các chữ số trong phần tử lớn nhất
  Tạo d khối có kích thước từ 0 tới 9
  Sử dụng vòng lặp for với i = 0 cho tới d
    Sắp xếp các phần tử dựa theo các chữ số tại vị trí bằng cách sử dụng hàm sắp xếp theo số đếm

Hàm sắp xếp theo số đếm với bộ tham số là (mảng cần sắp xếp, d)
  Gán max = tìm phần tử lớn trong các phần tử tại vị trí thứ d
  Khởi mảng đếm với tất cả các giá trị là 0
  Sử dụng vòng lặp for với j = 0 cho tới giá trị của kích thước
    Tìm số đếm tổng của mỗi số tại vị trí d của các phần tử
    Lưu trữ số đếm tại chỉ số thứ j trong mảng đếm
  Sử dụng vòng lặp for với i = 1 cho tới giá trị max
    Tính tổng tích lũy và lưu trữ trong mảng đếm
  Sử dụng vòng lặp for với j = size cho tới giá trị 1
    Khôi phục lại các phần tử thành một mảng
    Giảm số đếm của mỗi phần tử được lưu trữ đi 1 đơn vị

Hàm thực hiện sắp xếp theo cơ số với tham số đầu vào là (mảng cần sắp xếp)

Gán d = số lượng các chữ số trong phần tử lớn nhất

Tạo d khối có kích thước từ 0 tới 9

Sử dụng vòng lặp for với i = 0 cho tới d

Sắp xếp các phần tử dựa theo các chữ số tại vị trí bằng cách sử dụng hàm sắp xếp theo số đếm

Hàm sắp xếp theo số đếm với bộ tham số là (mảng cần sắp xếp, d)

Gán max = tìm phần tử lớn trong các phần tử tại vị trí thứ d

Khởi mảng đếm với tất cả các giá trị là 0

Sử dụng vòng lặp for với j = 0 cho tới giá trị của kích thước

Tìm số đếm tổng của mỗi số tại vị trí d của các phần tử

Lưu trữ số đếm tại chỉ số thứ j trong mảng đếm

Sử dụng vòng lặp for với i = 1 cho tới giá trị max

Tính tổng tích lũy và lưu trữ trong mảng đếm

Sử dụng vòng lặp for với j = size cho tới giá trị 1

Khôi phục lại các phần tử thành một mảng

Giảm số đếm của mỗi phần tử được lưu trữ đi 1 đơn vị

Ví dụ: Triển khai thuật toán sắp xếp dựa theo cơ số bằng ngôn ngữ lập trình C.

#include <stdio.h>

int get_max_element(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++)
    if (arr[i] > max)
      max = arr[i];
  return max;
}

void sort_counting(int arr[], int size, int place) {
  int output[size + 1];
  int max = (arr[0] / place) % 10;

  for (int i = 1; i < size; i++) {
    if (((arr[i] / place) % 10) > max)
      max = arr[i];
  }
  int count[max + 1];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  for (int i = 0; i < size; i++)
    count[(arr[i] / place) % 10]++;
    
  for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];

  for (int i = size - 1; i >= 0; i--) {
    output[count[(arr[i] / place) % 10] - 1] = arr[i];
    count[(arr[i] / place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    arr[i] = output[i];
}

void sort_radix(int arr[], int size) {
  int max = get_max_element(arr, size);
  for (int place = 1; max / place > 0; place *= 10)
    sort_counting(arr, size, place);
}

void print(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", arr[i]);
  }
  printf("\n");
}

int main() {
  int arr[] = {143, 654, 786, 45, 3, 78, 900};
  int n = sizeof(arr) / sizeof(arr[0]);
  sort_radix(arr, n);
  print(arr, n);
}

#include <stdio.h>

int get_max_element(int arr[], int n) {

int max = arr[0];

for (int i = 1; i < n; i++)

if (arr[i] > max)

max = arr[i];

return max;

}

void sort_counting(int arr[], int size, int place) {

int output[size + 1];

int max = (arr[0] / place) % 10;

for (int i = 1; i < size; i++) {

if (((arr[i] / place) % 10) > max)

max = arr[i];

}

int count[max + 1];

for (int i = 0; i < max; ++i)

count[i] = 0;

for (int i = 0; i < size; i++)

count[(arr[i] / place) % 10]++;

for (int i = 1; i < 10; i++)

count[i] += count[i - 1];

for (int i = size - 1; i >= 0; i--) {

output[count[(arr[i] / place) % 10] - 1] = arr[i];

count[(arr[i] / place) % 10]--;

}

for (int i = 0; i < size; i++)

arr[i] = output[i];

}

void sort_radix(int arr[], int size) {

int max = get_max_element(arr, size);

for (int place = 1; max / place > 0; place *= 10)

sort_counting(arr, size, place);

}

void print(int arr[], int size) {

for (int i = 0; i < size; ++i) {

printf("%d ", arr[i]);

}

printf("\n");

}

int main() {

int arr[] = {143, 654, 786, 45, 3, 78, 900};

int n = sizeof(arr) / sizeof(arr[0]);

sort_radix(arr, n);

print(arr, n);

}

Kết quả:

3  45  78  143  654  786  900

1	3 45 78 143 654 786 900

Độ phức tạp của thuật toán

Vì sắp xếp dựa trên cơ số là một thuật toán không so sánh, nó có lợi thế hơn so với các thuật toán sắp xếp so sánh khác.
Đối với sắp xếp dựa theo cơ số sử dụng sắp xếp đếm làm một sắp xếp trung gian, độ phức tạp về thời gian là $O(d(n + k))$
Ở đây, $d$ là số vòng chu kỳ và $O(n + k)$ là độ phức tạp về thời gian của sắp xếp đếm.
Do đó, sắp xếp dựa theo cơ số có độ phức tạp về thời gian tuyến tính tốt hơn $O(n\;log \;n)$ của các thuật toán sắp xếp so sánh.
Nếu chúng ta lấy các số có chữ số rất lớn hoặc số lượng các cơ số khác như số 32 bit và 64 bit thì nó có thể thực hiện trong thời gian tuyến tính tuy nhiên thuật toán sắp xếp trung gian chiếm không gian lớn.
Điều này làm cho không gian sắp xếp dựa trên cơ số là không hiệu quả. Đây là lý do tại sao kiểu sắp xếp này không được sử dụng trong các thư viện phần mềm.

Ứng dụng của sắp xếp dựa trên cơ số

Sắp xếp dựa trên cơ số được triển khai trong:

Thuật toán DC3 (Kärkkäinen-Sanders-Burkhardt) trong khi tạo mảng hậu tố.
Các nơi có các số trong phạm vi lớn.

Trên đây là khái niệm và ví dụ cơ bản về thuật toán sắp xếp dựa trên cơ số. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

P/s: Cảm ơn mọi người đã tin tưởng tek4!

Bài trước: Thuật toán sắp xếp đếm (Counting Sort)

Bài tiếp theo: Bucket Sort (sắp xếp theo khối)

0 0 vote

Article Rating