Thuật toán sắp xếp nổi bọt (Bubble sort)

963

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.

I. Giới thiệu

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ụ

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:

  • Dãy ban đầu : 5 4 3 2 1
  • So sánh 5 với 4, đổi chỗ: 4 5 3 2 1
  • So sánh 5 với 3, đổi chỗ: 4 3 5 2 1
  • So sánh 5 với 2, đổi chỗ: 4 3 2 5 1
  • So sánh 5 với 1, đổi chỗ: 4 3 2 1 5. Số 5 về đúng vị trí.
  • So sánh 4 với 3, đổi chỗ: 3 4 2 1 5
  • So sánh 4 với 2, đổi chỗ: 3 2 4 1 5
  • So sánh 4 với 1, đổi chỗ: 3 2 1 4 5. Số 4 về đúng vị trí.
  • So sánh 3 với 2, đổi chỗ: 2 3 1 4 5
  • So sánh 3 với 1, đổi chỗ: 2 1 3 4 5. Số 3 về đúng vị trí.
  • So sánh 2 với 1, đổi chỗ: 1 2 3 4 5. Số 2 về đúng vị trí.
  • So sánh 1 với 2, không đổi, dãy đã được sắp xếp.

Đặ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:

  • Nếu dãy có n phần tử, cứ tối đa n - 1 lần so sánh, ta luôn có ít nhất một phần tử về đúng vị trí của nó.
  • Mỗi lần có một số về đúng vị trí, số lần so sánh để đưa thêm ít nhất một phần tử nữa về đúng vị trí là n - 1 - (số phần tử đã về đúng vi trí).

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.

II. Code

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

Tổng kết

Thuật toán sắp xếp nổi bọt là một thuật toán điển hình dùng để … giảng dạy và làm ví dụ điển hình trong các bài học về giải thuật cơ bản. Tuy nhiên, tính áp dụng vào thực tế của nó lại không cao, bởi việc sắp xếp trải qua khá nhiều bước. Hơn nữa, các ngôn ngữ lập trình ngày nay phần lớn đều hỗ trợ sẵn một hàm để sắp xếp dãy số, bạn không cần phải tự code nữa.

Ví dụ với JavaScript, bạn có thể dễ dàng sắp được được với hàm sort(), như ví dụ sau:

const sorted = [5, 4, 3, 1, 2].sort()
console.log(sorted) // 1 2 3 4 5

Chúc các bạn học tập hiệu quả.

BÀI VIẾT LIÊN QUANXEM THÊM