Thuật Toán Sắp Xếp Nổi Bọt (bubble Sort) - DNMTechs

Sắp xếp nổi bọt (bubble sort), đôi khi được gọi là sắp xếp đánh chìm (Sinking sort) hoặc sắp xếp bong bóng là một thuật toán sắp xếp đơn giản lặp đi lặp lại qua danh sách cần sắp xếp, 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 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.

Phân loại: Giải thuật sắp xếp Cấu trúc dữ liệu: Ngẫu nhiên Phức tạp thời gian: Trung bình O(n2) Phức tạp dữ liệu: Không tốn thêm vùng nhớ Tối ưu: Không

Sắp xếp từ trên xuống

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, 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….

Ghi chú: 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.

Ví dụ dưới đây sắp xếp từ trên xuống (trái sang phải) một dãy số theo thứ tự tăng dần:

Sắp xếp từ dưới lên

Sắp xếp từ dưới lên 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 (nó giống như hình ảnh của các “bọt” khí nhẹ hơn được nổi lên trên). Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.

Ví dụ viết chương trình C++ nhập vào số phần tử của một mảng và sắp xếp mảng đó theo thứ tự tăng dần. Nhấn vào code để copy:

#include<iostream> using namespace std; void input_func(int A[], int &n) { cout << "nhap so phan tu cua mang n:"; cin >> n; for (int i = 0; i<n; i++) { cout << "phan tu A[" << i << "]" << "="; cin >> A[i]; } } void bubblesort(int A[], int &n) { for (int i = 0; i<n; i++) { for (int j = n - 1; j>i; j--) if (A[j - 1] > A[j]) { int temp = A[j - 1]; A[j - 1] = A[j]; A[j] = temp; } } } void output_func(int A[], int &n) { for (int i = 0; i < n; i++) { cout << A[i] << " "; } } int main() { int A[100], n; input_func(A, n); cout << "mang ban dau la:"; output_func(A, n); bubblesort(A, n); cout << "mang khi sap xep la:"; output_func(A, n); cin.get(); getchar(); return 0; }

Chạy thử với một chuỗi bất kỳ để xem kết quả.

Giảm bớt vòng duyệt

Nếu trong một lần duyệt nào đó với một i cố định khi vòng lặp j kết thúc mà không cần phải đổi chỗ cặp phần tử nào, nghĩa là mọi cặp phần tử kề nhau đã đứng đúng thứ tự thì dãy đã được sắp xếp và không cần tiến hành vòng lặp tiếp theo. Do đó có thể dùng một cờ (flag) để kiểm soát việc này.

Cũng có thể không cần dùng đến biến i, khi đó mỗi lần kiểm tra đều phải duyệt từ đầu đến cuối dãy.

Viết lại ví dụ ở trên bằng C++, với hàm bubblesort(int A[], int &n) được viết lại như sau:

#include<iostream> using namespace std; void input_func(int A[], int &n) { cout << "nhap so phan tu cua mang n:"; cin >> n; for (int i = 0; i<n; i++) { cout << "phan tu A[" << i << "]" << "="; cin >> A[i]; } } void bubblesort(int A[], int &n) { int i = n; bool flag = false; while (i > 0) { flag = false; //khởi tạo lại giá trị cờ flag = false; for (int j = 0; j < i-1;j++){ if (A[j] > A[j + 1]){ int temp = A[j]; A[j] = A[j + 1]; A[j + 1] = temp; flag = true; } } if (flag == false){ //nếu không có lần đổi chỗ nào, danh sách đã sắp xếp xong break; } else //nếu có ít nhất một lần đổi chỗ, danh sách chưa sắp xếp xong { i = i - 1; } } } void output_func(int A[], int &n) { for (int i = 0; i < n; i++) { cout << A[i] << " "; } } int main() { int A[100], n; input_func(A, n); cout << "mang ban dau la:"; output_func(A, n); bubblesort(A, n); cout << "mang khi sap xep la:"; output_func(A, n); cin.get(); getchar(); return 0; }

Chạy thử và xem kết quả.

Thời gian tính

Với mỗi i = 1,2,..,n-1 ta cần i phép so sánh. Do đó số nhiều nhất các lần so sánh và đổi chỗ trong giải thuật là:

Do đó độ phức tạp của giải thuật là khoảng O(n2).