Giải thuật sắp xếp nổi bọt (Bubble Sort)
Sắp xếp nổi bọt (Bubble Sort) là gì?
Sắp xếp nổi bọt là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.
Cách giải thuật sắp xếp nổi bọt làm việc?
Giả sử chúng ta có một mảng không có thứ tự gồm các phần tử như dưới đây. Bây giờ chúng ta sử dụng giải thuật sắp xếp nổi bọt để sắp xếp mảng này.
Giải thuật sắp xếp nổi bọt bắt đầu với hai phần tử đầu tiên, so sánh chúng để kiểm tra xem phần tử nào lớn hơn.
Trong trường hợp này, 33 lớn hơn 14, do đó hai phần tử này đã theo thứ tự. Tiếp đó chúng ta so sánh 33 và 27.
Chúng ta thấy rằng 33 lớn hơn 27, do đó hai giá trị này cần được tráo đổi thứ tự.
Mảng mới thu được sẽ như sau:
Tiếp đó chúng ta so sánh 33 và 35. Hai giá trị này đã theo thứ tự.
Sau đó chúng ta so sánh hai giá trị kế tiếp là 35 và 10.
Vì 10 nhỏ hơn 35 nên hai giá trị này chưa theo thứ tự.
Tráo đổi thứ tự hai giá trị. Chúng ta đã tiến tới cuối mảng. Vậy là sau một vòng lặp, mảng sẽ trông như sau:
Để đơn giản, tiếp theo mình sẽ hiển thị hình ảnh của mảng sau từng vòng lặp. Sau lần lặp thứ hai, mảng sẽ trông giống như:
Sau mỗi vòng lặp, ít nhất một giá trị sẽ di chuyển tới vị trí cuối. Sau vòng lặp thứ 3, mảng sẽ trông giống như:
Và khi không cần tráo đổi thứ tự phần tử nào nữa, giải thuật sắp xếp nổi bọt thấy rằng mảng đã được sắp xếp xong.
Tiếp theo, chúng ta tìm hiểu thêm một số khía cạnh thực tế của giải thuật sắp xếp.
Giải thuật cho sắp xếp nổi bọt (Bubble Sort)
Giả sử list là một mảng có n phần tử. Tiếp đó giả sử hàm swap để tráo đổi giá trị của các phần tử trong mảng (đây là giả sử, tất nhiên là bạn có thể viết code riêng cho hàm swap này).
Bắt đầu giải thuật BubbleSort(list) for tất cả phần tử trong list if list[i] > list[i+1] swap(list[i], list[i+1]) kết thúc if kết thúc for return list Kết thúc BubbleSort
Giải thuật mẫu cho sắp xếp nổi bọt (Bubble Sort)
Chúng ta thấy rằng giải thuật sắp xếp nổi bọt so sánh mỗi cặp phần tử trong mảng trừ khi cả toàn bộ mảng đó đã hoàn toàn được sắp xếp theo thứ tự tăng dần. Điều này có thể làm tăng độ phức tạp, tức là tăng các thao tác so sánh và tráo đổi không cần thiết nếu như mảng này không cần sự tráo đổi nào nữa khi tất cả các phần tử đã được sắp xếp theo thứ tự tăng dần rồi.
Để tránh việc này xảy ra, chúng ta có thể sử dụng một biến swapped chẳng hạn để giúp chúng ta biết có cần thực hiện thao tác tráo đổi thứ tự hay không. Nếu không cần thiết thì thoát khỏi vòng lặp.
Bạn theo dõi phần giải thuật mẫu minh họa sau:
Bắt đầu hàm bubbleSort( list : mảng các phần tử ) loop = list.count; for i = 0 tới loop-1 thực hiện: swapped = false for j = 0 tới loop-1 thực hiện: /* so sánh các phần tử cạnh nhau */ if list[j] > list[j+1] then /* tráo đổi chúng */ swap( list[j], list[j+1] ) swapped = true kết thúc if kết thúc for /*Nếu không cần tráo đổi phần tử nào nữa thì tức là mảng đã được sắp xếp. Thoát khỏi vòng lặp.*/ if(not swapped) then break kết thúc if kết thúc for Kết thúc hàm return list
Triển khai giải thuật sắp xếp nổi bọt trong C
Một điều nữa mà chúng ta chưa nói tới trong 2 phần thiết kế giải thuật đó là cứ sau mỗi vòng lặp thì các giá trị lớn nhất sẽ xuất hiện ở vị trí cuối mảng (như trong hình minh họa: sau vòng lặp 1 là 35; sau vòng lặp 2 là 33 và 35; …). Do đó, vòng lặp tiếp theo sẽ không cần bao gồm cả các phần tử đã được sắp xếp này. Để thực hiện điều này, trong phần code chúng ta giới hạn vòng lặp lặp bên để tránh phải lặp lại các giá trị đã qua sắp xếp này.
Theo Tutorialspoint
Bài trước: Giải thuật sắp xếp trong cấu trúc dữ liệu & giải thuật
Bài tiếp: Giải thuật sắp xếp chèn (Insertion Sort)
Bạn nên đọc
-
Công thức tính diện tích hình vuông, tính chu vi hình vuông
-
Công thức tính diện tích xung quanh hình nón, diện tích toàn phần hình nón, thể tích hình nón, V nón
-
Công thức tính diện tích xung quanh hình nón cụt, diện tích toàn phần hình nón cụt, thể tích hình nón cụt
-
Công thức tính diện tích tam giác: vuông, thường, cân, đều
-
Công thức tính thể tích hình chóp cụt, diện tích xung quanh và toàn phần của hình chóp cụt
-
Cách giải phương trình bậc 2
Cũ vẫn chất
-
Cách đăng nhập nhiều tài khoản trên Telegram iPhone, Android
Hôm qua -
Đáp án đoán tướng sinh nhật Liên Quân, Thử tài đoán tướng Liên Quân 04/11/2024
Hôm qua -
Câu lệnh COALESCE trong SQL Server
Hôm qua -
Cách tạo thiệp cưới online, ghép ảnh thiệp cưới online
Hôm qua -
Stick War Legacy
-
Hướng dẫn cách vẽ sơ đồ trong Word
Hôm qua -
Cách chặn tải file, video trên Google Drive
Hôm qua -
Hướng dẫn root Android dễ dàng và nhanh chóng
Hôm qua -
Muốn đọc được báo cáo tài chính, bạn phải hiểu các chỉ số cơ bản này
Hôm qua -
Hàm YEAR trong SQL Server
Hôm qua