Noob Weblog

Khảo sát thuật toán sắp xếp nhanh nhất

Posted by noob on Tháng Tám 23, 2008

Một trong những nhiệm vụ thông thường nhất của máy tính là sắp xếp dữ liệu nhằm phân tích và xử lý lượng dữ liệu đó. Đã có rất nhiều thuật toán nhằm tìm ra cách thức đơn giản nhất và nhanh nhất thực hiện nhiệm vụ này. Trong phạm vi bài báo này, chúng ta sẽ cùng khảo sát thời gian thực hiện của một số thuật toán xắp xếp đơn giản, một vài thuật toán đã được giới thiệu trong giáo trình toán rời rạc 1 + 2 của chúng ta.

Sắp xếp nổi bọt – Sắp xếp nổi bọt là một thuật toán rất phổ biến, nhưng kô phải lựa chọn tốt nhất

Sắp xếp chèn – Sắp xếp chèn tỏ ra hữu dụng trong một vài trường hợp, đặc biệt khi nó được sử dụng làm nền cho thuật toánk hác

Sắp xếp trung điểm – Thuật toán sắp xếp trung điểm được cho là một thụât toán cổ điển nổi tiếng vì sự tối ưu mã nguồn cao

Sắp xếp theo danh sách đa kết nối – có vẻ đây là phương pháp nhanh nhất, nhưng chỉ trong vài trường hợp đặc biệt

Sắp xếp giảm dần – Nếu bạn chỉ học một thuật toán sắp xếp, học sắp xếp nhân.

Thời gian thực nghiệm

Dữ liệu để kiểm tra thời gian thực nghiệm được sinh ra bởi thuật toán sinh số ngẫu nhiên. Điều này cho phép mỗi thuật toán sắp xếp phải làm việc trên các số ngẫu nhiên đồng nhất. Thời gian cuối cùng sẽ là giá trị trung bình của 10 lần chạy khác nhau.

Thực nghiệm này được thực hiện trên bộ vi xử lý Pentium 3 Ghz. Kô có chương trình nào chạy đồng thời trong thời gian thí nghiệm, ngoại trừ Windows XP

Bubble Sort

Sắp xếp nổi bọt

Sắp xếp nổi bọt là một thuật toán đơn giản và rất dễ viết mã, nhưng nó là một thuật toán khá lâu đời và nhiều khi kô thích hợp với các ứng dụng số lớn. Khi chúng ta tăng gấp đôi số lượng đơn vị cần sắp xếp, thời gian sắp xếp sẽ tăng lên bốn lần. Nếu con số đó tăng lên là 10, thời gian sắp xếp sẽ tăng lên 100. Kết quả thực nghiệm được cho dưới đây:

Sort 10,000 Sort 100,000
Random Numbers Random Numbers
Time 0.366 sec. 36.702 sec.

Insertion Sort

Sắp xếp chèn

Sắp xếp kiểu chèn tuần tự được mô tả giống như cách bạn có thể sắp xếp các quân bài cùng chất. Bạn chọn lấy một quân bài, so sánh nó với quân bài bên cạnh và đặt nó vào vị trí phù hợp.

Cho dù sắp xếp chèn cũng là một thuật toán có thời gian xử lý tăng gấp bốn khi số đơn vị tăng lên gấp đôi, xắp xếp chèn tuần tự cũng có vài ưu điểm so với sắp xếp nổi bọt.

1) Thuật toán này tỏ ra vượt trội với danh sách nhỏ ( ít hơn 30 thành tố )

2) Thuật toán chèn là nền tảng cho thuật toán xắp xếp giảm dần ( Shell sort ). Khi bạn học sắp xếp chèn, sắp xếp Shell là một thuật toán bổ sung quan trọng

3) Sắp xếp chèn thực hiện rất nhanh cho mảng gần như đã được sắp xếp. Nó rất hữu hiệu cho đợt sắp xếp cuối cùng sau khi đã thực hiện xắp xếp nhanh ( Quicksort )

4) Các máy tính hiện đại đều có bộ nhớ đệm có thể truy cập nhanh hơn các bộ nhớ thông thường. Mỗi khi Insertsort thực hiện sắp xếp một phần của mảng, phần đó sẽ được lưu vào bộ nhớ đệm của máy tính và làm giảm thời gian thực hiện sắp xếp

Sort 10,000 Sort 100,000
Random Numbers Random Numbers
Time 0.055 sec. 5.392 sec.

Multiple Link List Sort

Xắp xếp các danh sách liên kết đa chiều

Sắp xếp các danh sách liên kết đa chiều chỉ có hiệu quả với các dữ liệu và điều kiện tính toán nhất định, cho dù vậy, vẫn có những sự tương hợp với tốc độ thực hiện kết quả của nó. Trong những điều kiện cho phép, đây sẽ là thuật toán xắp xếp nhanh nhất. MLLsort là một phép xắp xếp các địa chỉ cần tính toán. Với mỗi số được xắp xếp, thuật toán sẽ so sánh giá trị của số đó và đưa ra vị trí phù hợp trong danh sách đã được xắp xếp

Tiến trình này có vẻ giống với cách thức xắp xếp trong trò chơi lắp ráp các khối hình. Bạn chọn ngẫu nhiên một đối tượng, so sánh nó với các đối tượng khác trên tổng thể toàn bức tranh, và đặt mẩu ảnh đó vào vị trí phù hợp. Sau đó chọn một đối tượng thứ hai và lặp lại quá trình trên. Mỗi phần chỉ cần thực hiện một lần, và sau khi bạn kết thúc việc chọn các phần khác nhau đặt vào các vị trí phù hợp, trò chơi sẽ kết thúc.

Thuật toán MLLS chạy trong thời gian tuyến tính ( kô phải log(n) hay log(log(n))). Đó là lý do đôi lúc nó là thuật toán sắp xếp nhanh nhất.

Sort 1,000,000 Sort 10,000,000
Random Numbers Random Numbers
Time 0.127 sec. 1.230 sec.


Median-of-three Quicksort

Sắp xếp trung điểm

Quicksort là thuật toán sinh xắp xếp thông thường nhất. Quicksort có thể làm việc trên bất kì kiểu dữ liệu nào. Nó còn đòi hỏi một số ít hơn các bộ nhớ được cấp phép so với MLLsort

Quicksort có điểm yếu là khó viết mã. Tuy vậy, cái nghèo nhất của Quicksort là làm chậm thời gian xắp xếp với một số kiểu dữ liệu – nhiều khi là một phần dữ liệu. Nếu Quicksort được viết mã theo phương pháp thông thường, nó sẽ chạy với khoảng thời gian là N*(Log(N)), và có thể chạy lâu hơn các thuật toán N*log(N) khác như Heapsort hay Merge Sort

Cách làm việc của Quicksort các bạn có thể tham khảo trong sách Toán rời rạc

Theo dõi kết quả bảng dưới đây, biến “MinGroup” đại diện một khối đơn vị thuật toán lựa chọn để xắp xếp.

<- – – – – – – – Sort 1,000,000 Elements – – – – – – – ->
MinGroup MinGroup MinGroup MinGroup MinGroup MinGroup MinGroup
= 20 = 40 = 50 = 60 = 70 = 80 = 100
Time 0.186 0.178 0.176 0.178 0.181 0.177 0.178 sec.

<- – – – – – – – Sort 10,000,000 Elements – – – – – – – ->
MinGroup MinGroup MinGroup MinGroup MinGroup MinGroup MinGroup
= 20 = 40 = 50 = 60 = 70 = 80 = 100
Time 2.163 2.112 2.097 2.089 2.097 2.094 2.111 sec.

Shell Sort

Sắp xếp vớI độ dài bước giảm dần

Nếu bạn chỉ học một loại thuật toán sắp xếp, hãy tập trung vào Shell sort. Viết mã Shell sort dễ dàng hơn viết mã Quicksort và nó cũng nhanh gần như Quicksort

Shellsort có nguồn gốc từ Insertion Sort. Khi chạy chương trình, nếu bạn làm vịêc với số lượng đối tượng nhỏ, nó hoàn toàn giống với Insertsort. Nhưng nếu bạn làm việc với số lớn, nó sẽ là sự mở rộng của Insert Sort. Shell sort phá các mảng thành các phần nhỏ hơn đúng theo ” Inserion sort”

—————————————————————
RandNbrs | A | B | C | D | A | B | C | D | A | B | C | D | A | B | C | D |
—————————————————————
Index(Pos) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Ví dụ, cho rằng bạn đang sắp xếp 16 thành tố và đặt cờ kí hiệu A ( flag ) vào các giá trị 1,4,13. Thuật toán sẽ chia cả mảng thành các phần có kích cỡ là 4. Lúc này nó sẽ làm việc như là sắp xếp chèn. 3 vị trí tiếp theo thuật toán sẽ sử dụng tới các số đánh dấu “B”, “C”, “D”. Khi tiến trình kết thúc, mảng sẽ được sắp xếp một cách hoàn thiện.

Bảng kết quả thời gian thực nghiệm

<- – – – – – Sort 1,000,000 Elements – – – – – ->
Use 1, 3, 7, Use 1, 4, 13, Use 1, 8, 23,
for “Gaps” for “Gaps” for “Gaps”
Time 0.337 sec. 0.422 sec. 0.297 sec.

<- – – – – – Sort 10,000,000 Elements – – – – – ->
Use 1, 3, 7, Use 1, 4, 13, Use 1, 8, 23,
for “Gaps” for “Gaps” for “Gaps”
Time 4.389 sec. 6.858 sec. 3.997 sec.

Một phản hồi to “Khảo sát thuật toán sắp xếp nhanh nhất”

  1. thang said

    bạn có thể gửi code cái cách mà bạn tính time của các thuật toán được ko
    cảm ơn bạn nhiều
    nếu bạn có thể gửi cho minh qua mail:quyetthangqbh mình cám ơn bạn nhiều

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: