Thuật toán sắp xếp

Lại bàn về giải thuật sắp xếp

Tạ Tiến Đạt

Các bạn thân mến!

Hôm nay qua bài viết này tôimuốn đề cập tới một thuật toán sắp xếp ổn định để giải bài

toán mã hóa Burrows (mà hẳn nhiều bạn đã quen thuộc).Nếu bạn nào chưa rõ về bài toán

này có thể tìm đọc số báo tháng11 năm 2001, bài "Lựa chọn giải thuật sắp xếp " của thầy

Nguyễn XuânHuy để rõ hơn.

Sau đây tôisẽ đi ngay vào phân tích thuật toán sắp xếp mà tôi định nói đếnlà Sắp xếp bằng

phép đếm phân phối(Distribution Counting).

Yêu cầu bàitoán là cho một dãy khóa k1, k2..kn (nguyênkhông âm) và đưa ra dãy đã sắp

tăng (hoặc giảm tùy ý)

Giả sử tađã xây dựng được dãy c1, c2..c(n+1) vớiý nghĩa ci là số lần xuất hiện của giá trị i

trong dãy sốban đầu. Dựa vào dãy biến đếm trên ta hoàn toàn có thể suy ra giátrị kj sẽ

thuộc vào đoạn nào trong dãy sau khi sắp xếp. Cụthể sau khi có dãy c ta xây dựng lại nó

như sau:

c0= 0

c1= c0 + c1

c2= c0 + c1 + c2

…

cn= c0 + c1 + c2 +..+ cn

khi đó giátrị i trong dãy ban đầu khi được sắp tăng thì nó sẽ nằm ở đoạn ci-1 + 1 tới ci

và ta dễ dàngsuy ra dãy khóa sau khi sắp tăng dựa vào dãy c này.

Ta có cách cài đặt củathuật toán như sau:

procedureDistributionCounting;

begin

fillchar(c, sizeof(c), 0);

for i := 1 to n do inc(c[k[i]]);

for i := 2 to n do c[i] := c[i-1] + c[i];

for i := n downto 1 do

begin

x[c[k[i]] := k[i]; {x là dãy khóa phụ chứa các giá trị của dãyk sau khi sắp}

dec(c[k[i]]);

end;

end;

Đánhgiá:

- Thuật toáncó độ phức tạp O(Max(M, n)) trong đó M là giá trị lớn nhất trong dãysố ban

đầu, hơn hẳn thuật toán sắp xếp chèn và nổi bọt có độ phứctạp O(n2

).