Thuật toán sắp xếp đếm phân phối

Sắp xếp đếm phân phối là một phương pháp sắp xếp có độ phức tạp tuyến tính. Nó dựa trên giả thiết rằng, các khoá cần sắp xếp là các số tự nhiên giới hạn trong một khoảng nào đó, chẳng hạn từ 1 đến N.

Ý tưởng thuật toán:

Bước 1:
Trong bước đầu tiên, chúng tôi đếm số lần xuất hiện của từng phần tử trong mảng cần sắp xếp A. Kết quả được lưu vào mảng C.
Bước 2: Ở bước này, chúng ta cần xem xét sửa đổi giá trị của C. C[i] thể hiện giới hạn trên của chỉ số của phần tử i sau khi sắp xếp.
Bước 3: Duyệt qua từng phần tử của A và đặt nó vào đúng chỉ số của mảng chứa các giá trị đã sắp xếp B dựa vào C.
Cài đặt thuật toán sử dụng ngôn ngữ lập trình C

#include <stdio.h>

// Function that sort the given input
void counting_sort(int input[], int n)
{
    int output[n]; // The output will have sorted input array
    int max = input[0];
    int min = input[0];

    int i;
    for(i = 1; i < n; i++)
    {
        if(input[i] > max)
            max = input[i]; // Maximum value in array
        else if(input[i] < min)
            min = input[i]; // Minimum value in array
    }

    int k = max - min + 1; // Size of count array

    int count_array[k]; // Create a count_array to store count of each individual input value
    for(i=0; i<k; i++)
        count_array[i]=0;

    for(i = 0; i < n; i++)
        count_array[input[i] - min]++; // Store count of each individual input value

    /* Change count_array so that count_array now contains actual
     position of input values in output array */
    for(i = 1; i < k; i++)
        count_array[i] += count_array[i - 1];

    // Populate output array using count_array and input array
    for(i = 0; i < n; i++)
    {
        output[count_array[input[i] - min] - 1] = input[i];
        count_array[input[i] - min]--;
    }

    for(i = 0; i < n; i++)
        input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values

}


// Driver program to test above function
int main()
{
    int n = 9, i;

    int input[] = {1, 5, 2, 7, 3, 4, 4, 1, 5};

    counting_sort(input, n);

    printf("Sorted Array : ");
    for(i = 0; i < n; i++)
        printf("%d ", input[i]);

    return 0;
}

Kết quả

Sorted Array : 1  1  2  3  4  4  5  5  7