1. Giới thiệu về thuật toán Bubble Sort
Thuật toán Bubble sort (Sắp xếp nổi bọt)
Bubble Sort (Sắp xếp nổi bọt) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap).
Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang).
Sắp xếp nổi bọt còn có tên gọi khác là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
-
Sắp xếp từ trái sang (Từ trên xuống)
Thuật toán sắp xếp nổi bọt: Từ trái sang
Giả sử dãy cần sắp xếp có n phần tử.
Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu ở bên trái mảng.
Nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau.
Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu.
Nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n - 1 với phần tử thứ n.
Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.
Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n - 2….
Lưu ý
: Nếu trong một lần duyệt, không phải đổi chỗ bất cứ cặp phần tử nào thì danh sách đã được sắp xếp xong.
-
Sắp xếp từ phải sang (Từ bên dưới lên)
Thuật toán sắp xếp nổi bọt: Từ phải sang
Sắp xếp từ phải sang so sánh (và đổi chỗ nếu cần) bắt đầu từ việc so sánh cặp phần tử thứ n - 1 và n.
Tiếp theo là so sánh cặp phần tử thứ n - 2 và n - 1,… cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai.
Sau bước này phần tử nhỏ nhất đã được nổi lên vị trí trên cùng.
Việc này giống như hình ảnh của các “bọt” khí nhẹ hơn được nổi lên trên.
Chính vì thế, đây được gọi là thuật toán sắp xếp nổi bọt.
Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.
Độ phức tạp của giải thuật : O(n2)
