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