Sắp xếp bong bóng là gì?
Bubble Sort là một thuật toán sắp xếp được sử dụng để sắp xếp các mục trong danh sách theo thứ tự tăng dần bằng cách so sánh hai giá trị liền kề. Nếu giá trị đầu tiên cao hơn giá trị thứ hai, giá trị đầu tiên sẽ chiếm vị trí giá trị thứ hai, trong khi giá trị thứ hai chiếm vị trí giá trị đầu tiên. Nếu giá trị đầu tiên thấp hơn giá trị thứ hai, thì không có hoán đổi nào được thực hiện.
Quá trình này được lặp lại cho đến khi tất cả các giá trị trong danh sách được so sánh và hoán đổi nếu cần. Mỗi lần lặp thường được gọi là một lần vượt qua. Số lần vượt qua trong sắp xếp bong bóng bằng số phần tử trong danh sách trừ đi một phần tử.
Trong hướng dẫn Sắp xếp bong bóng trong Python này, bạn sẽ học:
- Sắp xếp bong bóng là gì?
- Triển khai thuật toán sắp xếp bong bóng
- Thuật toán sắp xếp bong bóng được tối ưu hóa
- Đại diện trực quan
- Ví dụ Python
- Giải thích mã
- Ưu điểm sắp xếp bong bóng
- Sắp xếp bong bóng Nhược điểm
- Phân tích độ phức tạp của sắp xếp bong bóng
Triển khai thuật toán sắp xếp bong bóng
Chúng tôi sẽ chia nhỏ việc triển khai thành ba (3) bước, đó là vấn đề, giải pháp và thuật toán mà chúng tôi có thể sử dụng để viết mã cho bất kỳ ngôn ngữ nào.
Vấn đề
Danh sách các mặt hàng được đưa ra theo thứ tự ngẫu nhiên và chúng tôi muốn sắp xếp các mặt hàng một cách có trật tự
Hãy xem xét danh sách sau:
[21,6,9,33,3]
Giải pháp
Lặp lại danh sách so sánh hai phần tử liền kề và hoán đổi chúng nếu giá trị đầu tiên cao hơn giá trị thứ hai.
Kết quả sẽ như sau:
[3,6,9,21,33]
Thuật toán
Thuật toán sắp xếp bong bóng hoạt động như sau
Bước 1) Lấy tổng số phần tử. Nhận tổng số mục trong danh sách nhất định
Bước 2) Xác định số lần đi ngoài (n - 1) được thực hiện. Chiều dài của nó là danh sách trừ đi một
Bước 3) Thực hiện chuyền trong (n - 1) lần đối với truyền ngoài 1. Lấy giá trị phần tử đầu tiên và so sánh với giá trị thứ hai. Nếu giá trị thứ hai nhỏ hơn giá trị đầu tiên, thì hoán đổi vị trí
Bước 4) Lặp lại bước 3 đi cho đến khi bạn đến đường bên ngoài (n - 1). Lấy phần tử tiếp theo trong danh sách, sau đó lặp lại quy trình đã được thực hiện ở bước 3 cho đến khi tất cả các giá trị đã được đặt theo đúng thứ tự tăng dần của chúng.
Bước 5) Trả kết quả khi tất cả các đường chuyền đã được thực hiện. Trả về kết quả của danh sách đã sắp xếp
Bước 6) Tối ưu hóa thuật toán
Tránh các đường chuyền bên trong không cần thiết nếu danh sách hoặc các giá trị liền kề đã được sắp xếp. Ví dụ: nếu danh sách được cung cấp đã chứa các phần tử đã được sắp xếp theo thứ tự tăng dần, thì chúng ta có thể phá vỡ vòng lặp sớm.
Thuật toán sắp xếp bong bóng được tối ưu hóa
Theo mặc định, thuật toán sắp xếp bong bóng trong Python so sánh tất cả các mục trong danh sách bất kể danh sách đã được sắp xếp hay chưa. Nếu danh sách nhất định đã được sắp xếp, việc so sánh tất cả các giá trị là một sự lãng phí thời gian và tài nguyên.
Tối ưu hóa sắp xếp bong bóng giúp chúng tôi tránh lặp lại không cần thiết và tiết kiệm thời gian và tài nguyên.
Ví dụ: nếu mục đầu tiên và mục thứ hai đã được sắp xếp, thì không cần phải lặp lại các giá trị còn lại. Quá trình lặp được kết thúc và lần lặp tiếp theo được bắt đầu cho đến khi quá trình hoàn tất như được hiển thị trong ví dụ Sắp xếp bong bóng bên dưới.
Việc tối ưu hóa được thực hiện theo các bước sau
Bước 1) Tạo một biến cờ để giám sát nếu có bất kỳ sự hoán đổi nào xảy ra trong vòng lặp bên trong
Bước 2) Nếu các giá trị đã hoán đổi vị trí, hãy tiếp tục với lần lặp tiếp theo
Bước 3) Nếu các lợi ích chưa hoán đổi vị trí, hãy chấm dứt vòng lặp bên trong và tiếp tục với vòng lặp bên ngoài.
Sắp xếp bong bóng được tối ưu hóa hiệu quả hơn vì nó chỉ thực hiện các bước cần thiết và bỏ qua những bước không bắt buộc.
Đại diện trực quan
Đưa ra danh sách năm phần tử, các hình ảnh sau minh họa cách sắp xếp bong bóng lặp lại qua các giá trị khi sắp xếp chúng
Hình ảnh sau đây cho thấy danh sách chưa được sắp xếp
Lặp lại đầu tiên
Bước 1)
Giá trị 21 và 6 được so sánh để kiểm tra giá trị nào lớn hơn giá trị kia.
21 lớn hơn 6, do đó 21 chiếm vị trí bị chiếm bởi 6 trong khi 6 chiếm vị trí đã bị chiếm bởi 21
Danh sách sửa đổi của chúng tôi bây giờ trông giống như ở trên.
Bước 2)
Các giá trị 21 và 9 được so sánh.
21 lớn hơn 9, vì vậy chúng tôi hoán đổi vị trí của 21 và 9
Danh sách mới bây giờ như trên
Bước 3)
Các giá trị 21 và 33 được so sánh để tìm ra giá trị lớn hơn.
Giá trị 33 lớn hơn 21, vì vậy không có hoán đổi nào diễn ra.
Bước 4)
Các giá trị 33 và 3 được so sánh để tìm giá trị lớn hơn.
Giá trị 33 lớn hơn 3, vì vậy chúng tôi hoán đổi vị trí của chúng.
Danh sách được sắp xếp ở cuối lần lặp đầu tiên giống như danh sách ở trên
Lặp lại lần thứ hai
Danh sách mới sau lần lặp thứ hai như sau
Lặp lại lần thứ ba
Danh sách mới sau lần lặp thứ ba như sau
Lặp lại lần thứ tư
Danh sách mới sau lần lặp thứ tư như sau
Ví dụ Python
Đoạn mã sau đây cho thấy cách triển khai thuật toán Sắp xếp bong bóng trong Python.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
Thực thi chương trình sắp xếp bong bóng ở trên bằng Python sẽ tạo ra các kết quả sau
[6, 9, 21, 3, 33]
Giải thích mã
Giải thích cho mã chương trình Python Bubble Sort như sau
ĐÂY,
- Định nghĩa một hàm bubbleSort chấp nhận một tham số theSeq. Mã không xuất ra bất cứ thứ gì.
- Lấy độ dài của mảng và gán giá trị cho một biến n. Mã không xuất ra bất cứ thứ gì
- Bắt đầu vòng lặp for chạy thuật toán sắp xếp bong bóng (n - 1) lần. Đây là vòng lặp bên ngoài. Mã không xuất ra bất cứ thứ gì
- Xác định biến cờ sẽ được sử dụng để xác định xem hoán đổi có xảy ra hay không. Điều này dành cho mục đích tối ưu hóa. Mã không xuất ra bất cứ thứ gì
- Bắt đầu vòng lặp bên trong so sánh tất cả các giá trị trong danh sách từ giá trị đầu tiên đến giá trị cuối cùng. Mã không xuất ra bất cứ thứ gì.
- Sử dụng câu lệnh if để kiểm tra xem giá trị ở phía bên trái có lớn hơn giá trị ở phía bên phải ngay lập tức hay không. Mã không xuất ra bất cứ thứ gì.
- Gán giá trị của Seq [j] cho một biến tạm thời tmp nếu điều kiện cho giá trị true. Mã không xuất ra bất cứ thứ gì
- Giá trị của Seq [j + 1] được gán cho vị trí của Seq [j]. Mã không xuất ra bất cứ thứ gì
- Giá trị của biến tmp được gán cho vị trí theSeq [j + 1]. Mã không xuất ra bất cứ thứ gì
- Biến cờ được gán giá trị 1 để chỉ ra rằng một sự hoán đổi đã diễn ra. Mã không xuất ra bất cứ thứ gì
- Sử dụng câu lệnh if để kiểm tra xem giá trị của cờ biến có bằng 0. Mã không xuất ra bất kỳ thứ gì
- Nếu giá trị là 0, thì chúng ta gọi câu lệnh break bước ra khỏi vòng lặp bên trong.
- Trả về giá trị của Seq sau khi nó đã được sắp xếp. Mã xuất ra danh sách đã sắp xếp.
- Định nghĩa một biến el chứa danh sách các số ngẫu nhiên. Mã không xuất ra bất cứ thứ gì.
- Gán giá trị của hàm bubbleSort cho một kết quả biến.
- In giá trị của kết quả biến.
Ưu điểm sắp xếp bong bóng
Sau đây là một số ưu điểm của thuật toán sắp xếp bong bóng
- Nó rất dễ hiểu
- Nó hoạt động rất tốt khi danh sách đã hoặc gần như được sắp xếp
- Nó không yêu cầu bộ nhớ rộng.
- Thật dễ dàng để viết mã cho thuật toán
- Yêu cầu về không gian là tối thiểu so với các thuật toán sắp xếp khác.
Sắp xếp bong bóng Nhược điểm
Sau đây là một số nhược điểm của thuật toán sắp xếp bong bóng
- Nó không hoạt động tốt khi sắp xếp danh sách lớn. Tốn quá nhiều thời gian và nguồn lực.
- Nó chủ yếu được sử dụng cho các mục đích học thuật chứ không phải ứng dụng trong thế giới thực.
- Số bước cần thiết để sắp xếp danh sách theo thứ tự n 2
Phân tích độ phức tạp của sắp xếp bong bóng
Có ba loại Phức tạp là:
1) Sắp xếp độ phức tạp
Độ phức tạp sắp xếp được sử dụng để biểu thị số lượng thời gian thực thi và không gian cần thiết để sắp xếp danh sách. Sắp xếp bong bóng thực hiện (n - 1) lần lặp để sắp xếp danh sách trong đó n là tổng số phần tử trong danh sách.
2) Độ phức tạp về thời gian
Độ phức tạp thời gian của loại bong bóng là O (n 2 )
Sự phức tạp về thời gian có thể được phân loại là:
- Trường hợp tệ nhất - đây là nơi danh sách được cung cấp theo thứ tự giảm dần. Thuật toán thực hiện số lần thực thi tối đa được biểu thị bằng [Big-O] O (n 2 )
- Trường hợp tốt nhất - điều này xảy ra khi danh sách được cung cấp đã được sắp xếp. Thuật toán thực hiện số lần thực thi tối thiểu được biểu thị bằng [Big-Omega] Ω (n)
- Trường hợp trung bình - điều này xảy ra khi danh sách theo thứ tự ngẫu nhiên. Độ phức tạp trung bình được biểu diễn là [Big-theta] ⊝ (n 2 )
3) Không gian phức tạp
Độ phức tạp của không gian đo lượng không gian bổ sung cần thiết để sắp xếp danh sách. Sắp xếp bong bóng chỉ yêu cầu thêm một (1) khoảng trống cho biến thời gian được sử dụng để hoán đổi các giá trị. Do đó, nó có độ phức tạp không gian là O (1).
Tóm lược
- Thuật toán sắp xếp bong bóng hoạt động bằng cách so sánh hai giá trị liền kề và hoán đổi chúng nếu giá trị bên trái nhỏ hơn giá trị bên phải.
- Việc triển khai thuật toán sắp xếp bong bóng tương đối dễ hiểu với Python. Tất cả những gì bạn cần sử dụng là vòng lặp for và câu lệnh if.
- Vấn đề mà thuật toán sắp xếp bong bóng giải quyết là lấy một danh sách ngẫu nhiên các mục và biến nó thành một danh sách có thứ tự.
- Thuật toán sắp xếp bong bóng trong cấu trúc dữ liệu hoạt động tốt nhất khi danh sách đã được sắp xếp vì nó thực hiện một số lần lặp lại tối thiểu.
- Thuật toán sắp xếp bong bóng không hoạt động tốt khi danh sách có thứ tự ngược lại.
- Loại bong bóng có độ phức tạp về thời gian là O (n 2 ) và độ phức tạp về không gian là O (1)
- Thuật toán sắp xếp bong bóng phù hợp nhất cho các mục đích học thuật chứ không phải các ứng dụng trong thế giới thực.
- Sắp xếp bong bóng được tối ưu hóa làm cho thuật toán hiệu quả hơn bằng cách bỏ qua các lần lặp không cần thiết khi kiểm tra các giá trị đã được sắp xếp.