So sánh
Hoán đổi
Lượt

  • Đang so sánh
  • Vừa hoán đổi
  • Đã đúng chỗ

Tìm hiểu thêm về sắp xếp nổi bọt

Sắp xếp nổi bọt

Sắp xếp nổi bọt duyệt danh sách nhiều lần, so sánh từng cặp kề nhau và hoán đổi khi số bên trái lớn hơn. Sau mỗi lượt, giá trị lớn nhất chưa đúng chỗ đã nổi lên cuối danh sách. Phát quá trình sắp xếp ở tốc độ bất kỳ, hoặc đi từng phép so sánh, và theo dõi bộ đếm phép so sánh, hoán đổi và lượt. Nhấn Phát để xem quá trình sắp xếp, hoặc Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Các ô đếm số phép so sánh, hoán đổi và lượt. Chọn số cột, thứ tự ban đầu, hoặc tự nhập các số. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Chọn số cột và thứ tự ban đầu: ngẫu nhiên, gần như đã sắp xếp, đảo ngược, hoặc ít giá trị khác nhau. Hoặc tự nhập các số.
  2. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình sắp xếp.
  3. Theo dõi các ô đếm số phép so sánh, hoán đổi và lượt, rồi so với trường hợp xấu nhất.

Sắp xếp nổi bọt hoạt động thế nào

Bắt đầu từ bên trái. So sánh hai giá trị đầu tiên; nếu số bên trái lớn hơn, hoán đổi chúng. Dịch sang phải một vị trí và so sánh tiếp, cho đến cuối danh sách. Đó là một lượt, và nó đưa giá trị lớn nhất về vị trí cuối. Lượt tiếp theo dừng sớm hơn một vị trí. Tiếp tục cho đến khi một lượt không có hoán đổi nào, hoặc chỉ còn lại một giá trị.

Đếm khối lượng công việc

Với n giá trị, lượt đầu thực hiện n − 1 phép so sánh, lượt sau n − 2, và cứ thế, nên cả quá trình có tối đa n(n − 1)/2 phép so sánh. Số lần hoán đổi luôn bằng số nghịch thế của danh sách ban đầu: các cặp giá trị nằm sai thứ tự. Danh sách đảo ngược có nhiều nhất, n(n − 1)/2. Danh sách đã sắp xếp không có nghịch thế nào, và với dừng sớm chỉ cần một lượt gồm n − 1 phép so sánh.

Câu hỏi thường gặp

Vì sao gọi là sắp xếp nổi bọt?

Vì các giá trị lớn nổi dần về cuối danh sách như bọt khí trong nước. Ở mỗi lượt, giá trị lớn nhất chưa đúng chỗ dịch dần sang phải cho đến khi tới vị trí cuối cùng của nó.

Sắp xếp nổi bọt thực hiện bao nhiêu phép so sánh và hoán đổi?

Tối đa n(n − 1)/2 phép so sánh với n giá trị: 45 với 10 giá trị, 780 với 40. Số lần hoán đổi luôn bằng số nghịch thế của danh sách ban đầu, từ 0 với danh sách đã sắp xếp đến n(n − 1)/2 với danh sách đảo ngược.

Dừng sớm có tác dụng gì?

Nếu cả một lượt không có hoán đổi nào, mọi cặp kề nhau đều đúng thứ tự, nên danh sách đã được sắp xếp và có thể dừng. Khi bật dừng sớm, danh sách đã sắp xếp chỉ cần một lượt. Khi tắt, sắp xếp nổi bọt luôn chạy đủ n − 1 lượt.

Sắp xếp nổi bọt có được dùng trong thực tế không?

Hiếm khi. Nó đơn giản và ổn định, nhưng trung bình tốn thời gian tỉ lệ với n². Sắp xếp chèn làm cùng việc với ít bước hơn trên danh sách nhỏ hoặc gần như đã sắp xếp, còn sắp xếp trộn hay sắp xếp nhanh nhanh hơn nhiều trên danh sách lớn.

Các số của tôi có bị gửi đi đâu không?

Không. Quá trình sắp xếp chạy trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa