Làm thế nào về các yếu tố của một số? . Trong phạm vi từ 1 cho đến số ta đang tìm thừa số, nếu bất kỳ số nào có thể chia hết cho số chính mà không có số dư thì đó là thừa số của số ta
Sắp xếp bong bóng là thuật toán sắp xếp để sắp xếp danh sách theo thứ tự tăng dần [hoặc giảm dần]. Đây là thuật toán sắp xếp đơn giản nhất nhưng nó không hiệu quả lắm. Nó có thể được sử dụng trên kích thước đầu vào nhỏ nhưng không hiệu quả về thời gian đối với danh sách hoặc mảng có độ dài lớn hơn. Độ phức tạp thời gian của nó là O[n^2]. Tuy nhiên, đây là thuật toán sắp xếp tại chỗ, có nghĩa là nó không sử dụng thêm bất kỳ khoảng trống nào. Do đó, nó hiệu quả về độ phức tạp không gian. Tuy nhiên, nó không được sử dụng nhiều vì có những thuật toán sắp xếp tốt hơn sắp xếp bong bóng
Sắp xếp bong bóng hoạt động như thế nào?
Trong sắp xếp bong bóng, hai vòng for được sử dụng. Vòng lặp for bên ngoài lặp qua danh sách. Vòng lặp for bên trong cũng lặp qua danh sách cho tất cả các lần lặp của vòng lặp bên ngoài
Thao tác chính trong Bubble sort là so sánh hai phần tử liên tiếp. Nếu phần tử đầu tiên lớn hơn phần tử tiếp theo, thì hoán đổi cả hai, để phần tử nhỏ hơn đi trước và phần tử lớn hơn quay lại. Trong một lần lặp của vòng lặp bên ngoài, phần tử lớn nhất của danh sách nằm ở chỉ mục cuối cùng. Trong lần lặp thứ hai của vòng lặp bên ngoài, phần tử lớn thứ hai của danh sách nằm ở chỉ mục cuối cùng thứ hai, v.v. Do đó, chúng tôi nhận được danh sách được sắp xếp ở cuối tất cả các lần lặp
Chúng ta có thể hiểu rõ hơn với sự giúp đỡ của một ví dụ
Ví dụ
Chúng tôi được yêu cầu sắp xếp danh sách sau
Vòng ngoài = 1
5>2, do đó hoán đổi cả hai
5>1, do đó hoán đổi cả hai
5>3, do đó hoán đổi cả hai
5>4, do đó hoán đổi cả hai
[Phần tử 5 lớn nhất đã đạt đến chỉ mục cuối cùng sau lần lặp lại bên ngoài đầu tiên]
Vòng ngoài = 2
2>1, do đó đổi chỗ
Không cần trao đổi
Không cần trao đổi
Như chúng ta có thể thấy danh sách được sắp xếp trong lần lặp thứ 2 bên ngoài. Nhưng vòng lặp bên ngoài sẽ lặp lại thêm 3 lần nữa mà không cần thao tác hoán đổi nào nữa. Do đó, chỉ có 2 lần lặp lại được hiển thị trong ví dụ. Đôi khi, danh sách có thể được sắp xếp trong lần lặp đầu tiên. Đôi khi, danh sách có thể được sắp xếp trong lần lặp lại cuối cùng. Do đó, vòng lặp bên ngoài sẽ luôn lặp lại n lần
Đố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
Khô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