Sắp xếp bong bóng trong python bằng chức năng

Đối với hầu hết mọi người, Sắp xếp bong bóng có thể là thuật toán sắp xếp đầu tiên họ nghe nói đến trong khóa học Khoa học Máy tính

Nó rất trực quan và dễ dàng "dịch" thành mã, điều này rất quan trọng đối với các nhà phát triển phần mềm mới để họ có thể dễ dàng biến ý tưởng thành một dạng có thể thực thi trên máy tính. Tuy nhiên, Sắp xếp bong bóng là một trong những thuật toán sắp xếp hoạt động kém nhất trong mọi trường hợp ngoại trừ việc kiểm tra xem mảng đã được sắp xếp hay chưa, trong đó thuật toán này thường hoạt động tốt hơn các thuật toán sắp xếp hiệu quả hơn như Sắp xếp nhanh

Sắp xếp bong bóng

Ý tưởng đằng sau Sắp xếp bong bóng rất đơn giản, chúng tôi xem xét các cặp phần tử liền kề trong một mảng, từng cặp một và hoán đổi vị trí của chúng nếu phần tử đầu tiên lớn hơn phần tử thứ hai hoặc chỉ cần di chuyển nếu không. Hãy xem một ví dụ và sắp xếp mảng 8, 5, 3, 1, 4, 7, 9

Nếu bạn tập trung vào số đầu tiên, số 8, bạn có thể thấy nó "nổi bong bóng" mảng vào đúng vị trí. Sau đó, quá trình này được lặp lại cho số 5, v.v.

Thực hiện

Với cách trực quan hóa, hãy tiếp tục và thực hiện thuật toán. Một lần nữa, nó cực kỳ đơn giản

Bây giờ, hãy điền vào một danh sách và gọi thuật toán trên đó

our_list = [19, 13, 6, 2, 18, 8]
bubble_sort(our_list)
print(our_list)

đầu ra

[2, 6, 8, 13, 18, 19]

Tối ưu hóa

Việc triển khai đơn giản đã thực hiện công việc của nó, nhưng có hai cách tối ưu hóa mà chúng tôi có thể thực hiện ở đây

Khi không có hoán đổi nào được thực hiện, điều đó có nghĩa là danh sách được sắp xếp. Mặc dù vậy, với thuật toán đã triển khai trước đó, nó sẽ tiếp tục đánh giá phần còn lại của danh sách mặc dù nó thực sự không cần. Để khắc phục điều này, chúng tôi sẽ giữ cờ boolean và kiểm tra xem có bất kỳ giao dịch hoán đổi nào được thực hiện trong lần lặp trước không

Nếu không có giao dịch hoán đổi nào được thực hiện, thuật toán sẽ dừng lại

Cách tối ưu hóa khác mà chúng ta có thể thực hiện tận dụng thực tế là Sắp xếp bong bóng hoạt động theo cách sao cho các phần tử lớn nhất trong một lần lặp cụ thể sẽ kết thúc ở cuối mảng

Lần đầu tiên chúng ta đi qua danh sách, vị trí n được đảm bảo là phần tử lớn nhất, lần thứ hai chúng ta đi qua vị trí n-1 được đảm bảo là phần tử lớn thứ hai, v.v.

Điều này có nghĩa là với mỗi lần lặp liên tiếp, chúng ta có thể xem xét một phần tử ít hơn trước. Chính xác hơn, ở lần lặp thứ k, chỉ cần xét n - k + 1 phần tử đầu tiên

Hãy tiếp tục và so sánh thời gian cần thiết để mỗi đoạn mã này sắp xếp cùng một danh sách hàng nghìn lần bằng cách sử dụng mô-đun timeit

Hãy xem hướng dẫn thực hành, thực tế của chúng tôi để học Git, với các phương pháp hay nhất, tiêu chuẩn được ngành chấp nhận và bao gồm bảng gian lận. Dừng các lệnh Git trên Google và thực sự tìm hiểu nó

Unoptimized Bubble Sort took: 0.0106407

Bubble Sort with a boolean flag took: 0.0078251

Bubble Sort with a boolean flag and shortened list took: 0.0075207

Không có nhiều sự khác biệt giữa hai cách tiếp cận sau do thực tế là danh sách cực kỳ ngắn, nhưng trên các danh sách lớn hơn - cách tối ưu hóa thứ hai có thể tạo ra sự khác biệt lớn

Phần kết luận

Theo cách tiếp cận kém hiệu quả nhất, Sắp xếp bong bóng trải qua n-1 lần lặp, xem xét n-1 cặp phần tử liền kề. Điều này mang lại cho nó độ phức tạp về thời gian là O(n2), trong cả trường hợp tốt nhất và trường hợp trung bình. O(n2) được coi là khá kinh khủng đối với thuật toán sắp xếp

Nó có độ phức tạp không gian O(1), nhưng điều đó không đủ để bù đắp cho những thiếu sót của nó trong các lĩnh vực khác

Tuy nhiên, nó vẫn là một phần quan trọng trong lịch sử và cộng đồng phát triển phần mềm, và sách giáo khoa hầu như không bao giờ không đề cập đến nó khi nói về các thuật toán sắp xếp cơ bản

Sắp xếp bong bóng, hoạt động bằng cách liên tục trao đổi các vật phẩm lân cận nếu chúng sai thứ tự. Trong hướng dẫn này, chúng ta sẽ thực hiện thao tác Sắp xếp bong bóng để sắp xếp một mảng

Sắp xếp bong bóng - Giới thiệu cơ bản

Sắp xếp bong bóng là một thuật toán sắp xếp trong đó hai phần tử liền kề được so sánh và hoán đổi cho đến khi chúng không còn theo thứ tự mong muốn. Trong thao tác này, mỗi phần tử của mảng di chuyển đến cuối trong mỗi lần lặp, tương tự như cách bong bóng khí nổi lên mặt nước

Hãy để chúng tôi có một sự hiểu biết sơ bộ về sắp xếp bong bóng

1. So sánh và Hoán đổi. - So sánh các mục đầu tiên và thứ hai bắt đầu với chỉ số đầu tiên. Phần tử thứ nhất và thứ hai được chuyển đổi nếu phần tử thứ nhất lớn hơn phần tử thứ hai. So sánh các mục thứ hai và thứ ba bây giờ. Nếu chúng không theo đúng trình tự, hãy hoán đổi chúng. Quy trình tiếp tục cho đến khi mục cuối cùng được thêm vào
2. Vòng lặp còn lại. - Các lần lặp còn lại thực hiện tương tự. Phần tử lớn nhất trong số các mục chưa sắp xếp được đặt ở cuối mỗi lần lặp
3. Kết quả sau mỗi thao tác là một mảng đã được sắp xếp

Để hiểu rõ hơn chúng ta hãy xem sơ đồ dưới đây

thuật toán

Đến bây giờ, chúng tôi đã hiểu sơ bộ về cách sắp xếp hợp nhất được thực hiện. Để hiểu rõ hơn, hãy đi sâu vào thuật toán, sau đó là mã

1. Tạo hàm Bubble_Sort()
2. Truyền mảng tham số cho hàm
3. Tạo một vòng lặp để truy cập từng mảng
4. Tạo vòng lặp so sánh các phần tử mảng
5. So sánh hai phần tử liền kề
6. Hoán đổi các phần tử nếu không theo thứ tự
7. Kết quả sẽ là một mảng được sắp xếp
8. In mảng

Chương trình sắp xếp bong bóng

Như đã thảo luận ở trên về thuật toán, bây giờ chúng ta hãy đi sâu vào phần lập trình của thao tác Sắp xếp bong bóng chịu ảnh hưởng của thuật toán

def bubbleSort(array):
  # access each element
  for a in range(len(array)):
     # compare array elements
    for b in range(0, len(array) - a - 1):
      # compare 
      if array[b] > array[b + 1]:
          
        # swapping elements
        temp = array[b]
        array[b] = array[b+1]
        array[b+1] = temp

#driver code
array = [5, 4, 2, 1, 3]
print("The original array is: ", array)

bubbleSort(array)
print('The Sorted Array is: ', array)

Mảng ban đầu là. [5, 4, 2, 1, 3]
Mảng được sắp xếp là. [1, 2, 3, 4, 5]

Phần kết luận

Trong hướng dẫn này, chúng tôi đã thực hiện thao tác Sắp xếp bong bóng trong python để sắp xếp một mảng. Sắp xếp bong bóng được sử dụng khi độ phức tạp không thành vấn đề. Độ phức tạp trường hợp tốt nhất của sắp xếp bong bóng là O(n) và độ phức tạp trường hợp trung bình xấu nhất là O(n2), độ phức tạp không gian của sắp xếp bong bóng là O(1)

Chức năng của sắp xếp bong bóng là gì?

Công thức cho sắp xếp bong bóng là gì?

Thuật toán của phương thức sort() trong Python là gì?

Python có chức năng sắp xếp hợp nhất không?