Thuật toán sắp xếp cơ số trong cấu trúc dữ liệu

Thuật toán sắp xếp cơ số là gì?

Radix Sort là một thuật toán sắp xếp không so sánh. Nó hoạt động bằng cách nhóm các chữ số riêng lẻ của các phần tử cần sắp xếp. Sau đó, một kỹ thuật sắp xếp ổn định được sử dụng để sắp xếp các phần tử dựa trên cơ số của chúng. Đó là một thuật toán sắp xếp tuyến tính.

Quá trình phân loại bao gồm các tính chất sau:

Tìm phần tử lớn nhất và lấy số chữ số của phần tử đó. Nó cho chúng ta số lần lặp mà quá trình sắp xếp sẽ tuân theo.
Nhóm các chữ số riêng lẻ của các phần tử ở cùng một vị trí quan trọng trong mỗi lần lặp.
Quá trình nhóm sẽ bắt đầu từ chữ số có nghĩa nhỏ nhất và kết thúc ở chữ số có nghĩa nhất.
Sắp xếp các phần tử dựa trên các chữ số tại vị trí quan trọng đó.
Duy trì thứ tự tương đối của các phần tử có cùng giá trị khóa. Thuộc tính này của sắp xếp cơ số làm cho nó trở thành một sắp xếp ổn định.

Lần lặp cuối cùng sẽ cho chúng ta một danh sách được sắp xếp hoàn chỉnh.

Hoạt động của thuật toán sắp xếp cơ số

Hãy thử sắp xếp danh sách các số nguyên trong hình trên theo thứ tự tăng dần bằng thuật toán Radix Sort.

Dưới đây là các bước để thực hiện quy trình Sắp xếp Cơ số:

Bước 1) Xác định phần tử có giá trị lớn nhất trong danh sách. Trong trường hợp này, nó là 835.

Bước 2) Tính số chữ số của phần tử lớn nhất. 835 có đúng 3 chữ số.

Bước 3) Xác định số lần lặp dựa vào bước 2. 835 có 3 chữ số, nghĩa là số lần lặp sẽ là 3.

Bước 4) Xác định cơ sở của các phần tử. Vì đây là hệ thập phân nên cơ số sẽ là 10.

Bước 5) Bắt đầu lần lặp đầu tiên.

a) Lần lặp đầu tiên

Trong lần lặp đầu tiên, chúng tôi xem xét giá trị vị trí đơn vị của từng phần tử.

Bước 1) Sửa số nguyên thêm 10 để lấy vị trí đơn vị của các phần tử. Ví dụ: 623 mod 10 cho chúng ta giá trị 3 và 248 mod 10 cho chúng ta giá trị 8.

Bước 2) Sử dụng phương pháp sắp xếp đếm hoặc bất kỳ phương pháp sắp xếp ổn định nào khác để sắp xếp các số nguyên theo chữ số có nghĩa nhỏ nhất của chúng. Như đã thấy Từ hình vẽ, 248 sẽ rơi vào thùng thứ 8. 623 sẽ rơi vào thùng thứ 3, v.v.

Sau lần lặp đầu tiên, danh sách bây giờ trông như thế này.

Như bạn có thể thấy trong hình trên, danh sách chưa được sắp xếp và cần phải lặp lại nhiều lần để được sắp xếp đầy đủ.

b) Lần lặp thứ hai

Trong lần lặp này, chúng ta sẽ xem xét chữ số ở số 10^th nơi thực hiện quá trình phân loại.

Bước 1) Chia các số nguyên cho 10. 248 chia cho 10 được 24.

Bước 2) Sửa đổi đầu ra của bước 1 x 10. 24 mod 10 cho chúng ta 4.

Bước 3) Thực hiện theo bước 2 từ lần lặp trước.

Sau lần lặp thứ hai, danh sách bây giờ trông như thế này

Bạn có thể thấy từ hình trên rằng danh sách vẫn chưa được sắp xếp hoàn toàn vì nó chưa theo thứ tự tăng dần.

c) Lần lặp thứ ba

Đối với lần lặp cuối cùng, chúng tôi muốn lấy chữ số có ý nghĩa nhất. Trong trường hợp này là 100^thvị trí cho mỗi số nguyên trong danh sách.

Bước 1) Chia các số nguyên cho 100… 415 chia cho 100 được 4.

Bước 2) Sửa đổi kết quả từ bước 1 đến 10. 4 mod 10 lại cho chúng ta 4.

Bước 3) Thực hiện theo bước 3 từ lần lặp trước.

Như chúng ta có thể thấy, danh sách hiện được sắp xếp theo thứ tự tăng dần. Lần lặp cuối cùng đã được hoàn thành và quá trình sắp xếp đã kết thúc.

Mã giả của thuật toán sắp xếp cơ số

Đây là mã giả cho Thuật toán sắp xếp cơ số

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the j^th place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the j^thplace
   arr = sorted elements

C++ Chương trình thực hiện sắp xếp cơ số

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Đầu ra:

162 248 415 623 835

Python Chương trình cho thuật toán sắp xếp cơ số

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Đầu ra:

[162,248,415,623,835]

Phân tích độ phức tạp của Radix Sort

Có hai loại độ phức tạp cần xem xét: độ phức tạp về không gian và độ phức tạp về thời gian.

Độ phức tạp về không gian: O(n+b) trong đó n là kích thước của mảng và b là cơ sở được xem xét.
Độ phức tạp thời gian: O(d*(n+b)) trong đó d là số chữ số của phần tử lớn nhất trong mảng.

Độ phức tạp không gian của thuật toán sắp xếp theo cơ số

Hai tính năng cần tập trung vào để có không gian phức tạp

Số phần tử trong mảng, n.
Cơ sở biểu diễn các phần tử b.

Đôi khi cơ sở này có thể lớn hơn kích thước của mảng.

Do đó, độ phức tạp tổng thể là O(n+b).

Các thuộc tính sau đây của các phần tử trong danh sách có thể làm cho không gian sắp xếp cơ số trở nên kém hiệu quả:

Các phần tử có số lượng chữ số lớn.
Cơ sở của các phần tử lớn, giống như số 64 bit.

Độ phức tạp thời gian của thuật toán sắp xếp theo cơ số

Bạn có thể sử dụng tính năng sắp xếp đếm như một chương trình con vì mỗi lần lặp sẽ mấte O(n+b) thời gian. Nếu tồn tại d lần lặp, tổng thời gian chạy sẽ trở thành O(d*(n+b)). Ở đây, “O” có nghĩa là hàm phức tạp.

Độ tuyến tính của sắp xếp cơ số

Sắp xếp cơ số là tuyến tính khi

d là hằng số, trong đó d là số chữ số của phần tử lớn nhất.
b không lớn hơn nhiều so với n.

So sánh Radix Sort với các thuật toán so sánh khác

Như chúng ta đã thấy, độ phức tạp của Radix sort dựa trên kích thước của một từ hoặc số. Nó sẽ có cùng độ phức tạp đối với trường hợp trung bình và trường hợp tốt nhất. Và đó là O(d*(n+b)). Ngoài ra, nó khác nhau tùy theo kỹ thuật sắp xếp mà bạn sử dụng ở giữa. Ví dụ, bạn có thể sử dụng sắp xếp đếm hoặc sắp xếp nhanh cho thuật toán sắp xếp trung gian bên trong Radix sort.

Ứng dụng của thuật toán sắp xếp cơ số

Các ứng dụng quan trọng của Radix Sort là:

Sắp xếp cơ số có thể được sử dụng làm thuật toán tìm vị trí trong đó sử dụng phạm vi giá trị lớn.
Nó được sử dụng để xây dựng một mảng hậu tố trong thuật toán DC3.
Nó được sử dụng trong máy truy cập ngẫu nhiên, tuần tự có trong một máy tính thông thường nơi các bản ghi được khóa.

Bạn có thể thích: