+6

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 1A1A, thầy giáo viết lên bảng một dãy số như sau:

4,2,2,8,3,3,1,24, 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 11 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,81, 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,24, 2, 2, 8, 3, 3, 1, 2

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

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

Coi phần tử c[i]c[i] đại diện cho số ii, thực hiện gắn giá trị cho mảng c[ ]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ố ii chạy từ 00 đến 88, nếu có c[i]>0c[i]>0 ta viết số ii và giảm c[i]c[i] xuống 11 đơn vị, đến khi nào c[i]=0c[i]=0 thì cho ii tiếp tục tăng lên 11 đơn vị, và tiếp tục như vậy.
  • Cụ thể, ban đầu tại i=0i=0, ta có c[0]=0c[0]=0 nên chuyển sang i=1i=1, lúc này c[1]=1>0c[1]=1>0 ta viết xuống số i=1i=1: Dãy số kết quả: 11
  • Sau khi viết xong giảm xuống c[1]=0c[1]=0 và tiếp tục chuyển sang i=2i=2, ta có c[2]=3>0c[2]=3>0 ta viết tiếp số i=2i=2: Dãy số kết quả: 1,21, 2
  • Ta giảm xuống c[2]=2>0c[2]=2>0 và tiếp tục viết tiếp số i=2i=2: Dãy số kết quả: 1,2,21, 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,81, 2, 2, 2, 3, 3, 4, 8

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

  • Ngôn ngữ C++:
#include<iostream>
using namespace std;
#define LENGTH 23
#define MAX_ELEMENT 13
int main()
{
    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;
        }
    }


    return 0;
}
  • Ngôn ngữ Java:
class CountingSort {
    void sort(char arr[])
    {
        int n = arr.length;
        char output[] = new char[n];
        int count[] = new int[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];
    }
    public static void main(String args[])
    {
        CountingSort ob = new CountingSort();
        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;
    function countSort($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


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí