Đây là blog đầu tiên của tôi, cố gắng viết đơn giản và ngắn gọn về các khái niệm cụ thể mà tôi đang tìm hiểu và chia sẻ nó với bạn
Giới thiệu về Sắp xếp bong bóng
Bubble Sort là thuật toán sắp xếp đơn giản nhất. Nó được sử dụng để sắp xếp các phần tử theo thứ tự tăng dần hoặc giảm dần. Tên của nó giống với cách hoạt động của Thuật toán. với mỗi lần vượt qua mới, phần tử lớn nhất trong danh sách sẽ "nổi bong bóng" khỏi danh sách
Sắp xếp bong bóng bao gồm nhiều lần đi qua một danh sách. Trong mỗi lần vượt qua, thuật toán so sánh các phần tử liền kề và hoán đổi chúng nếu chúng chưa được sắp xếp tùy thuộc vào giá trị và thứ tự dự định của chúng
Về cơ bản, sắp xếp bong bóng thực hiện ba nhiệm vụ đơn giản
Lặp đi lặp lại danh sách các phần tử để sắp xếp
So sánh các phần tử liền kề với nhau và sắp xếp chúng
Trao đổi chúng xung quanh nếu chúng không theo thứ tự dự định
bubbleSort[inputArray]
n = length[inputArray]
for [1= 0 until n]
for [j = 0 until n-i-1]
if[array[j] > array[j + 1]]
swap[array, j, j+1]
Trong mã giả này, n là độ dài của mảng của chúng tôi. Để đảm bảo rằng toàn bộ danh sách của chúng tôi được sắp xếp, chúng tôi cần thực hiện n — 1 lượt trong danh sách của mình. Nếu chúng tôi có một danh sách gồm 10 mục, chúng tôi sẽ cần so sánh phần tử thứ hai của danh sách của chúng tôi [ở vị trí 1 trong mảng] và tiếp tục lặp lại 9 lần cho đến khi chúng tôi sắp xếp toàn bộ danh sách. Một bong bóng được sắp xếp đang hình thành ở cuối danh sách, đây là lý do tại sao chúng ta cần thực hiện n — 1 lần vượt qua trong danh sách của mình
Trong các câu lệnh if của chúng ta, chúng ta đang so sánh số trong mảng ở vị trí j với số ở vị trí j + 1 [số liền kề trong danh sách của chúng ta]
Để phân tích chính xác cách thức hoạt động của thuật toán này, ở đây chúng tôi đang xem xét một Mảng các chuỗi [‘g’, ‘i’, ‘a’, ‘k’, ‘e’], chúng tôi cũng có thể sử dụng một mảng các số nguyên. Giả sử bạn đang sử dụng bubble_sort[] từ phía trên. Đây là một hình minh họa mảng trông như thế nào ở mỗi lần lặp lại thuật toán
Danh sách chưa sắp xếp ở trên không phải là trường hợp xấu nhất, danh sách chưa sắp xếp trong trường hợp xấu nhất sẽ là danh sách theo thứ tự giảm dần. Đối với một danh sách như vậy, chứa n phần tử, chúng ta cần thực hiện [n-1] phép hoán đổi để nó được sắp xếp theo thứ tự tăng dần. Quan sát cách đối với vòng đầu tiên, bạn cần sắp xếp tất cả các phần tử n , trong khi ở vòng thứ hai, bạn sắp xếp . elements and so on and so forth.
Dưới đây là triển khai để sắp xếp một mảng số nguyên/chuỗi bằng cách sử dụng sắp xếp bong bóng trong Python
def bubble_sort[arr]:
n = len[arr]
for i in range[n]:
for j in range[n - i - 1]:
if arr[j] > arr[j + 1]:
# sorting by using simultaneous assignment in python
arr[j], arr[j + 1] = arr[j + 1], arr[j]
arr1 = [7, 4, 3, 6, 2]
arr2 = ['g', 'i', 'a', 'k', 'e']
print['Before sorting an Integer Array: {}'.format[arr1]]
bubble_sort[arr1]
print['After sorting an Integer Array: {}'.format[arr1]]
print['Before sorting an String Array: {}'.format[arr2]]
bubble_sort[arr2]
print['After sorting an String Array: {}'.format[arr2]]
đầu ra
Before sorting an Integer Array: [7, 4, 3, 6, 2]
After sorting an Integer Array: [2, 3, 4, 6, 7]
Before sorting an String Array: ['g', 'i', 'a', 'k', 'e']
After sorting an String Array: ['a', 'e', 'g', 'i', 'k']Thời gian phức tạp
Độ phức tạp về thời gian của Sắp xếp bong bóng là O[n²]
Phần kết luận
Điều này đưa chúng ta đến phần cuối của bài viết, nơi chúng ta đã tìm hiểu về Sắp xếp bong bóng và cách triển khai nó trong python
Sắp xếp bong bóng hoạt động như thế nào trong Python?
Làm thế nào sắp xếp bong bóng hoạt động với ví dụ?
Sắp xếp bong bóng có khó không?
Khi nào bạn không nên sử dụng sắp xếp bong bóng?