Cách mà Bubble Sort hoạt động
Đầu tiên chúng ta cho 1 mảng đơn giản như: mang = [9,1,4,7]
Phần tử lớn nhất được đặt vào đúng vị trí của nó, tức là ở cuối mảng.
Đặt phần tử lớn thứ hai vào đúng vị trí
Đặt hai phần tử còn lại vào đúng vị trí của chúng.
- Tổng số không. số lần vượt qua: n-1
- Tổng số không. so sánh: n*(n-1)/2
Code thuật toán Bubble Sort
function bubbleSort(arr) {
var n = arr.length;
for (var i = 0; i < n; i++) {
for (var j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Hoán đổi phần tử nếu chúng không được sắp xếp đúng thứ tự
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Ví dụ về cách sử dụng
var arr = [64, 34, 25, 12, 22, 11, 90];
bubbleSort(arr);
console.log("Danh sách sau khi sắp xếp:", arr);Độ phức tạp
Độ phức tạp thời gian của Bubble Sort là O(n^2), trong đó “n” là số lượng phần tử trong danh sách. Điều này có nghĩa là thời gian thực thi của thuật toán tăng theo bình phương của số lượng phần tử trong danh sách. Vì vậy, Bubble Sort thường không được ưa chuộng trong các trường hợp có số lượng phần tử lớn.
Ưu điểm
- Sắp xếp bong bóng rất dễ hiểu và dễ thực hiện.
- Nó không yêu cầu bất kỳ không gian bộ nhớ bổ sung.
- Đây là một thuật toán sắp xếp ổn định, nghĩa là các phần tử có cùng giá trị khóa sẽ duy trì thứ tự tương đối của chúng trong kết quả được sắp xếp.
Nhược điểm
- Sắp xếp nổi bọt có độ phức tạp về thời gian là O(N 2 ) khiến cho việc xử lý các tập dữ liệu lớn trở nên rất chậm.
- Sắp xếp nổi bọt là một thuật toán sắp xếp dựa trên so sánh, có nghĩa là nó yêu cầu toán tử so sánh để xác định thứ tự tương đối của các phần tử trong tập dữ liệu đầu vào. Nó có thể hạn chế hiệu quả của thuật toán trong một số trường hợp nhất định.
Kết luận
Mặc dù Bubble Sort không phải là thuật toán sắp xếp hiệu quả nhất, nhưng việc hiểu và nắm vững cách hoạt động của nó có thể giúp ta hiểu sâu hơn về các thuật toán sắp xếp khác và làm nền tảng cho việc học các thuật toán phức tạp hơn trong lĩnh vực khoa học máy tính.
Tài liệu tham khảo
Các bạn có thể tham khảo các ví dụ khác về Bubbke Sort này ví dụ như: Sắp xếp chuỗi bằng Bubble Sort, Sắp xếp bong bóng đệ quy ….