Đố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.0075207Khô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
- 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
- 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
- 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ã
- Tạo hàm Bubble_Sort()
- Truyền mảng tham số cho hàm
- Tạo một vòng lặp để truy cập từng mảng
- Tạo vòng lặp so sánh các phần tử mảng
- So sánh hai phần tử liền kề
- Hoán đổi các phần tử nếu không theo thứ tự
- Kết quả sẽ là một mảng được sắp xếp
- 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)