thucnq

Lang thang 1 hồi thấy bài này hay nên sưu tầm về anh em đọc nhé

Một trong những vấn đề nền tảng của khoa học máy tính là sắp xếp một tập các phần tử cho trước theo thứ tự nào đó. Có rất nhiều các giải pháp cho vấn đề này, được biết đến như là các thuật toán sắp xếp (sorting algorithms). Bên cạnh các thuật toán sắp xếp đơn giản và rất rỏ ràng, như là sắp xếp nổi bọt (bubble sort). Một số khác, như phương pháp sắp xếp nhanh (quick sort) thì lại rất phức tạp nhưng đổi lại có kết quả thực thi nhanh hơn một cách đáng kể.


Dưới đây là liên kết tới các mô tả, phân tích, và mã nguồn cho 7 thuật toán sắp xếp quan trọng, phổ biến nhất hiện nay.


Bubble sort
Heap sort
Insertion sort
Merge sort
Quick sort
Selection sort
Shell sort

Những thuật toán sắp xếp quen thuộc này có thể được chia thành hai nhóm dựa theo độ phức tạp của chúng. Độ phức tạp của thuật toán (Algorithmic complexity) là một chủ đề khá rắc rối đòi hỏi sự tưởng tượng mà sẽ tốn nhiều thời gian để giải thích, nhưng ở đây có thể hiểu thông qua mối tương quan trực tiếp giữa độ phức tạp của thuật toán và hiệu quả của nó. Độ phức tạp của thuật toán thường được kí hiệu bởi một hàm O, trong đó O biểu diễn độ phức tạp của thuật toán đi kèm với một giá trị n biểu diễn kích thước của số lần chạy tối đa mà thuật toán đó dựa vào để xử lý trên dữ liệu.

Ví dụ, O(n) có nghĩa là thuật toán có độ phức tạp tuyến tính. Cụ thể hơn , nó sẽ mất thời gian gấp 10 lần cho việc xử lý trên tập dữ liệu có 100 phần tử so với tập chỉ có 10 phần tử (10 * 10 = 100). Nếu độ phức tạp là O(n2) (quadratic complexity), thì nó sẽ phải tiêu tốn thời gian gấp 100 lần để xử lý trên tập 100 phần tử so với tập dữ liệu chỉ gồm 10 phần tử.

Hai nhóm thuật toán sắp xếp được phân như sau: nhóm thứ nhất có độ phức tạp là O(n2) bao gồm bubble, insertion, selection, và shell sorts; Nhóm thứ hai có độ phức tạp là O(n log n) gồm heap, merge, và quick sorts.

Bên cạnh độ phức tạp của thuật toán, tốc độ của các thuật toán sắp xếp có thể được so sánh dựa vào kinh nghiệm có được từ việc thử trên các tập dữ liệu. Vì tốc độ sắp xếp có thể thay đổi rất nhiều tùy theo đặc điểm của dữ liệu, nên để các kết quả thống kê chính xác dựa trên kinh nghiệm đòi hỏi việc chạy các thuật toán nhiều lần trên các dữ liệu khác nhau và tính trung bình. Thông thường tập dữ liệu kiểm tra được tạo ngẫu nhiên.

Trong các biểu đồ thể hiện mức độ hiệu quả của thuật toán dưới đây, đường thấp nhất là "tốt nhất". Ghi nhớ rằng "tốt nhất" ở đây là một khái niệm không tuyệt đối vì nó còn tùy vào trường hợp sử dụng của bạn - nếu nhìn biểu đồ bạn sẽ thấy quick sort có lẽ là thuật toán nhanh nhất, nhưng nếu sử dụng nó để sắp xếp một tập 20 phần tử thì cũng giống như đem dao mổ trâu đi cắt hành.


Đồ thị trên đã thể hiện khá rỏ, Bubble sort là giải pháp cực kì không hiệu quả, và shell sort là sự cải tiến tạo ra cuộc bứt phá hết sức ngoạn mục. Chú ý rằng vào đường ngang đầu tiên của khu vực đồ thị thể hiện thời gian 100 giây- bạn sẽ thấy rằng không có thuật toán nào trong số này mà bạn muốn sử dụng cho tập dữ liệu lớn của một ứng dụng tương tác. Ngay cả khi dùng shell sort, người sử dụng cũng có nguy cơ ngồi bấm móng tay nếu bạn cố gắng sắp xếp nhiều hơn 10,000 phần tử.

Nhìn từ phương diện tươi sáng hơn, tất cả những thuật toán thuộc nhóm O(n2) đều đơn giản một cách không ngờ (có thể shell sort là một ngoại lệ hơi phức tạp hơn). Với những chương trình dùng kiểm tra nhanh, những mẩu thử nghiệm gấp, hay các phần mềm dành cho người sử dụng nội bộ, chúng không phải là những lựa chọn tồi nếu bạn không đặt quá nặng về hiệu năng.


Trong trường hợp tốc độ là ưu tiên hàng đầu, những giải thuật thuộc nhóm O(n log n) nên được sử dụng. Chú ý rằng thời gian trong đồ thị ngay trên đây được đo theo từng phần 10 của giây thay vì từng trăm giây như đồ thị của nhóm O(n2).

Tuy nhiên mọi thứ thì không thật sự dễ dàng với các ứng dụng thực tiễn, bạn phải đứng trước sự lựa chọn cân bằng (trade-offs) giữa các yếu tố. Những thuật toán thuộc nhóm O(n log n) thì rất nhanh, nhưng tốc độ đó có được do phải trả giá cho sự phức tạp trong triển khai. Trong trường hợp đệ quy, các cấu trúc dữ liệu nâng cao, mảng đa chiều - việc sử dụng những thuật toán này sẽ tạo ra nhiều vấn đề phát sinh rất khó chịu.

Copy this link and send via YM,MSN,AOL,ICQ..... Tổng quan về thuật toán sắp xếp http://www.laptrinhviet.com/showthread.php?t=19820 Hãy gửi link này cho bạn bè trong list của bạn giúp mình nhé ;) thank nhiều