Làm thế nào để bạn sắp xếp một danh sách trong sắp xếp bong bóng trong python?

def bubbleSort[nlist]:
    for passnum in range[len[nlist]-1,0,-1]:
        for i in range[passnum]:
            if nlist[i]>nlist[i+1]:
                temp = nlist[i]
                nlist[i] = nlist[i+1]
                nlist[i+1] = temp

nlist = [14,46,43,27,57,41,45,21,70]
bubbleSort[nlist]
print[nlist]

[14, 21, 27, 41, 43, 45, 46, 57, 70]

Mức độ khó của bài tập này là gì?

Kiểm tra kỹ năng Lập trình của bạn với bài kiểm tra của w3resource

Theo dõi chúng tôi trên Facebook và Twitter để cập nhật thông tin mới nhất.

con trăn. Lời khuyên trong ngày

Độ dài bit

Lưu ý rằng số nguyên 4 thực sự đại diện cho 5 giá trị bao gồm 0 do đó cần 3 bit
00
01
10
11
100 -> 4
101 -> 5

x=5
y=x.bit_length[]
print[y]
z=500
a=z.bit_length[]
print[a]

đầu ra

3
9

• Xu hướng hàng tuần
• Bài tập lập trình Java cơ bản
• Truy vấn con SQL
• Bài tập cơ sở dữ liệu Adventureworks
• Bài tập cơ bản C# Sharp
• SQL COUNT[] với sự khác biệt
• Bài tập chuỗi JavaScript
• Xác thực biểu mẫu HTML JavaScript
• Bài tập bộ sưu tập Java
• hàm SQL COUNT[]
• Tham gia bên trong SQL
• Hàm JavaScript Bài tập
• Hướng dẫn Python
• Bài tập mảng Python
• Tham gia chéo SQL
• Bài tập về mảng Sharp trong C#

Trong bài viết này, chúng tôi đã giải thích cơ bản về Sắp xếp bong bóng cùng với giải thích chi tiết về việc triển khai Sắp xếp bong bóng trong Python trong Python

Mục lục

1. Giới thiệu về Sắp xếp bong bóng
2. Triển khai Python của Sắp xếp bong bóng với lời giải thích
3. Độ phức tạp và thời gian chạy
4. Các ứng dụng của Sắp xếp bong bóng

Hãy để chúng tôi bắt đầu triển khai Sắp xếp bong bóng trong danh sách bằng Python

Thuật toán sắp xếp bong bóng sắp xếp một danh sách chưa được sắp xếp theo đúng thứ tự. Nó liên quan đến việc xem xét hai phần tử liền kề của một danh sách và sau đó hoán đổi chúng theo đúng thứ tự. Điều này được thực hiện cho đến khi kết thúc danh sách và cho đến khi tất cả các phần tử kết thúc theo đúng thứ tự. Việc đổi chỗ các phần tử chỉ xảy ra khi các phần tử liền kề không đúng thứ tự. Các số lớn hơn nổi lên ở bên phải khi sắp xếp, do đó có tên là sắp xếp bong bóng

Cú pháp và lưu lượng

Thuật toán sắp xếp bong bóng có thể được thực hiện dễ dàng bằng cách sử dụng vòng lặp for. Việc triển khai yêu cầu các bước sau-

1. Lấy chiều dài [i. e số phần tử trong một danh sách] của danh sách. Đặt số lượng phần tử trong danh sách là 'n'
2. Đi qua danh sách 'n' số lần và tạo một biến để kiểm tra mọi giao dịch hoán đổi. Duyệt qua tất cả các phần tử của danh sách 'n-i-1' mỗi lần. Điều này là do ở mỗi lần lặp, phần tử cuối cùng luôn được đặt theo đúng thứ tự
3. Khi duyệt qua tất cả các phần tử, mỗi lần kiểm tra xem phần tử hiện tại có lớn hơn phần tử tiếp theo không. Nếu vậy, trao đổi chúng
4. Nếu không xảy ra hoán đổi, thoát ra khỏi vòng lặp
5. In danh sách đã sắp xếp cuối cùng

Chương trình sau sắp xếp một danh sách chưa sắp xếp bằng vòng lặp for và in kết quả cuối cùng

# a function to sort a list using bubble sort algorithm
def bubblesort[lst]:
        # get the length of the list
        n = len[lst]
        # go through the list n number of times
        for i in range[n]:
                # variable to keep check for any swaps
                swap = False
                # traverse through all adjacent elements
                for j in range[0, n-i-1]:
                    # if current element greater than next element, swap them
                    if lst[j]>lst[j+1]:
                        lst[j], lst[j+1] = lst[j+1], lst[j]
                        swap = True
                # if no swaps, then break out of the loop
                if swap == False:
                        break
        # print the final sorted list
        print[lst]

# an example unsorted list 
y = [1,5,4,6,7,8,3,2,12,10,9,11]

# function call to sort list y
bubblesort[y]

1. Đầu tiên, chúng ta tạo một hàm có tên là 'bubblesort' bằng cách sử dụng câu lệnh def. Câu lệnh này được sử dụng bất cứ khi nào chúng ta cần tạo một hàm tùy chỉnh cho chương trình của mình bằng Python. Tên hàm có thể là bất cứ thứ gì, nhưng 'bubblesort' có ý nghĩa ở đây vì trọng tâm là thuật toán sắp xếp bong bóng. Để tạo một hàm, trước tiên hãy nhập def theo sau là tên ưa thích của hàm. Sau đó, bên trong dấu ngoặc đơn, trong định nghĩa hàm, chúng ta truyền vào các tham số, là bí danh của biến thực tế mà sau này chúng ta truyền vào lệnh gọi hàm. Hãy coi các tham số là các biến tạm thời mà chúng ta sử dụng bên trong hàm để chỉ định các thay đổi sẽ được thực hiện trên biến thực tế. Ở đây tham số được đặt tên là lst

2. Sau đó, chúng tôi tạo một biến có tên 'n' lưu trữ độ dài đó của danh sách [số lượng mục trong danh sách]. Để biết độ dài của danh sách trong Python, hãy nhập len và bên trong dấu ngoặc đơn, nhập tên của danh sách. Ở đây, vì nó là một định nghĩa hàm, nên chúng ta chuyển vào biến tạm thời như trước, đó là tham số có tên lst

3. Sau đó, chúng tôi sử dụng vòng lặp for đi qua danh sách 'n' số lần. Giá trị của i nằm trong khoảng từ 0 đến 'n-1', vì từ khóa phạm vi bao gồm giá trị cho đến 'n' nhưng không bao gồm 'n'. Do đó, đối với tất cả các giá trị của 'i' ngụ ý các giá trị bắt đầu từ 0 trở lên nhưng không bao gồm 'n'

4. Sau đó, chúng tôi tạo một biến có tên là swap lưu trữ giá trị boolean [ i. đúng hay sai]. Chúng tôi sử dụng biến này sau để kiểm tra xem có bất kỳ giao dịch hoán đổi nào xảy ra hay không. Giá trị ban đầu được đặt thành False, ngụ ý rằng cho đến nay, không có hoán đổi nào xảy ra

5. Sau đó, chúng ta tạo một vòng lặp for khác, lần này chứa câu lệnh if, để duyệt qua tất cả các phần tử liền kề và để kiểm tra xem phần tử hiện tại có lớn hơn phần tử tiếp theo không. Điều kiện của câu lệnh if lst[j]>lst[j+1] luôn trả về giá trị boolean [Đúng hoặc Sai] và mã bên trong câu lệnh if chỉ chạy khi điều kiện này là Đúng. Chúng tôi sử dụng toán tử lớn hơn > để kiểm tra các giá trị. Khi điều này đúng, chúng tôi hoán đổi các phần tử bằng cách đặt phần tử hiện tại và gán cho nó giá trị của phần tử tiếp theo và ngược lại. Vì lst là bí danh của một danh sách, để xem bên trong danh sách, chúng tôi sử dụng dấu ngoặc vuông

   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
   

   1. Sau đó, chúng tôi đặt biến swap là True, ngụ ý rằng bây giờ đã xảy ra hoán đổi. Trong trường hợp không xảy ra hoán đổi, không có thay đổi nào xảy ra với biến swap

6. Sau khi chúng tôi thoát khỏi vòng lặp thứ hai, chúng tôi kiểm tra mọi giao dịch hoán đổi. Đối với điều này, chúng tôi kiểm tra biến swap. Và một lần nữa sử dụng câu lệnh if và toán tử đẳng thức

   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
   

   5 để kiểm tra mọi giao dịch hoán đổi. Nếu biến swap là Sai, nó có nghĩa là không có hoán đổi và do đó, chúng tôi thoát ra khỏi toàn bộ vòng lặp for chính bằng cách sử dụng câu lệnh

   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
   

   7. Chúng tôi sử dụng câu lệnh này bất cứ khi nào chúng tôi muốn thoát khỏi bất kỳ vòng lặp nào trong Python

7. Sau khi thoát khỏi vòng lặp for cuối cùng, chúng ta sử dụng hàm

   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
   

   8 và truyền vào tham số lst để in danh sách đã sắp xếp cuối cùng. Và một lần nữa, vì nó là một định nghĩa hàm, nên chúng ta sử dụng biến tạm thời, là tham số có tên lst

8. Trong ví dụ trên, chúng tôi sử dụng danh sách có tên def1 để kiểm tra chức năng sắp xếp bong bóng của chúng tôi. Danh sách này có 12 phần tử. Để sử dụng hàm [hoặc theo thuật ngữ chính thức, để gọi hàm], chúng ta nhập tên của hàm, theo sau là dấu ngoặc đơn và bên trong nó, chúng ta nhập tên của danh sách mà chúng ta muốn sắp xếp

Chạy chương trình trên cho kết quả sau

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

• Ký hiệu Big-O. Trong trường hợp xấu nhất, thuật toán sắp xếp bong bóng có thời gian chạy n ô vuông. Điều này là do, tối đa, chúng tôi duyệt qua danh sách chưa sắp xếp 'n' số lần và duyệt qua tất cả các phần tử 'n-i-1' lần. Khi 'n' ngày càng lớn hơn, chúng ta có xu hướng bỏ qua các hằng số. Vì vậy, cuối cùng, tổng số bước mà thuật toán trải qua là [n]x[n]i. e n bình phương

• Ký hiệu Big-Omega. Trong trường hợp tốt nhất, thuật toán sắp xếp bong bóng có thời gian chạy là 'n'. Điều này là do, tối thiểu, ngay cả khi tất cả các phần tử của danh sách đã được sắp xếp, chúng ta vẫn phải duyệt qua danh sách một lần để kiểm tra

• Sắp xếp bong bóng là một thuật toán phát hiện các lỗi thậm chí rất nhỏ trong các mảng/danh sách không được sắp xếp hoàn toàn. Điều này được sử dụng trong đồ họa máy tính

• Trên các tập dữ liệu nhỏ, thuật toán sắp xếp bong bóng tốt hơn so với sắp xếp lựa chọn về độ phức tạp của thời gian

  Bạn có thể bong bóng sắp xếp một danh sách?

  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.

  Sắp xếp bong bóng hoạt động như thế nào trong Python?

  Sắp xếp bong bóng là thuật toán sắp xếp đơn giản nhất hoạt động bằng cách hoán đổi liên tục các phần tử liền kề nếu chúng sắp xếp sai thứ tự

  Cách nhanh nhất để sắp xếp danh sách trong Python là gì?

  Cách dễ nhất để sắp xếp là sử dụng hàm sorted[list] , hàm này lấy một danh sách và trả về một danh sách mới với các phần tử đó trong . Danh sách ban đầu không thay đổi. Thông thường nhất là chuyển một danh sách vào hàm sorted[], nhưng trên thực tế, nó có thể lấy bất kỳ loại bộ sưu tập có thể lặp nào làm đầu vào.

  Làm thế nào để thuật toán sắp xếp bong bóng biết danh sách được sắp xếp?

  Thuật toán sắp xếp bong bóng duyệt qua danh sách dữ liệu nhiều lần, so sánh hai mục nằm cạnh nhau để xem mục nào không theo thứ tự.