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

Thuật toán sắp xếp 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...ping Các chữ số riêng lẻ của các phần tử cần được sắp xếp. Sau đó, một kỹ thuật sắp xếp ổn định được sử dụng để tổ chức 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ử đó. Điều này cho biết số lần lặp mà quá trình sắp xếp thực hiện.
• Nhómping các chữ số riêng lẻ của các phần tử ở cùng vị trí có nghĩa trong mỗi lần lặp.
• Nhómping Quá trình này bắt đầu từ chữ số có ý nghĩa thấp nhất và kết thúc ở chữ số có ý nghĩa cao nhất.
• Sắp xếp các phần tử dựa trên 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 Radix Sort làm cho nó trở thành một thuật toán sắp xếp ổn định.

Lần lặp cuối cùng trả về 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ố

Danh sách các số nguyên cần sắp xếp

Chúng ta hãy 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 theo cơ số:

Bước 1) Xác định phần tử lớn nhất trong danh sách. Ở đây, đó là 835.

Bước 2) Hãy đếm các chữ số của nó. 835 có 3 chữ số, vậy số lần lặp là 3.

Bước 3) Xác định cơ số. Vì đây là số thập phân, nên cơ số là 10.

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

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

Sắp xếp theo chữ số cuối cùng

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) Lấy phần dư của số nguyên chia cho 10 để tìm chữ số hàng đơn vị của các phần tử. Ví dụ, 623 chia cho 10 được 3, và 248 chia cho 10 được 8.

Bước 2) Sử dụng thuật toán sắp xếp đếm hoặc một thuật toán sắp xếp ổn định khác để sắp xếp các số nguyên theo chữ số có trọng số thấp nhất. Từ hình vẽ, 248 thuộc nhóm thứ 8, 623 thuộc nhóm thứ 3, v.v.

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

Danh sách sau lần lặp đầu tiên

Danh sách này chưa được sắp xếp và cần thêm các bước xử lý nữa.

b) Lần lặp thứ hai

Sắp xếp dựa trên chữ số hàng chục

Trong lần lặp này, chúng ta xem xét chữ số hàng chục trong quá trình sắp xếp.

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

Bước 2) Lấy phần dư của kết quả Bước 1 chia cho 10. 24 chia cho 10 ta được 4.

Bước 3) Hãy làm theo Bước 2 từ lần thực hiện trước.

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

Danh sách sau lần lặp thứ hai

Danh sách vẫn chưa được sắp xếp hoàn toàn vì chưa được sắp xếp theo thứ tự tăng dần.

c) Lần lặp thứ ba

Sắp xếp dựa trên chữ số hàng trăm

Ở bước lặp cuối cùng, chúng ta muốn lấy chữ số quan trọng nhất. Trong trường hợp này, đó là chữ số hàng trăm của mỗi số nguyên trong danh sách.

Bước 1) Chia các số nguyên cho 100. Ví dụ, 415 chia cho 100 được 4.

Bước 2) Lấy phần dư của kết quả từ Bước 1 chia cho 10. 4 chia cho 10 bằng 4.

Bước 3) Hãy làm theo Bước 3 từ lần thực hiện trước.

Danh sách sau lần lặp thứ ba

Danh sách hiện đã được sắp xếp theo thứ tự tăng dần. Vòng lặp cuối cùng đã hoàn tất 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ả của thuật toán sắp xếp Radix:

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 jth 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 in the jth place
    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 integer
    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 in 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

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

Đầu ra:

[162, 248, 415, 623, 835]

Phân tích độ phức tạp của thuật toán sắp xếp Radix

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 không gian: Độ phức tạp 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 về 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 đặc điểm cần tập trung vào để đánh giá độ phức tạp của không gian:

• Số phần tử trong mảng, n.
• Phần đế được sử dụng để đại diện cho các yếu 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 đặc tính sau của các phần tử trong danh sách có thể khiến thuật toán Radix Sort trở nên kém hiệu quả về mặt không gian:

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

Sử dụng thuật toán sắp xếp đếm làm chương trình con, mỗi lần lặp mất... 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” biểu thị hàm độ phức tạp.

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

Thuật toán Radix Sort 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 đáng kể so với n.

So sánh thuật toán Radix Sort với các thuật toán sắp xếp khác Algorithms

Độ phức tạp của thuật toán Radix Sort phụ thuộc vào kích thước của số. Trường hợp tốt nhất và trường hợp trung bình đều là O(d * (n + b)). Hiệu suất thay đổi tùy thuộc vào thuật toán sắp xếp bên trong — sắp xếp đếm là thuật toán chuẩn, nhưng bất kỳ thuật toán sắp xếp ổn định nào cũng hoạt động được.

Ứ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 thuật toán sắp xếp theo cơ số (Radix Sort) bao gồm:

• Thuật toán Radix Sort có thể được sử dụng như một thuật toán tìm vị trí khi xử lý các 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 các máy truy cập ngẫu nhiên tuần tự, nơi các bản ghi được mã hóa bằng các định danh có độ rộng cố định.

Câu Hỏi Thường Gặp