Một là gì Sắp xếp bong bóng ?

Sắp xếp bong bóng 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ố đường chuyền trong một Sắp xếp bong bóng bằng số phần tử trong danh sách trừ đi một.

Trong này Sắp xếp bong bóng Trong Python hướng dẫn bạn sẽ học:

Thực hiện Sắp xếp bong bóng Thuật toán

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

Các Sắp xếp bong bóng thuật toán 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ần 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 lần chuyển trong (n – 1) lần đối với đường 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 vượt ngoài cùng (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.

Tối ưu hóa Sắp xếp bong bóng Thuật toán

Theo mặc định, thuật toán cho 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 tiếp theo được bắt đầu cho đến khi quá trình hoàn tất như được hiển thị trong hình dưới đây Sắp xếp bong bóng thí dụ.

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 đến 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.

Một tối ưu hóa Sắp xếp bong bóng hiệu quả hơn vì nó chỉ thực thi những điều cần thiết và bỏ qua những điều không cần thiết.

Đại diện trực quan

Đưa ra danh sách năm yếu tố, những hình ảnh sau đây minh họa cách Sắp xếp bong bóng lặp 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

Python Các ví dụ

Đoạn mã sau đây cho thấy cách triển khai Sắp xếp bong bóng thuật toán trong Con trăn.

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)

Đang thực hiện ở trên Sắp xếp bong bóng chương trình 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 Sắp xếp bong bóng mã chương trình như sau

NƠI ĐÂY,

  1. Xác định một chức năng bubbleSort chấp nhận một tham số theSeq . Mã không xuất ra bất cứ thứ gì.
  2. 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ì
  3. Bắt đầu một vòng lặp for chạy Sắp xếp bong bóng thuật toán (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ì
  4. 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ì
  5. 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ì.
  6. 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ì.
  7. Gán giá trị của theSeq[j] thành một biến thời gian tmp nếu điều kiện đánh giá là true. Mã không xuất ra bất cứ thứ gì
  8. Giá trị của theSeq[j + 1] được giao cho vị trí của theSeq[j]. Mã không xuất ra bất cứ thứ gì
  9. 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ì
  10. 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ì
  11. 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ì
  12. 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.
  13. 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.
  14. Đị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ì.
  15. Gán giá trị của hàm bubbleSort đến một kết quả thay đổi.
  16. In giá trị của kết quả biến.

Sắp xếp bong bóng thuận lợi

Sau đây là một số ưu điểm của Sắp xếp bong bóng thuật toán

  • 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.
  • Rấ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 Sắp xếp bong bóng thuật toán

  • 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ự n2

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 để thể hiện số lượng thời gian thực thi và không gian cần thiết để sắp xếp danh sách. Các 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

Sự phức tạp về thời gian của Sắp xếp bong bóng O (n2)

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 (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ầ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 thị bằng [Big-theta] ⊝ (n2)

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. Các 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).

Bản tóm tắt

  • Các Sắp xếp bong bóng thuật toán 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.
  • Thực hiện một Sắp xếp bong bóng thuật toán tương đối thẳng 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à Sắp xếp bong bóng thuật toán giải 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ự.
  • Các Sắp xếp bong bóng thuật toán 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.
  • Các Sắp xếp bong bóng thuật toán không hoạt động tốt khi danh sách có thứ tự ngược lại.
  • Loại bọt có độ phức tạp về thời gian là O (n2) và sự phức tạp về không gian của 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.
  • Tối ưu hóa Sắp xếp bong bóng 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.

Trong bài viết này, chúng tôi đã giải thích Sắp xếp bong bóng là gì? Cách triển khai thuật toán sắp xếp bong bóng [Detailed Guide]. Đừng ngần ngại cho chúng tôi biết nếu bạn có câu hỏi hoặc nhận xét về bài viết này. Để lại bình luận bên dưới và softgeek.org sẽ phản hồi trong thời gian sớm nhất.