Sắp xếp bằng đếm phân phối (Counting Sort)

I. Ý tưởng thuật toán

Chúng ta hãy cùng xem xét tình huống sau: Trong giờ Toán tại lớp $1A$, thầy giáo viết lên bảng một dãy số như sau:

$4,2,2,8,3,3,1,2$

Thầy giáo yêu cầu cả lớp hãy sắp xếp dãy số trên theo thứ tự không giảm từ trái qua phải. Cả lớp đều đang loay hoay vì trong bài toán lần này mỗi số không phải chỉ xuất hiện $1$ lần duy nhất như bình thường mà có thể lặp lại. An là một học sinh thông minh, An đưa ra cách xếp độc đáo như sau: Đầu tiên, đếm mỗi số xuất hiện bao nhiêu lần và ghi chúng vào bảng như sau:

Như vậy chỉ cần viết các giá trị lặp lại đúng bằng số lần xuất hiện của chúng thì An sẽ thu được dãy số thỏa mãn yêu cầu của thầy:

$1,2,2,2,3,3,4,8$

Cách làm của An thật độc đáo phải không? Liệu chúng ta có thể áp dụng nó trong Tin học?

II. Chi tiết thuật toán

Vẫn tiếp tục sử dụng dãy số thầy giáo ở trên:

$4,2,2,8,3,3,1,2$

Coi dãy trên là mảng $a[]$ như sau:

Ta để ý rằng mảng trên có số lớn nhất là $8$, khai báo một mảng mới $c[]$ có $9$ phần tử đều nhận giá trị bằng $0$ như sau:

Coi phần tử $c[i]$ đại diện cho số $i$, thực hiện gắn giá trị cho mảng $c[]$ giống với cách làm của An ta thu được bảng sau:

Cuối cùng ta thực hiện sắp xếp lại dãy như sau:

• Cho số $i$ chạy từ $0$ đến $8$, nếu có $c[i]>0$ ta viết số $i$ và giảm $c[i]$ xuống $1$ đơn vị, đến khi nào $c[i]=0$ thì cho $i$ tiếp tục tăng lên $1$ đơn vị, và tiếp tục như vậy.
• Cụ thể, ban đầu tại $i=0$, ta có $c[0]=0$ nên chuyển sang $i=1$, lúc này $c[1]=1>0$ ta viết xuống số $i=1$:
  Dãy số kết quả: $1$
• Sau khi viết xong giảm xuống $c[1]=0$ và tiếp tục chuyển sang $i=2$, ta có $c[2]=3>0$ ta viết tiếp số $i=2$:
  Dãy số kết quả: $1,2$
• Ta giảm xuống $c[2]=2>0$ và tiếp tục viết tiếp số $i=2$:
  Dãy số kết quả: $1,2,2$
• Tương tự như vậy ta thu được dãy số hoàn chỉnh:
  Dãy số kết quả: $1,2,2,2,3,3,4,8$

III. Thuật toán tham khảo

• Ngôn ngữ C++:

#include<iostream>
using namespace std;#defineLENGTH23#defineMAX_ELEMENT13intmain(){int array[LENGTH]={1,12,9,3,6,1,9,3,3,8,8,13,10,4,4,6,5,5,5,12,10,11,9};int count[MAX_ELEMENT+1]={0};for(int i =0; i < LENGTH ; i++){
        count[array[i]]++;}for(int i =0, j=0; i <= MAX_ELEMENT && j < LENGTH ; j++){while(count[j]>0){
            count[j]--;
            array[i++]= j;}}return0;}

• Ngôn ngữ Java:

classCountingSort{voidsort(char arr[]){int n = arr.length;char output[]=newchar[n];int count[]=newint[256];for(int i =0; i <256;++i)
            count[i]=0;for(int i =0; i < n;++i)++count[arr[i]];for(int i =1; i <=255;++i)
            count[i]+= count[i -1];for(int i = n -1; i >=0; i--){
            output[count[arr[i]]-1]= arr[i];--count[arr[i]];}for(int i =0; i < n;++i)
            arr[i]= output[i];}publicstaticvoidmain(String args[]){CountingSort ob =newCountingSort();char arr[]={'g','e','e','k','s','f','o','r','g','e','e','k','s'};
 
        ob.sort(arr);System.out.print("Sorted character array is ");for(int i =0; i < arr.length;++i)System.out.print(arr[i]);}}

• Ngôn ngữ PHP:

<?php$RANGE=255;functioncountSort($arr){global$RANGE;$output=array(strlen($arr));$len=strlen($arr);$count=array_fill(0,$RANGE+1,0);for($i=0;$i<$len;++$i){++$count[ord($arr[$i])];}for($i=1;$i<=$RANGE;++$i){$count[$i]+=$count[$i-1];}for($i=$len-1;$i>=0;$i--){$output[$count[ord($arr[$i])]-1]=$arr[$i];--$count[ord($arr[$i])];}for($i=0;$i<$len;++$i){$arr[$i]=$output[$i];}return$arr;}$arr="geeksforgeeks";//"applepp";$arr=countSort($arr);echo"Sorted character array is ".$arr;?>

Xung quanh thuật toán sắp xếp bằng đếm phân phối

1. Ưu điểm

• Ý tưởng đơn giản, dễ hiểu.
• Đoạn code dễ nhớ, gần gũi với người mới học về sắp xếp.

2. Nhược điểm

• Cần tìm dữ kiện lớn nhất trong dãy.
• Chưa phù hợp với các trường hợp dãy số lớn.

V. Tài liệu tham khảo

• https://vi.wikipedia.org/wiki/Sắp_xếp_đếm_phân_phối
• https://en.wikipedia.org/wiki/Counting_sort