Hướng dẫn bubble sort alphabetical order python - sắp xếp bong bóng thứ tự bảng chữ cái python

Chào bạn! Bài đăng trên blog into-into-code này là bài đầu tiên trong một loạt mà tôi sẽ cố gắng giải thích các khái niệm thành mã theo những cách đơn giản nhất mà tôi có thể.

Đây là blog đầu tiên của tôi, cố gắng làm đơn giản và ngắn gọn về các khái niệm cụ thể mà tôi đã học và chia sẻ nó với bạn.

Giới thiệu về Sắp xếp Bubble

Sắp xếp bong bóng 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 yếu tố theo thứ tự tăng dần hoặc trật tự giảm dần. Tên của nó giống như cách thức hoạt động của thuật toán: với mỗi lần vượt qua mới, yếu tố lớn nhất trong danh sách Bong bóng Bong bóng lên từ danh sách. is the simplest sorting algorithm. It is used to sort elements in Ascending order or Descending order. Its name resembles the way the Algorithm works: with every new pass, the largest element in the list “bubbles up” from the list.

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à trao đổi chúng nếu chúng chưa được phân loại tùy thuộc vào giá trị và thứ tự dự định của chúng.

Về cơ bản, Bubble sắp xếp thực hiện ba nhiệm vụ đơn giản:

1. Liên tục đi qua danh sách các yếu tố để sắp xếp.
2. So sánh các yếu tố liền kề với nhau và sắp xếp chúng.
3. Đổi chúng xung quanh nếu chúng không theo thứ tự dự định

Bubble sắp xếp mã giả

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 giả này, N là chiều 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 phải thực hiện N - 1 trong danh sách của chúng tôi. Nếu chúng tôi có một danh sách 10 mục, chúng tôi sẽ cần so sánh phần tử thứ hai trong danh sách của chúng tôi (ở vị trí 1 trong mảng) và tiếp tục trải qua nó 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 xây dựng ở cuối danh sách, đây là lý do tại sao chúng ta cần tạo ra n - 1 trong danh sách của chúng tôi.

Trong các câu lệnh của chúng tôi, chúng tôi đang so sánh số trong mảng của chúng tôi ở vị trí J với số ở vị trí J + 1 (số liền kề trong danh sách của chúng tôi).

Để 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 loạt các chuỗi [‘g,‘ i, ’a,’ k, ’e,], chúng tôi cũng có thể sử dụng một loạt các số nguyên. Giả sử bạn sử dụng bubble_sort () từ trên cao. Dưới đây, một con số minh họa cho mảng trông như thế nào ở mỗi lần lặp của thuật toán:

Danh sách không được xác định ở trên không phải là trường hợp xấu nhất, danh sách chưa được phân loại trong trường hợp xấu nhất sẽ là một danh sách theo thứ tự giảm dần. Đối với một danh sách như vậy, chứa N các yếu tố, chúng ta cần thực hiện hoán đổi (N-1) để nó được sắp xếp theo thứ tự tăng dần. Quan sát làm thế nào cho vòng đầu tiên bạn cần sắp xếp tất cả các yếu tố N, trong khi ở vòng thứ hai bạn sắp xếp các yếu tố (N-1), v.v.

Thực hiện phân loại bong bóng trong Python

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 phân loại 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))

Output:

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']

Độ phức tạp về thời gian

Độ phức tạp của thời gian của loại bong bóng là O (N²).

Sự kết luận

Điều này đưa chúng ta đến cuối bài viết mà chúng ta đã biết về Sắp xếp bong bóng và việc thực hiện nó trong Python.

Hi vọng điêu nay co ich. Cảm ơn bạn.

Hy vọng bài viết này sẽ giúp. Giữ biểu tượng Claps Claps. Theo dõi để theo dõi trên các blog trong tương lai

Được xuất bản lần đầu tại https://www.numpyninja.com vào ngày 10 tháng 10 năm 2020.

Có một lỗi trong mã sắp xếp bong bóng của bạn có nghĩa là nó sẽ không sắp xếp một số (có thể là hầu hết) danh sách chính xác. Điều này không liên quan gì đến kiểu dữ liệu của các giá trị trong danh sách (nó sẽ có cùng vấn đề với danh sách số hoặc danh sách chuỗi).

Đây là mã cố định:

def bubble(badList):
    length = len(badList) - 1
    unsorted = True

    while unsorted:
        unsorted = False             # this was moved out of the for loop
        for element in range(0,length):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList        # comment this out when you're done testing
                unsorted = True      # this was moved up from the else block

Nó hoạt động cho cả số và chuỗi, như được hiển thị ở đây:

lst = [12, 5, 13, 8, 9, 65]
>>> bubble(lst)
[5, 12, 13, 8, 9, 65]
[5, 12, 8, 13, 9, 65]
[5, 12, 8, 9, 13, 65]
[5, 8, 12, 9, 13, 65]
[5, 8, 9, 12, 13, 65]
>>> lst
[5, 8, 9, 12, 13, 65]
>>> lst = ['a', 'list', 'of', 'words', 'foo', 'bar', 'baz']
>>> bubble(lst)
['a', 'list', 'of', 'foo', 'words', 'bar', 'baz']
['a', 'list', 'of', 'foo', 'bar', 'words', 'baz']
['a', 'list', 'of', 'foo', 'bar', 'baz', 'words']
['a', 'list', 'foo', 'of', 'bar', 'baz', 'words']
['a', 'list', 'foo', 'bar', 'of', 'baz', 'words']
['a', 'list', 'foo', 'bar', 'baz', 'of', 'words']
['a', 'foo', 'list', 'bar', 'baz', 'of', 'words']
['a', 'foo', 'bar', 'list', 'baz', 'of', 'words']
['a', 'foo', 'bar', 'baz', 'list', 'of', 'words']
['a', 'bar', 'foo', 'baz', 'list', 'of', 'words']
['a', 'bar', 'baz', 'foo', 'list', 'of', 'words']
>>> lst
['a', 'bar', 'baz', 'foo', 'list', 'of', 'words']

Làm thế nào để bạn sắp xếp một danh sách theo thứ tự bảng chữ cái trong loại bong bóng trong Python?

Làm cách nào để sắp xếp bảng chữ cái theo loại bong bóng?

Làm thế nào để bạn giải quyết một loại bong bóng trong Python?

Là loại bong bóng tăng dần hoặc giảm dần?