Ý tưởng thuật toán: Quicksort thuộc loại phương pháp “chia để trị”. Nó thực hiện bằng cách phân hoạch một tập tin thành hai phần, sau đó sắp xếp các phần riêng biệt nhau. Như chúng ta đã biết, vị trí chính xác của các phần được phân hoạch phụ thuộc vào tập tin, vì thế thuật toán có cấu trúc đệ quy như sau:

++

procedure quicksort(l, r: integer);

var i: integer;

begin

if r> l then

begin

i:= partition(l,r);

quicksort(l, i-1);

quicksort(i+1,r);

end;

end;

++

Vấn đề đặt ra là làm thế nào để có thể khử đệ quy trong chương trình Quicksort này? Rất đơn giản, chúng ta có thể khử đệ quy trong chương trình Quicksort bằng cách dùng một ngăn xếp, lúc nào cần một tập tin con để xử lý, chúng ta lại lấy ra khỏi ngăn xếp. Khi phân hoạch, chúng ta tạo hai tập tin con có thể được đẩy vào trong ngăn xếp. Điều này dẫn đến một cài đặt không đệ quy của Quicksort.

++

procedure quicksort;

var t, i, l, r: integer;

begin

l:=1, r:=N;

stackint;

push(l); push(r);

repeat

if r>r then

begin

i:=partition(l,r);

if (i-l) > (r-i) then

begin

push(l); push(i-1); l:=i+1;

end

else begin push(i+1); push(l); r:=i-1; end;

end;

else begin r:=pop; l:= pop end;

until stackempty;

end;

+++

Có thể thấy rằng, chương trình này khác với ý tưởng ban đầu được mô tả ở trên của chúng ta ở hai điểm sau:

+ Thứ nhất, hai tập tin con không đặt trên ngăn xếp theo thứ tự tuỳ ý, nhưng kích thước của chúng sẽ được kiểm tra và tập tin nào có kích thước lớn hơn sẽ được đặt vào trong ngăn xếp trước.

+ Thứ hai là tập tin nào có kích thước nhỏ hơn trong hai tập tin con không được đặt vào ngăn xếp; giá trị của các tham số được khởi động lại.

Đây chính là kỹ thuật “khử đệ quy phần cuối”. Đối với Quicksort, sự tổ hợp giữa kỹ thuật khử đệ quy này và cơ chế xử lý tập tin có kích thước nhỏ hơn bảo đảm là ngăn xếp chỉ cần chỗ trống cho khoảng lgN đầu vào, bởi vì mỗi đầu vào trên ngăn xếp sau đầu vào trên cùng phải đại diện cho một tập tin con có kích thước nhỏ hơn một nửaso với đầu vào phía trước.

Trong trường hợp xấu nhất, điều này lại ngược lại với kích thước của ngăn xếp trong các cài đặt bằng đệ quy có thể lớn bằng N (chẳng hạn khi tập tin đã được sắp). Điều này rất khó đối với cài đặt bằng đệ quy của Quicksort: luôn luôn tồn tại một ngăn xếp nằm dưới, trường hợp tập tin kích thước lớn có thể làm cho chương trình chấm dứt không bình thường vì thiếu bộ nhớ, tình trạng này dĩ nhiên không được cho phép đối với một chương trình sắp xếp trong thư viện. Dưới đây chúng ta sẽ xem xét cách tạo ra các trường hợp suy thoái nhưng muốn né tránh vấn đề này tỏng một cài đặt đệ qui rất khó nếu không dùng kỹ thuật khử đệ qui. (Ngay cả chuyển đổi thứ tự xử lý của các tập tin con cũng không giúp gì hơn.)

Sử dụng thô sơ một ngăn xếp trong chương trình ở trên dẫn đến một chương trình hiệu quả hơn cài đặt đệ qui trực tiếp. Vấn đề là nếu cả hai tập tin con chỉ có một phần tử, một đầu vào với r=lđặt trên ngăn xếp sẽ được lấy ra và huỷ ngay. Vậy phải thay đổi chương trình để cho không có những tập tin như vậy trên ngăn xếp.

Dĩ nhiên phương pháp không đệ quy xử lý những dạng tập tin con giống như phương pháp có đệ qui với bất kỳ tập tin nào, nó chỉ thực hiện các tập tin con này theo thứ tự khác nhau.

School@net (Theo THNT)