STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

    Distribution Sort - Counting Sort

    Distribution Sort - Counting Sort là sắp xếp bằng phép đếm phân phối. Đây là một thuật toán sắp xếp đơn giản cho trường hợp đặc biệt, các giá trị trong mảng cần sắp xếp đều là số nguyên và biết được giá trị của mảng nằm trong khoảng nào đó.
    23/04/2017 18/08/2020 3 phút đọc
    Distribution Sort - Counting Sort

    Counting Sort là 1 thuật toán sắp xếp bằng phép đếm phân phối (Distribution Counting Sort), đây là một trong những thuật toán sắp xếp rút ngắn được thời gian của quá trình thực hiện thuật toán.

    Thuật toán Counting Sort

    Counting Sort - Sắp xếp bằng phép đếm phân phối là 1 trong những giải thuật sắp xếp thuộc nhóm Distribution Sort. Đây là một thuật toán sắp xếp đơn giản cho trường hợp đặc biệt các giá trị trong mảng cần sắp xếp đều là số nguyên và biết được giá trị của mảng nằm trong khoảng nào đó. Ví dụ như [0..M], [3..N], …

    Ý tưởng

    Cho mảng cần sắp xếp các giá trị của mảng đều là số nguyên và thuộc khoảng [0..M].

    Ý tưởng của thuật toán là đếm trong khoảng [0..M]:

    • Có bao nhiêu giá trị 0 (giả sử có C(0) giá trị).
    • Có bao nhiêu giá trị 1 (giả sử có C(1) giá trị),
    • Có bao nhiêu giá trị M (giả sử có C(M) giá trị).

    Sau đó sắp xếp lại mảng bằng cách đặt C(0) phần tử 0 ở đầu, đặt C(1) phần tử 1 tiếp theo, … và đặt C(M) phần tử M cuối cùng.

    Độ phức tạp của thuật toán này là O(max(N, M)). Giá trị của M càng nhỏ thì thuật toán sắp sếp càng nhanh.

    Ví dụ

    Cho dãy cần sắp xếp: 1, 4, 2, 7, 8, 2, 1, 3, 8, 6, 2, 4

    Thì: C(1) = 2, C(2) = 3, C(3) = 1, C(4) = 2, C(6) = 1, C(7) = 1, C(8) = 2

    • Giá trị 1 đứng ở vị trí từ 1 → C(1), tức là từ 1 → 2.
    • Giá trị 2 đứng ở vị trí từ C(1) + 1 → C(1) + C(2), tức là từ 3 → 5.
    • ...
    • Tương tự giá trị i đứng ở vị trí từ C(1) + C(2) + C(3) + … + C(i - 1) + 1 → C(1) + C(2) + C(3) + … + C(i - 1) + C(i).

     Vậy dãy sau khi sắp xếp: 1 1 2 2 2 3 4 4 6 7 8 8

    Hiện thực

    void countingSort(int* input, int n)
    {
        int countArr[SIZE] = { 0 };
     
        for (int i = 0; i < n; i++)
            countArr[input[i]]++;
     
        int outputIndex = 0;
    
        for (int j = 0; j < SIZE; j++)
            while (countArr[j]-- > 0)
                input[outputIndex++] = j;
    }

    Giải thích

    Đếm số lần xuất hiện của mỗi phần tử.

    for (int i = 0; i < INPUT_SIZE; i++)
        countArr[input[i]]++;

    Sắp xếp lại dãy theo thuật toán.

    for (int j = 0; j < SIZE; j++)
        while (countArr[j]-- > 0)
            input[outputIndex++] = j;

    Code mẫu Counting Sort

    #include <iostream>
    using namespace std;
    const int INPUT_SIZE = 20; const int SIZE = 20; void printArray(int *input, int n) { for (int i = 0; i < n; i++) cout << input[i] << "\t"; } void countingSort(int* input, int n) { int countArr[SIZE] = { 0 }; for (int i = 0; i < n; i++) countArr[input[i]]++; int outputIndex = 0; for (int j = 0; j < SIZE; j++) while(countArr[j]-- < 0) input[outputIndex++] = j; } int main() { int input[INPUT_SIZE] = { 2, 4, 6, 4, 7, 1, 4, 9, 5, 3, 7, 2, 2, 6, 9, 3, 7, 3, 4, 4 }; printArray(input, INPUT_SIZE); countingSort(input, INPUT_SIZE); printArray(input, INPUT_SIZE); return 0; }

    Bài chung Series

    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021