Bubble Sort là gì?
Bubble Sort là một thuật toán sắp xếp đơn giản. Thuật toán này hoạt động bằng cách lặp lại qua mảng và so sánh hai phần tử liên tiếp, sau đó trao đổi chúng nếu chúng không ở thứ tự chính xác. Quy trình này được lặp lại cho đến khi không cần thiết phải trao đổi nữa, tức là mảng đã được sắp xếp.
Cụ thể, quy trình của Bubble Sort bao gồm các bước sau:
- 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ử thứ hai, thì trao đổi chúng.
- Lặp lại các bước 1 và 2 cho đến khi không cần thiết phải trao đổi nữa.
Bubble Sort có những ưu điểm và nhược điểm riêng:
Ưu điểm:
- Đơn giản: Bubble Sort rất đơn giản và dễ hiểu.
- Stable: Bubble Sort là một thuật toán sắp xếp ổn định, nghĩa là nó duy trì thứ tự tương đối của các phần tử bằng nhau
Nhược điểm:
- Inefficient: Bubble Sort không phù hợp với các tập dữ liệu lớn vì độ phức tạp thời gian trung bình và tồi tệ là O(n^2), nơi n là số lượng phần tử trong mảng
- Not Adaptive: Bubble Sort không phù hợp với các tập dữ liệu thay đổi thường xuyên
Bubble Sort hoạt động như thế nào?
Giả sử chúng ta có một mảng sau: 5, 3, 8, 4, 2
Bước 1: So sánh hai phần tử đầu tiên, 5 và 3. Vì 5 lớn hơn 3, nên chúng ta trao đổi chúng: 3, 5, 8, 4, 2
Bước 2: So sánh hai phần tử tiếp theo, 5 và 8. Vì 5 nhỏ hơn 8, nên chúng ta không cần phải trao đổi: 3, 5, 8, 4, 2
Bước 3: So sánh hai phần tử tiếp theo, 8 và 4. Vì 8 lớn hơn 4, nên chúng ta trao đổi chúng: 3, 5, 4, 8, 2
Bước 4: So sánh hai phần tử tiếp theo, 8 và 2. Vì 8 lớn hơn 2, nên chúng ta trao đổi chúng: 3, 5, 4, 2, 8
Bước 5: Đây là lần lặp cuối cùng, nên chúng ta không cần phải so sánh và trao đổi nữa: 3, 5, 4, 2, 8
Vậy, mảng ban đầu 5, 3, 8, 4, 2 đã được sắp xếp thành 3, 5, 4, 2, 8.
Cách cài đặt Bubble Sort
function bubbleSort(arr) { let len = arr.length; let swapped; do { swapped = false; for (let i = 0; i < len; i++) { if (arr[i] > arr[i + 1]) { let temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; swapped = true; } } } while (swapped); return arr;
}
Trong đoạn mã trên, chúng ta sử dụng một vòng lặp do-while để lặp lại quy trình so sánh và trao đổi cho đến khi không cần thiết phải trao đổi nữa. Biến swapped được sử dụng để theo dõi xem có phần tử nào được trao đổi trong lần lặp hiện tại hay không
Ứng dụng của Bubble Sort
Thuật toán Bubble Sort có một số ứng dụng:
- Mục đích giáo dục: Bubble Sort được sử dụng rộng rãi trong giáo dục khoa học máy tính như một công cụ giảng dạy để giúp sinh viên hiểu được khái niệm về thuật toán sắp xếp.
- Kiểm tra và gỡ lỗi cho các thuật toán sắp xếp khác: Bubble Sort có thể được sử dụng để kiểm tra và gỡ lỗi cho các thuật toán sắp xếp khác bằng cách phục vụ như một điểm tham chiếu đơn giản và trực tiếp.
- Trong đồ họa máy tính: Bubble Sort phổ biến vì khả năng của nó phát hiện một lỗi nhỏ (như việc trao đổi chỉ hai phần tử) trong các mảng gần như đã được sắp xếp và sửa chúng với chỉ độ phức tạp tuyến tính (2n)
- Trong thuật toán điền đa giác: Bubble Sort được sử dụng trong thuật toán điền đa giác, nơi các đường ranh giới được sắp xếp theo tọa độ x của chúng ở một dòng quét cụ thể (một đường song song với trục x), và với việc tăng dần y, thứ tự của chúng chỉ thay đổi (chỉ hai phần tử được trao đổi) tại các giao điểm của hai đường.
Nguồn tham khảo: