Sắp xếp là một trong những thuật toán mà bất kì lập trình viên nào cũng phải trải qua trong quá trình học tập của mình. Trong số đó DISTRIBUTION COUNTING SORT – Sắp xếp bằng phép đếm phân phối là một trong những thuật toán hay rút ngắn được thời gian của quá trình thực hiện thuật toán.
Data Structure & Algorithm Tran Khanh Nguyen 2015-12-09 08:39:12

Giới thiệu

Sắp xếp là một trong những thuật toán mà bất kì lập trình viên nào cũng phải trải qua trong quá trình học tập của mình. Trong số đó DISTRIBUTION COUNTING SORT – Sắp xếp bằng phép đếm phân phối là một trong những thuật toán hay rút ngắn được thời gian của quá trình thực hiện thuật toán.

Code demo của bài viết được tôi thực hiện trên nền Visual Studio 2012 Ultimate.

Khái niệm

Distribution Counting Sort – 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. Trường hợp đặc biệt ở đây là 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 dãy nằm trong khoảng nào đó. Ví dụ như [0..M], [3..N],…

Ý tưởng

Giả sử tôi 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ị), 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 đó tôi sắp xếp lại mảng bằng cách đặt C(0) phần tử 0 ở đầu, tiếp theo đặ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

Ta có: 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í cừ 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 CountArr[M] = { 0 };
 
    for (int i=0;i<INPUT_SIZE;i++)
    {
        CountArr[Input[i]]++;
    }
 
    int OutputIndex=0;
    for (int j=0;j<M;j++)
    {
        while (CountArr[j]-- > 0)
            Input[OutputIndex++] = j;
    }
 
}
  • Dòng 3: Khởi tạo mảng M phần tử và gán tất cả các giá trị của mảng bằng 0 ( với M là giá trị của phần tử lớn nhất ).
  • Dòng 5 -> 8: Đếm số lần xuất hiện của mỗi phần tử.
  • Dòng 10 -> 15: Sắp xếp lại dãy theo thuật toán.

Download Demo

CountingSort_Demo.zip