Thuật toán sắp xếp nổi bọt (bubble sort)

Posted by Mạnh Chức Lê | Posted in | Posted on 5/12/2010

0

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.

Comments Posted (0)

Đăng nhận xét