Thuật toán sắp xếp là nhóm các thuật toán dùng để đặt các phần tử đã cho vào danh sách theo một thứ tự nào đó. Thứ tự thường được sử dụng nhất là thứ tự số học (numerical) và thứ tự từ điển (lexicographical). Có rất nhiều các thuật toán sắp xếp với hiệu quả tính toán rất khác biệt, chính vì vậy việc hiểu để tìm ra thuật toán thích hợp cho ứng dụng là quan trọng.
Bubble sort là một phương pháp đơn giản, rỏ ràng thường được dùng để giảng dạy trong khoa học máy tính. Thuật toán bắt đầu duyệt từ điểm đầu tiên của tập dữ liệu. Nó so sánh hai phần tử đầu tiên nếu phần tử đầu lớn hơn phần tử thứ hai thì nó tiến hành hoán đổi vị trị giữa chúng. Cứ như thế thao tác này được làm với mỗi cặp phần tử liền kề cho tới cuối tập dữ liệu. Sau đó nó quay lại lặp lại tiến trình với hai phần tử đầu tiên, quá trình lặp lại cho tới khi không có hiện tượng hoán đổi xảy ra trong toàn bộ phạm vi duyệt. Mặc dù đơn giản, thuật toán này thật sự không hiểu quả và hiếm khi được sử dụng trong thực tế ngoại trừ cho mục đích giáo dục. Tuy nhiên với số lượng phần tử sắp xếp của dữ liệu nhỏ (vd. 20) nó tốt hơn Quicksort.
Vì sau lần duyệt toàn bộ tập dữ liệu thứ nhất chúng ta chắc chắn có phần tử lớn nhất nằm cuối . Lần thứ hai phần từ lớn nhất liền kề sẽ nằm kế cuối, cứ như thế cho tới khi toàn bộ dữ liệu được sắp xếp. Do đó tổng số lần lặp xử lý cho thuật toán bubble sort gốc sẽ tối đa là NxN (O(NxN)). Tuy nhiên có rất nhiều phương pháp để cải tiến bubble sort nhằm làm giãm độ phức tạp thực tế xuống đáng kể. Những phương pháp này sẽ được trình bày ở những bài sau.
Binh Nguyen - Bioz - ieev.org
Bản tin lập trình việt
07-02-2010, 01:13 PM
Thuật toán sắp xếp nổi bọt (bubble sort) 
