StarGhost
18-04-2005, 19:35
(Bài viết tham khảo từ bài viết trong Dr. Dobb’s Journal về Flash Sort vào tháng 2 1998)
Thấy mọi người có vẻ ít quan tâm đến các thuật toán sắp xếp, tôi mạn phép nói một chút về cái này - một trong những công cụ hay trong lập trình thuật toán. (Nếu bài toán này đã xuất hiện đâu đó trên ddth thì các mod cứ việc del, tui thì không hay dò tìm xét hỏi trong này lắm)
Như các bạn đã biết, cho đến ngày nay, để giải một bài toán phức tạp, trong hầu hết các trường hợp, người ta chia bài toán đó ra làm các bài toán nhỏ hơn đã được giải bằng các thuật toán cho trước, chỉ có một số ít là sáng tác (đúng hơn là phát minh) một thuật toán mới cho bài toán đó và bài toán đó sẽ trở thành bài toán cơ bản. Phương pháp thứ hai thì hơi khó, thường dành cho các nhà nghiên cứu nhiều hơn.
Còn về phương pháp thứ nhất, tôi xin nói đến một trong những vấn đề cơ bản nhất mà các bài toán về quản lý dữ liệu đòi hỏi, đó là sắp xếp dữ liệu. Như nhiều (thậm chí hầu hết) các bạn đã biết, phổ biến trên thế giới hiện nay là một số các thuật toán điển hình như Bubble sort, Insertion Sort, Shell Sort với độ phức tạp O(n2), hay nhanh hơn và cũng khó hơn là Quick Sort, Heap Sort với độ phức tạp O(n ln(n)). Có lẽ tôi cũng không cần phải nói nhiều về ý tưởng của các thuật toán này vì các bạn đã biết quá rõ rồi.
Bây giờ tôi xin trình bày một thuật toán mới (cũng không phải mới lắm, hình như là từ năm chín mấy ấy, không nhớ nữa) với một ý tưởng hoàn toàn mới, đi ngược lại với ý tưởng chính của tất cả các thuật toán trước đó và quan trọng nhất: LÀ THUẬT TOÁN NHANH NHẤT CÓ THỂ (ĐẠT ĐẾN TỐC ĐỘ TỚI HẠN). Thuật toán này có tên là FLASH SORT, được phát minh bới 1 guy named Karl-Dietrich Neubert .
Như các bạn có thể nhận thấy dễ dàng từ các thuật toán trước, mỗi khi muốn đổi chỗ 2 phần từ bất kỳ nào đó của mảng, các bạn đều phải dùng câu lệnh IF (một số ngôn ngữ diễn tả câu lệnh khác) để so sánh giá trị của 2 phần tử đó. Chính vì vậy, tôi có thể nói là ý tưởng chính của các thuật toán trước đây là dựa trên so sánh phần tử (Elements Comparison - EC). Bây giờ nói đến Flash sort, mặc dù trong thuật toán có sử dụng EC nhưng ý tưởng chính lại là phân lớp các phần tử (Subclasses Arrangement - SA).
Bây giờ tôi đi vào chi tiết hơn. Toàn bộ quá trình xử lý của thuật toán này được chia làm 3 giai đoạn (không kể giai đoạn nhập dữ liệu và in kết quả) bao gồm 2 giai đoạn phân lớp và 1 giai đoạn sắp xếp. Ta có mảng dữ liệu A[0..n]
1. Phân loại các phần tử (Elements Classification):
Như đã nói, ý tưởng chính là phân lớp, vì thế đây là giai đoạn chuẩn bị cho việc phân lớp (giống như procedure Ready trong cái form bài giải của mấy người thi đội tuyển tin học ấy, ^_^). Các yếu tố cần thiết để ready là:
- Số phân lớp m
- Một mảng m ghi vị trí của bắt đầu của mỗi phân lớp
Vấn đề 1: Xác định giá trị phần tử nhỏ nhất (minval) và vị trí phần tử lớn nhất (nmax) -> duyệt O(n)
Vấn đề 2: Để xác định xem phần tử nào thuộc phân lớp nào, ta dùng công thức sau:
K[i]=1+Floor[ (m-1)(A[i]-minval)(A[nmax]-minval) ]
Từ công thức trên, K[i] sẽ cho biết phân lớp chứa phần tử I của mảng A. Nhìn kỹ một chút, các bạn sẽ thấy là giá trị của K sẽ nằm trong khoảng [1,m]. Các bạn nhớ dùng hàm Floor chứ đừng dùng hàm Round, vì giá trị có thể sẽ bị sai lệch, Floor luôn cho giá trị nguyên gần nhất thấp hơn giá trị thực (trong Pascal bạn có thể dùng div).
Vấn đề 3: Ta lập một mảng L ghi vị trí xuất phát của các phân lớp trong mảng A. Ta tưởng tượng (imagine) một qui tắc rằng: một phân lớp I được coi là đã đầy khi mà L[I] nằm đúng ở vị trí xuất phát của phân lớp đó trong mảng A. Chính vì vậy ta coi như một phân lớp là rỗng khi nó nằm ở vị trí cuối của vị trí chính xác của nó trong phân lớp A, để mỗi khi ta bỏ một phần tử vào phân lớp đó, ta lùi L[I] lại 1 cho đến khi về đến đúng vị trí của nó thì nghĩa là đầy. Vậy để xác định được vị trí xuất phát cũng như vị trí kết thúc của từng phân lớp, ta phải biết được kích thước của từng phân lớp. Sau đó, để coi như các phân lớp là rỗng, vị trí bắt đầu của mỗi phân lớp phải nằm ở vị trí lẽ ra là kết thúc của nó trong mảng A. Vậy ta có công thức sau:
L[I]=L[I-1]+ kích thước của lớp I
Từ trên ta suy ra, vị trí ban đầu của phân lớp 1 sẽ là kích thước của nó, còn của phân lớp m sẽ là n (số phần tử).
2. Hoán vị các phần tử (Elements Permutation):
Sau khi đã sẵn sàng, chúng ta bắt đầu việc sắp xếp các phần tử vào đúng phân lớp của nó. Việc này sẽ hình thành các chu trình hoán vị: mỗi khi ta đem một phẩn tử ở đâu đó đến một vị trí nào đó thì ta phải nhấc phần tử hiện tại đang chiếm chỗ ra, và tiếp tục với phần tử bị nhấc ra và đưa đến chỗ khác cho đến khi quay lại vị trí ban đầu thì hoàn tất vòng lặp.
Vấn đề 1: Vậy làm thế nào để khi cầm trong tay 1 phần tử nào đó, ta biết phải bỏ nó vào chỗ nào cho phù hợp? Câu trả lời thật đơn giản, ta tính xem nó phải nằm ở phân lớp nào, rồi bỏ nó vào cái vị trí hiện tại của phân lớp đó, và vì ta bỏ vào phân lớp đó 1 phần tử nên phải lùi vị trí của phân lớp lại 1 đơn vị.
Vấn đề 2: Mặc dù ta đã đi qua 1 chu trình nhưng vẫn còn những phần tử chưa ở đúng chỗ thì phải làm thế nào? Cũng đơn giản, tiến hành 1 chu trình khác cho đến khi không còn con thỏ nào trong chuồng bò và ngược lại nữa thì thôi.
Vấn đề 3: Vậy là ta có một số các chu trình cần phải xử lý, vậy tại mỗi chu trình ta phải bắt đầu từ phần tử nào của mảng (Cycle leaders searching)? Đây cũng là một trong những điều đơn giản: ta chỉ việc duyệt từ đầu đến cuối mảng và tìm xem phần tử nào không nằm trong phân lớp (I<L[K[I]]), và bắt đầu bằng phần tử đó.
3. Sắp xếp các phần tử trong từng phân lớp theo đúng thứ tự (Elements Ordering)
Phù, đến đây thì mọi việc dường như trở nên quá đơn giản rồi, hai giai đoạn trên đã giúp chúng ta chia nhỏ 1 mảng to thành nhiều mảng nhỏ để việc sắp xếp trở nên nhanh hơn.
Vấn đề duy nhất: Chọn thuật toán nào để sắp xếp các phân lớp? Câu trả lời cho vấn đề này tương đối khó, nhưng nếu các bạn tính toán 1 chút, các bạn sẽ thấy rằng Straight-Insertion Sort là lựa chọn tối ưu vì chỉ có nó mới thực sự chia nhỏ mảng A ra các phân lớp và sắp xếp từng phân lớp.
4. Cài đặt (Installation)
Như vậy, tôi đã trình bày xong toàn bộ quá trình xử lý của thuật toán FLASH SORT. Dưới đây là cách cài đặt chương trình bằng PASCAL (nếu các bạn có Free Pascal thì càng tốt vì có thể thử nghiệm với mảng lớn):
Const
N=;
M=;
Var
L: array[1..m] of Integer;
A: array[1..n] of Integer;
Minval, nmax, nho, ban_dau: integer;
Program Flash_sort;
Procedure Ready;
Var i: integer;
Begin
For i:=1 to n do
A[i]:=Random(n*2);
End;
Procedure Classification;
Var
hang_so: integer;
i: integer;
Begin
Nmax:=1;
Minval:=A[1];
For i:=1 to n do
Begin
If (A[i]>A[nmax]) then nmax:=I;
If (Minval<A[i]) then Minval:=A[i];
End;
Hang_so:= (m-1)/(A[nmax]-Minval);
For i:=1 to n do
Inc(L[1+Trunc((A[i]-Minval )*Hang_so)]);
For i:=2 to m do
L[i]:=L[i-1]+L[i];
Nho:=A[nmax];
A[nmax]:=A[1];
A[1]:=nho;
End;
Procedure Permutation;
Var
Dem, I, k: integer;
Begin
Dem:=0;
I:=1;
K:=m;
While (dem<(n-1)) do
Begin
While (i>L[k]) do
Begin
Inc(i);
K:=1+Trunc((A[i]-minval)*hang_so);
End;
Bandau:=A[i];
While (i<>L[k]+1) do
Begin
K:=1+Trunc((bandau-minval)*hang_so);
Nho=A[L[k]];
A[L[k]]:=bandau;
Bandau:=nho;
Dec(L[k]);
Inc(dem);
End;
End;
Procedure Straight_Insertion_Sort;
Var
I,j: integer;
Begin
For i:=n-2 downto 1 do
If (A[i+1]<A[i]) then
Begin
Nho:=A[i];
J:=I;
While (A[j+1]<nho)
Begin
A[j]:=A[j+1];
Inc(j);
End;
A[j]:=nho;
End;
End;
Begin
Ready;
Classification;
Permutation;
Straight_Insertion_Sort;
End.
Chương trình trên sở dĩ tôi viết bằng PASCAL là vì tôi cho rằng đây là ngôn ngữ phổ biến nhất dùng trong việc học lập trình thuật toán, sẽ dễ dàng hơn cho việc đọc, hiểu (vì sử dụng modules) và translate ra các ngôn ngữ khác. Tuy nhiên vì máy tôi không có PASCAL nên mới chỉ là Primary version, chưa test được, nếu bạn nào dùng mà thấy lỗi thì cố gắng sửa hoặc không thì post lỗi lên rồi tôi sửa cũng được.
5. Thời gian chạy (Running time complexity)
Nhìn lại toàn bộ các giai đoạn của thuật toán, ta thấy như sau:
- Giai đoạn Classification đòi hỏi độ phức tạp O(n) và O(m)
- Giai đoạn Permutation đòi hỏi độ phức tạp O(n) ( vì mỗi phần tử chỉ phải đổi chỗ đúng một lần, và n lần cho n phần tử)
- Giai đoạn Straight_Insertion_Sort đỏi hỏi độ phức tạp O(n2/m) ( mỗi 1 phân lớp đòi hỏi độ phức tạp O((n/m)2) và m phân lớp đòi hỏi O(m*(n/m)2) )
Vấn đề ở đây là làm sao chọn số phân lớp để cho thời gian tối ưu. Ta có công thức tính độ phức tạp tổng cộng cho toàn bộ quá trình là :
F(m)= a1*n+a2*m+a3*n2/m.
F’(m)=a2-a3(n/m)2=0 => m=n*(a3/a2)1/2.
Theo một số khảo sát dưạ trên nghiên cứu về tốc độ chạy của chương trình (của một số nhà nghiên cứu), a2 xấp xỉ 2 và a3 xấp xỉ 3/8, như vậy ta có m xấp xỉ 0.43n là số phân lớp tối ưu đề cho thời gian chạy nhanh nhất. Tuy nhiên đây chỉ là con số dựa trên lý thuyết, còn trên thực tế thời gian thực để chạy chương trình còn phụ thuộc vào tốc độ hiện tại của máy tính (lúc nhanh lúc chậm, ì à ì ạch).
Còn một điều nữa, thuật toán này cài đặt trên các ngôn ngữ khác nhau sẽ cho thời gian chạy khác nhau vì còn tuỳ vào tốc độ của trình biên dịch (nếu bạn viết được trên ngôn ngữ máy thì nhanh nhất). Nói chung, cái chương trình sắp xếp mà tôi thấy nhanh nhất bây giờ là Mathematica, sắp xếp 1 mảng 1 triệu phần tử trong vòng 1.25s (không biết dùng thuật toán gì nữa???).
End. Have fun.
SG.
Thấy mọi người có vẻ ít quan tâm đến các thuật toán sắp xếp, tôi mạn phép nói một chút về cái này - một trong những công cụ hay trong lập trình thuật toán. (Nếu bài toán này đã xuất hiện đâu đó trên ddth thì các mod cứ việc del, tui thì không hay dò tìm xét hỏi trong này lắm)
Như các bạn đã biết, cho đến ngày nay, để giải một bài toán phức tạp, trong hầu hết các trường hợp, người ta chia bài toán đó ra làm các bài toán nhỏ hơn đã được giải bằng các thuật toán cho trước, chỉ có một số ít là sáng tác (đúng hơn là phát minh) một thuật toán mới cho bài toán đó và bài toán đó sẽ trở thành bài toán cơ bản. Phương pháp thứ hai thì hơi khó, thường dành cho các nhà nghiên cứu nhiều hơn.
Còn về phương pháp thứ nhất, tôi xin nói đến một trong những vấn đề cơ bản nhất mà các bài toán về quản lý dữ liệu đòi hỏi, đó là sắp xếp dữ liệu. Như nhiều (thậm chí hầu hết) các bạn đã biết, phổ biến trên thế giới hiện nay là một số các thuật toán điển hình như Bubble sort, Insertion Sort, Shell Sort với độ phức tạp O(n2), hay nhanh hơn và cũng khó hơn là Quick Sort, Heap Sort với độ phức tạp O(n ln(n)). Có lẽ tôi cũng không cần phải nói nhiều về ý tưởng của các thuật toán này vì các bạn đã biết quá rõ rồi.
Bây giờ tôi xin trình bày một thuật toán mới (cũng không phải mới lắm, hình như là từ năm chín mấy ấy, không nhớ nữa) với một ý tưởng hoàn toàn mới, đi ngược lại với ý tưởng chính của tất cả các thuật toán trước đó và quan trọng nhất: LÀ THUẬT TOÁN NHANH NHẤT CÓ THỂ (ĐẠT ĐẾN TỐC ĐỘ TỚI HẠN). Thuật toán này có tên là FLASH SORT, được phát minh bới 1 guy named Karl-Dietrich Neubert .
Như các bạn có thể nhận thấy dễ dàng từ các thuật toán trước, mỗi khi muốn đổi chỗ 2 phần từ bất kỳ nào đó của mảng, các bạn đều phải dùng câu lệnh IF (một số ngôn ngữ diễn tả câu lệnh khác) để so sánh giá trị của 2 phần tử đó. Chính vì vậy, tôi có thể nói là ý tưởng chính của các thuật toán trước đây là dựa trên so sánh phần tử (Elements Comparison - EC). Bây giờ nói đến Flash sort, mặc dù trong thuật toán có sử dụng EC nhưng ý tưởng chính lại là phân lớp các phần tử (Subclasses Arrangement - SA).
Bây giờ tôi đi vào chi tiết hơn. Toàn bộ quá trình xử lý của thuật toán này được chia làm 3 giai đoạn (không kể giai đoạn nhập dữ liệu và in kết quả) bao gồm 2 giai đoạn phân lớp và 1 giai đoạn sắp xếp. Ta có mảng dữ liệu A[0..n]
1. Phân loại các phần tử (Elements Classification):
Như đã nói, ý tưởng chính là phân lớp, vì thế đây là giai đoạn chuẩn bị cho việc phân lớp (giống như procedure Ready trong cái form bài giải của mấy người thi đội tuyển tin học ấy, ^_^). Các yếu tố cần thiết để ready là:
- Số phân lớp m
- Một mảng m ghi vị trí của bắt đầu của mỗi phân lớp
Vấn đề 1: Xác định giá trị phần tử nhỏ nhất (minval) và vị trí phần tử lớn nhất (nmax) -> duyệt O(n)
Vấn đề 2: Để xác định xem phần tử nào thuộc phân lớp nào, ta dùng công thức sau:
K[i]=1+Floor[ (m-1)(A[i]-minval)(A[nmax]-minval) ]
Từ công thức trên, K[i] sẽ cho biết phân lớp chứa phần tử I của mảng A. Nhìn kỹ một chút, các bạn sẽ thấy là giá trị của K sẽ nằm trong khoảng [1,m]. Các bạn nhớ dùng hàm Floor chứ đừng dùng hàm Round, vì giá trị có thể sẽ bị sai lệch, Floor luôn cho giá trị nguyên gần nhất thấp hơn giá trị thực (trong Pascal bạn có thể dùng div).
Vấn đề 3: Ta lập một mảng L ghi vị trí xuất phát của các phân lớp trong mảng A. Ta tưởng tượng (imagine) một qui tắc rằng: một phân lớp I được coi là đã đầy khi mà L[I] nằm đúng ở vị trí xuất phát của phân lớp đó trong mảng A. Chính vì vậy ta coi như một phân lớp là rỗng khi nó nằm ở vị trí cuối của vị trí chính xác của nó trong phân lớp A, để mỗi khi ta bỏ một phần tử vào phân lớp đó, ta lùi L[I] lại 1 cho đến khi về đến đúng vị trí của nó thì nghĩa là đầy. Vậy để xác định được vị trí xuất phát cũng như vị trí kết thúc của từng phân lớp, ta phải biết được kích thước của từng phân lớp. Sau đó, để coi như các phân lớp là rỗng, vị trí bắt đầu của mỗi phân lớp phải nằm ở vị trí lẽ ra là kết thúc của nó trong mảng A. Vậy ta có công thức sau:
L[I]=L[I-1]+ kích thước của lớp I
Từ trên ta suy ra, vị trí ban đầu của phân lớp 1 sẽ là kích thước của nó, còn của phân lớp m sẽ là n (số phần tử).
2. Hoán vị các phần tử (Elements Permutation):
Sau khi đã sẵn sàng, chúng ta bắt đầu việc sắp xếp các phần tử vào đúng phân lớp của nó. Việc này sẽ hình thành các chu trình hoán vị: mỗi khi ta đem một phẩn tử ở đâu đó đến một vị trí nào đó thì ta phải nhấc phần tử hiện tại đang chiếm chỗ ra, và tiếp tục với phần tử bị nhấc ra và đưa đến chỗ khác cho đến khi quay lại vị trí ban đầu thì hoàn tất vòng lặp.
Vấn đề 1: Vậy làm thế nào để khi cầm trong tay 1 phần tử nào đó, ta biết phải bỏ nó vào chỗ nào cho phù hợp? Câu trả lời thật đơn giản, ta tính xem nó phải nằm ở phân lớp nào, rồi bỏ nó vào cái vị trí hiện tại của phân lớp đó, và vì ta bỏ vào phân lớp đó 1 phần tử nên phải lùi vị trí của phân lớp lại 1 đơn vị.
Vấn đề 2: Mặc dù ta đã đi qua 1 chu trình nhưng vẫn còn những phần tử chưa ở đúng chỗ thì phải làm thế nào? Cũng đơn giản, tiến hành 1 chu trình khác cho đến khi không còn con thỏ nào trong chuồng bò và ngược lại nữa thì thôi.
Vấn đề 3: Vậy là ta có một số các chu trình cần phải xử lý, vậy tại mỗi chu trình ta phải bắt đầu từ phần tử nào của mảng (Cycle leaders searching)? Đây cũng là một trong những điều đơn giản: ta chỉ việc duyệt từ đầu đến cuối mảng và tìm xem phần tử nào không nằm trong phân lớp (I<L[K[I]]), và bắt đầu bằng phần tử đó.
3. Sắp xếp các phần tử trong từng phân lớp theo đúng thứ tự (Elements Ordering)
Phù, đến đây thì mọi việc dường như trở nên quá đơn giản rồi, hai giai đoạn trên đã giúp chúng ta chia nhỏ 1 mảng to thành nhiều mảng nhỏ để việc sắp xếp trở nên nhanh hơn.
Vấn đề duy nhất: Chọn thuật toán nào để sắp xếp các phân lớp? Câu trả lời cho vấn đề này tương đối khó, nhưng nếu các bạn tính toán 1 chút, các bạn sẽ thấy rằng Straight-Insertion Sort là lựa chọn tối ưu vì chỉ có nó mới thực sự chia nhỏ mảng A ra các phân lớp và sắp xếp từng phân lớp.
4. Cài đặt (Installation)
Như vậy, tôi đã trình bày xong toàn bộ quá trình xử lý của thuật toán FLASH SORT. Dưới đây là cách cài đặt chương trình bằng PASCAL (nếu các bạn có Free Pascal thì càng tốt vì có thể thử nghiệm với mảng lớn):
Const
N=;
M=;
Var
L: array[1..m] of Integer;
A: array[1..n] of Integer;
Minval, nmax, nho, ban_dau: integer;
Program Flash_sort;
Procedure Ready;
Var i: integer;
Begin
For i:=1 to n do
A[i]:=Random(n*2);
End;
Procedure Classification;
Var
hang_so: integer;
i: integer;
Begin
Nmax:=1;
Minval:=A[1];
For i:=1 to n do
Begin
If (A[i]>A[nmax]) then nmax:=I;
If (Minval<A[i]) then Minval:=A[i];
End;
Hang_so:= (m-1)/(A[nmax]-Minval);
For i:=1 to n do
Inc(L[1+Trunc((A[i]-Minval )*Hang_so)]);
For i:=2 to m do
L[i]:=L[i-1]+L[i];
Nho:=A[nmax];
A[nmax]:=A[1];
A[1]:=nho;
End;
Procedure Permutation;
Var
Dem, I, k: integer;
Begin
Dem:=0;
I:=1;
K:=m;
While (dem<(n-1)) do
Begin
While (i>L[k]) do
Begin
Inc(i);
K:=1+Trunc((A[i]-minval)*hang_so);
End;
Bandau:=A[i];
While (i<>L[k]+1) do
Begin
K:=1+Trunc((bandau-minval)*hang_so);
Nho=A[L[k]];
A[L[k]]:=bandau;
Bandau:=nho;
Dec(L[k]);
Inc(dem);
End;
End;
Procedure Straight_Insertion_Sort;
Var
I,j: integer;
Begin
For i:=n-2 downto 1 do
If (A[i+1]<A[i]) then
Begin
Nho:=A[i];
J:=I;
While (A[j+1]<nho)
Begin
A[j]:=A[j+1];
Inc(j);
End;
A[j]:=nho;
End;
End;
Begin
Ready;
Classification;
Permutation;
Straight_Insertion_Sort;
End.
Chương trình trên sở dĩ tôi viết bằng PASCAL là vì tôi cho rằng đây là ngôn ngữ phổ biến nhất dùng trong việc học lập trình thuật toán, sẽ dễ dàng hơn cho việc đọc, hiểu (vì sử dụng modules) và translate ra các ngôn ngữ khác. Tuy nhiên vì máy tôi không có PASCAL nên mới chỉ là Primary version, chưa test được, nếu bạn nào dùng mà thấy lỗi thì cố gắng sửa hoặc không thì post lỗi lên rồi tôi sửa cũng được.
5. Thời gian chạy (Running time complexity)
Nhìn lại toàn bộ các giai đoạn của thuật toán, ta thấy như sau:
- Giai đoạn Classification đòi hỏi độ phức tạp O(n) và O(m)
- Giai đoạn Permutation đòi hỏi độ phức tạp O(n) ( vì mỗi phần tử chỉ phải đổi chỗ đúng một lần, và n lần cho n phần tử)
- Giai đoạn Straight_Insertion_Sort đỏi hỏi độ phức tạp O(n2/m) ( mỗi 1 phân lớp đòi hỏi độ phức tạp O((n/m)2) và m phân lớp đòi hỏi O(m*(n/m)2) )
Vấn đề ở đây là làm sao chọn số phân lớp để cho thời gian tối ưu. Ta có công thức tính độ phức tạp tổng cộng cho toàn bộ quá trình là :
F(m)= a1*n+a2*m+a3*n2/m.
F’(m)=a2-a3(n/m)2=0 => m=n*(a3/a2)1/2.
Theo một số khảo sát dưạ trên nghiên cứu về tốc độ chạy của chương trình (của một số nhà nghiên cứu), a2 xấp xỉ 2 và a3 xấp xỉ 3/8, như vậy ta có m xấp xỉ 0.43n là số phân lớp tối ưu đề cho thời gian chạy nhanh nhất. Tuy nhiên đây chỉ là con số dựa trên lý thuyết, còn trên thực tế thời gian thực để chạy chương trình còn phụ thuộc vào tốc độ hiện tại của máy tính (lúc nhanh lúc chậm, ì à ì ạch).
Còn một điều nữa, thuật toán này cài đặt trên các ngôn ngữ khác nhau sẽ cho thời gian chạy khác nhau vì còn tuỳ vào tốc độ của trình biên dịch (nếu bạn viết được trên ngôn ngữ máy thì nhanh nhất). Nói chung, cái chương trình sắp xếp mà tôi thấy nhanh nhất bây giờ là Mathematica, sắp xếp 1 mảng 1 triệu phần tử trong vòng 1.25s (không biết dùng thuật toán gì nữa???).
End. Have fun.
SG.