Trong bài viết này, thuật toán sắp xếp nổi bọt là tăng dần, bạn sẽ biết cách sắp xếp giảm dần nếu hiểu rõ cách chạy của thuật toán này.
Thuật toán sắp xếp nổi bọt là một trong những thuật toán “vỡ lòng” của gần như tất cả các lập trình viên. Cách chạy của thuật toán này khá tương tự như việc bong bóng nổi bọt – tức là bong bóng nào càng nhẹ, thì sẽ càng nổi lên trên và ngược lại.
Thuật toán sắp xếp nội bọt thường để sắp xếp một dãy số theo chiều tăng dần, ý tưởng thì rất đơn giản như sau: Trong dãy số, ta tiến hành xét từng cặp số một, nếu số trước lớn hơn số sau, thì ta đổi chỗ cặp số đó (theo chiều từ trái qua phải, thì số bên trái được coi là đứng trước số bên phải), so sánh đến bao giờ không phát hiện sự đổi chỗ nữa, thì dãy đã được sắp xếp thành công.
Ví dụ 1
Sắp xếp dãy 5 phần tử 5 4 3 2 1, thì các bước chạy sẽ diễn ra như sau:
Ví dụ 2
Sắp xếp dãy gồm 5 phần tử 6 5 3 1 8 7 2 4 theo chiều tăng dần, thì cách chạy được diễn ra như trong ảnh gif dưới đây:
Đặc điểm của thuật toán sắp xếp nổi bọt
Từ ví dụ trên, bạn có thể thấy thuật toán sắp xếp nổi bọt có một số đặc điểm sau:
Hãy đọc kỹ và đảm bảo bạn hiểu ví dụ trên, nếu không thì … hãy đọc lại lần nữa, vì hiểu thuật toán chạy như thế nào là cực kỳ quan trọng khi bạn tìm hiểu bất kỳ giải thuật nào.
Sau cùng, nếu bạn đã hiểu cách thuật toán này hoạt động, thì đây là một đoạn code minh họa cho việc sắp xếp dãy số tăng dần sử dụng thuật toán sắp xếp nổi bọt.
// Dãy cần sắp xếp
const input = "5 4 3 2 1";
const numbers = input.split(' ');
// Tối đa chỉ so sánh n - 1 cặp số, vì thế j chỉ chạy tới n - 1
// j là đại diện cho số lượng phần tử đã về đúng vị trí
// mỗi lần chạy hết một lượt trong vòng lặp này
// luôn tối thiểu có 1 số về đúng vị trí
for (let j = 0; j < numbers.length - 1; j++) {
// Biến đánh dấu có xảy ra sự kiện đổi chỗ không?
let sw = false;
// Tiến hành so sánh các cặp số
// So sánh tối đa n - j - 1 cặp số
for (let i = 0; i < numbers.length - j - 1; i++) {
// Nếu phần tử trước lớn hơn phần tử sau
if (numbers[i] > numbers[i + 1]) {
// Đổi chỗ cặp số
const temp = numbers[i];
numbers[i] = numbers[i + 1];
numbers[i + 1] = temp;
// đánh dấu là có sự kiện đổi chỗ
sw = true;
}
}
// Sau khi so sánh một lượt các cặp, mà không xảy ra sự kiện đổi chỗ
// tức là dãy đã được sắp xếp, thì ta không cần chạy vòng lặp nữa
// break luôn để tiếp kiện thời gian chạy
if (!sw) {
break;
}
}
console.log(numbers.join(' ')); // 1 2 3 4 5
