Một loại bong bóng Python đi qua một danh sách và so sánh các yếu tố cạnh nhau. Nếu một phần tử bên phải lớn hơn một ở bên trái, các phần tử được hoán đổi. Điều này xảy ra cho đến khi danh sách được sắp xếp. Show
Bạn có cần sắp xếp một danh sách? Các loại bong bóng đã trở lại của bạn. Sắp xếp bong bóng là một loại thuật toán tiêu chuẩn sắp xếp danh sách. Nó có lẽ là loại đơn giản nhất ngoài kia, vì vậy, nó hoàn hảo cho những người mới bắt đầu mới sắp xếp các thuật toán!  Tìm Bootcamp của bạn phù hợp
Chọn mối quan tâm của bạn họ Tên điện thoại Email Tên của bạn Bằng cách tiếp tục, bạn đồng ý với các điều khoản dịch vụ và chính sách quyền riêng tư của chúng tôi và bạn đồng ý nhận được các ưu đãi và cơ hội từ Karma nghề nghiệp qua điện thoại, tin nhắn văn bản và email. Trong hướng dẫn này, chúng tôi sẽ thảo luận về cách các loại bong bóng hoạt động và cách bạn có thể thực hiện thuật toán sắp xếp bong bóng Python. Chúng tôi sẽ trải qua một ví dụ để bạn hiểu cách mỗi phần của một loại bong bóng hoạt động. Python bong bóng sắp xếpMột loại bong bóng so sánh các cặp phần tử liền kề và hoán đổi các yếu tố đó nếu chúng không theo thứ tự. Nó thường được thực hiện trong Python để sắp xếp các danh sách các số chưa được phân loại. Các loại bong bóng là một thuật toán khoa học máy tính tiêu chuẩn. Bằng cách sử dụng một loại bong bóng, bạn có thể sắp xếp dữ liệu theo thứ tự tăng dần hoặc giảm dần. Bắt đầu từ phần tử đầu tiên trong danh sách, một loại bong bóng sẽ so sánh các phần tử thứ nhất và thứ hai. Nếu phần tử thứ nhất lớn hơn phần thứ hai, một hoán đổi xảy ra. Quá trình này được lặp lại cho đến khi mọi mục trong danh sách được kiểm tra. Sau đó, một loại bong bóng sẽ lặp lại trong danh sách một lần nữa. Điều này xảy ra cho đến khi không cần phải thực hiện hoán đổi. Khi nào bạn nên sử dụng một loại bong bóng trong Python?Các loại bong bóng là một phương pháp sắp xếp tốt để sử dụng khi bạn chỉ bắt đầu tìm hiểu về các thuật toán sắp xếp. Một loại bong bóng là một cách đơn giản để sắp xếp một danh sách các mục không xuất hiện theo thứ tự. Sắp xếp bong bóng hoạt động tốt nhất khi bạn có một danh sách chỉ có một vài đối tượng. Điều này là do khi một loại bong bóng chỉ phải so sánh một vài so sánh, nó rất nhanh. Khi bạn cần sắp xếp một danh sách lớn hơn, có nhiều thuật toán hiệu quả hơn mà bạn có thể sử dụng. Hầu hết các nhà phát triển sẽ chọn sử dụng một phương thức như sắp xếp chèn để sắp xếp danh sách các mục dài hơn. Thuật toán loại bong bóng Python: hướng dẫnHãy để Lừa vào cỏ dại và bắt đầu bước qua cách thức hoạt động của một bong bóng. Chúng tôi sẽ bắt đầu với danh sách sau, có các yếu tố xuất hiện theo thứ tự sai: Sắp xếp bong bóng của chúng tôi bắt đầu bằng cách so sánh các yếu tố thứ nhất và thứ hai trong danh sách của chúng tôi. Nếu phần tử thứ nhất lớn hơn phần thứ hai, thì chúng ta trao đổi hai yếu tố này. Trong ví dụ này, chúng ta sẽ so sánh 7 và 19. 7 không lớn hơn 19, vì vậy nó ở cùng một nơi. Danh sách của chúng tôi bây giờ trông giống như trước đây: Bây giờ chúng tôi sẽ tiếp tục so sánh các yếu tố thứ hai và thứ ba trong danh sách của chúng tôi. 19 lớn hơn 4, điều đó có nghĩa là chúng ta cần trao đổi chúng. Danh sách của chúng tôi bây giờ trông như thế này: Bây giờ chúng tôi có thể so sánh các mục thứ ba và thứ tư trong danh sách của chúng tôi. 19 lớn hơn 12, vì vậy chúng tôi trao đổi hai số: Đạt đến cuối danh sáchDanh sách của chúng tôi đã bắt đầu trông được sắp xếp. Nhưng chúng tôi đã đạt đến cuối danh sách của chúng tôi và nó không được sắp xếp. Chuyện gì đang xảy ra? Các loại bong bóng tạo ra nhiều lần qua một danh sách, điều đó có nghĩa là chúng tiếp tục chạy cho đến khi mọi mục trong danh sách được sắp xếp. Sắp xếp bong bóng của chúng tôi sẽ bắt đầu lại từ đầu cho đến khi danh sách được sắp xếp. Chúng tôi gọi mỗi khi danh sách bắt đầu sắp xếp các giá trị từ đầu một lần vượt qua. Trong ví dụ này, loại bong bóng của chúng tôi sẽ so sánh 7 và 4. 7 lớn hơn 4, vì vậy chúng tôi trao đổi các yếu tố:a pass. In this example, our bubble sort will compare 7 and 4. 7 is greater than 4, so we swap the elements: Thuật toán của chúng tôi so sánh 7 và 12. Không cần trao đổi, vì vậy chúng tôi sẽ tiếp tục. Chúng tôi so sánh 12 và 19. Một lần nữa không cần trao đổi. Bây giờ chúng tôi đã đạt đến cuối danh sách của mình, nó rõ ràng là không cần phải hoán đổi nữa. Bạn có nhận thấy rằng thuật toán của chúng tôi tiếp tục đi ngay cả sau khi danh sách của chúng tôi được sắp xếp? Điều đó bởi vì một loại bong bóng sẽ tiếp tục trao đổi các phần tử cho đến khi nó so sánh mọi mục trong danh sách cho mỗi mục trong danh sách. Thuật toán của chúng tôi sẽ không dừng lại cho đến khi mỗi lần trao đổi đã diễn ra. Chương trình Python sắp xếp bong bóngCho đến bây giờ, chúng tôi đã hoán đổi số trong một bảng. Thật đúng là chúng tôi đã xoay sở để sắp xếp danh sách của mình, nhưng chúng tôi không phải làm điều này bằng tay. Các loại bong bóng là một thuật toán tính toán sau tất cả; Hãy để một máy tính chạy thuật toán cho chúng tôi. Hãy bắt đầu bằng cách viết một hàm Python sắp xếp một danh sách các số theo thứ tự tăng dần: def sortList(array): for item in range(len(array)): for j in range(0, (len(array) - item - 1)): if array[j] > array[j + 1]: (array[j], array[j + 1]) = (array[j + 1], array[j]) Thuật toán của chúng tôi bắt đầu với một vòng lặp. Vòng lặp này lặp qua mọi mục trong mảng của chúng tôi. Sau đó, chúng tôi sử dụng một vòng khác để so sánh tất cả các mục trong mảng của chúng tôi với nhau. Trong mã của chúng tôi, chúng tôi đã xác định một câu lệnh Python, nếu có thể kiểm tra xem một mục nhất định có lớn hơn mục tiếp theo trong danh sách hay không. Tuyên bố này của IF IF IF sẽ thực hiện các so sánh như:
Mã của chúng tôi chưa được hoàn thành. Nếu bạn cố gắng chạy chương trình Python ở trên, sẽ không có gì xảy ra. Chúng tôi phải gọi chức năng của chúng tôi và cung cấp cho nó một số dữ liệu: numbers = [7, 19, 4, 12]
sortList(numbers)
print("List in order:", numbers)
Mã của chúng tôi trả về: List in order: [4, 7, 12, 19] Chúng ta làm được rồi! Mảng Python của chúng tôi được sắp xếp theo thứ tự tăng dần! Bạn có thể sử dụng một loại bong bóng để sắp xếp một danh sách theo thứ tự giảm dần. Để làm như vậy, hãy trao đổi số lượng lớn hơn dấu hiệu với một dấu hiệu nhỏ hơn là dấu hiệu trong câu lệnh Python, nếu có: if array[j] < array[j + 1]: Khi chúng tôi chạy chương trình của mình với dòng mã sửa đổi này, phần sau được trả về: List in order: [19, 12, 7, 4] Tối ưu hóa loại bong bóngTrước đó, chúng tôi đã nói về cách mọi so sánh có thể được thực hiện ngay cả khi danh sách của chúng tôi được sắp xếp. Điều này làm cho bong bóng của chúng tôi sắp xếp không hiệu quả: nó tiếp tục ngay cả sau khi danh sách được sắp xếp. Mặc dù nó không tạo ra sự khác biệt lớn trong ví dụ này, nhưng ở quy mô, điều này có thể ảnh hưởng đến thời gian thực hiện của một chương trình. Đó là nơi mà loại bong bóng được tối ưu hóa xuất hiện. "Karma nghề nghiệp bước vào cuộc sống của tôi khi tôi cần nó nhất và nhanh chóng giúp tôi kết hợp với bootcamp. Hai tháng sau khi tốt nghiệp, tôi tìm thấy công việc mơ ước của mình phù hợp với các giá trị và mục tiêu của tôi trong cuộc sống!" Sao Kim, Kỹ sư phần mềm tại Rockbot Chúng tôi có thể tối ưu hóa sắp xếp bong bóng của chúng tôi bằng cách viết một biến mới. Hãy gọi nó là hoán đổi. Biến này sẽ theo dõi xem có bất kỳ giao dịch hoán đổi nào đã diễn ra trong Python cho vòng lặp hay không. Nếu biến này được đặt thành sai, thì điều đó có nghĩa là danh sách của chúng tôi được sắp xếp. Không cần lặp lại nữa. Hãy để sửa đổi chức năng Danh sách sắp xếp của chúng tôi từ trước đó: def sortList(array): for item in range(len(array)): swap = True for j in range(0, (len(array) - item - 1)): if array[j] > array[j + 1]: (array[j], array[j + 1]) = (array[j + 1], array[j]) swap = False if swap == True: break Chúng tôi đã xác định một biến có tên SWAP có giá trị mặc định: true. Điều này được chứa trong vòng lặp đầu tiên của chúng tôi vì nó theo dõi xem việc hoán đổi có xảy ra trên mỗi lần truyền qua danh sách hay không. Nếu mảng của chúng tôi so sánh, giá trị của hoán đổi được đặt thành sai. Nếu không có sự hoán đổi được thực hiện trong hoán đổi cuối cùng, thì mảng đã được sắp xếp. Danh sách của chúng tôi sau đó sẽ kiểm tra xem hoán đổi có bằng đúng không. Nếu có, chương trình của chúng tôi sẽ ngừng thực hiện. Hãy cùng chạy mã của chúng tôi một lần nữa: List in order: [4, 7, 12, 19] Dữ liệu của chúng tôi đã được sắp xếp theo cùng một cách nhưng thuật toán của chúng tôi hiện nhanh hơn và hiệu quả hơn. Thuật toán của chúng tôi bây giờ dừng lại ngay khi tất cả các mục trong danh sách đã được sắp xếp. Phân tích độ phức tạpĐộ phức tạp thời gian trung bình của loại bong bóng là O (n^2). Điều này xảy ra khi các yếu tố trong một mảng chưa được phân loại. Trong trường hợp xấu nhất, một loại bong bóng thực hiện tại O (n^2). Điều này xảy ra khi một mảng đã theo thứ tự tăng dần hoặc giảm dần và cần được sắp xếp theo cách ngược lại. Trong trường hợp tốt nhất, thuật toán này sẽ thực hiện tại O (n). Điều này xảy ra nếu một mảng đã được sắp xếp. Để tìm hiểu thêm về sự phức tạp của thuật toán, hãy xem hướng dẫn ký hiệu nghiệp của chúng tôi. Sự kết luậnCác loại bong bóng cung cấp một cách đơn giản trong đó bạn có thể sắp xếp một danh sách dữ liệu. Chúng có thể được sử dụng để sắp xếp dữ liệu theo thứ tự tăng dần hoặc giảm dần. Thuật toán này được sử dụng phổ biến nhất khi bạn cần sắp xếp một danh sách nhỏ. Các loại bong bóng là một giới thiệu tốt về các thuật toán sắp xếp. Bạn có thể sử dụng chúng để giúp làm quen với các thuật toán trước khi bạn tìm hiểu về các phương pháp sắp xếp nâng cao hơn, chẳng hạn như sắp xếp chèn. Để được hướng dẫn chuyên gia về tài nguyên và khóa học Python, hãy xem Cách học hướng dẫn Python của chúng tôi. Làm thế nào để bong bóng sắp xếp làm việc từng bước?Một thuật toán sắp xếp bong bóng đi qua một danh sách dữ liệu một số lần, so sánh hai mục nằm cạnh nhau để xem cái nào không đúng thứ tự. Nó sẽ tiếp tục đi qua danh sách dữ liệu cho đến khi tất cả dữ liệu được sắp xếp theo thứ tự. Mỗi lần thuật toán đi qua danh sách, nó được gọi là 'vượt qua'.goes through a list of data a number of times, comparing two items that are side by side to see which is out of order. It will keep going through the list of data until all the data is sorted into order. Each time the algorithm goes through the list it is called a 'pass'.
Làm thế nào bong bóng sắp xếp hoạt động với ví dụ?Sắp xếp bong bóng bắt đầu với hai yếu tố đầu tiên, so sánh chúng để kiểm tra cái nào lớn hơn. . Bây giờ, vì các yếu tố này đã theo thứ tự (8> 5), thuật toán không trao đổi chúng.starts with very first two elements, comparing them to check which one is greater. ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Tại sao bong bóng sắp xếp hoạt động?Nó còn được gọi là một loại chìm (vì các vật phẩm nhỏ nhất "chìm" xuống dưới cùng của mảng).Thay vì tìm kiếm một mảng nói chung, loại bong bóng hoạt động bằng cách so sánh các cặp đối tượng liền kề trong mảng.Nếu các đối tượng không theo thứ tự chính xác, chúng được hoán đổi để lớn nhất trong hai di chuyển lên.comparing adjacent pairs of objects in the array. If the objects are not in the correct ordered, they are swapped so that the largest of the two moves up. |
