Cách Giải Sắp Xếp Nổi Bọt (Bubble Sort), Dể Hiểu

Thuật toán Sắp Xếp Nổi Bọt có nguồn gốc từ một bài báo năm 1956 của Edward H. Friend, trong đó thuật toán này được mô tả như một ví dụ về “sắp xếp bằng cách trao đổi”. Mặc dù thuật toán này không hiệu quả, nhưng nó đã trở thành một công cụ giáo dục phổ biến để giúp sinh viên hiểu về các phương pháp sắp xếp.

Định Nghĩa

Thuật toán Sắp Xếp Nổi Bọt là một trong những thuật toán sắp xếp cơ bản nhất. Nó không phức tạp nhưng lại hiệu quả để dạy người mới cách thức sắp xếp dữ liệu. Ý tưởng chính của nó là so sánh từng cặp phần tử liền kề trong danh sách, và nếu phần tử phía trước lớn hơn phần tử phía sau, thì chúng sẽ hoán đổi vị trí.

Kết quả của việc hoán đổi là phần tử lớn nhất sẽ dần “nổi” lên cuối danh sách qua mỗi lần duyệt. Quá trình này lặp lại cho đến khi toàn bộ danh sách được sắp xếp. Đó là lý do vì sao thuật toán này được gọi là “nổi bọt” – các phần tử lớn dần nổi lên từ dưới lên trên.

Sắp Xếp Nổi Bọt có thể tốn thời gian khi làm việc với danh sách dài, nhưng là một cách tiếp cận đơn giản để hiểu về nguyên tắc so sánh và hoán đổi trong lập trình. Hơn nữa, thuật toán này có thể dễ dàng thực hiện trong nhiều ngôn ngữ lập trình mà không yêu cầu bộ nhớ bổ sung.

Điểm mạnh của Sắp Xếp Nổi Bọt là sự đơn giản – dễ viết, dễ đọc, dễ học. Tuy vậy, đối với những bài toán phức tạp, ta cần đến các thuật toán sắp xếp tối ưu hơn.

Cách Giải

Thuật toán Sắp Xếp Nổi Bọt hoạt động trên nguyên tắc so sánh và hoán đổi. Sau đây là cách giải chi tiết:

Duyệt qua danh sách, từng giá trị một.
Với mỗi giá trị, so sánh nó với giá trị kế tiếp.
Nếu giá trị hiện tại lớn hơn giá trị kế tiếp, hoán đổi hai giá trị đó để giá trị lớn hơn dần dần dịch chuyển về cuối danh sách.
Lặp lại bước trên với toàn bộ danh sách, số lần duyệt bằng với số lượng giá trị trong danh sách.

Bạn thấy đó, mỗi lần duyệt, giá trị lớn nhất sẽ “nổi” lên cuối, làm cho danh sách dần dần được sắp xếp. Cứ như vậy, đến khi không còn giá trị nào cần hoán đổi, thuật toán kết thúc và bạn có một danh sách đã sắp xếp.

Để dể hình dung hơn, bạn có thể xem diễn họa của các thuật toán tại đây: https://visualgo.net/en/sorting

Triển Khai

Để triển khai thuật toán Sắp Xếp Nổi Bọt trong một ngôn ngữ lập trình, chúng ta cần:

Một mảng chứa các giá trị cần sắp xếp.
Một vòng lặp bên trong (for j) để duyệt qua mảng và hoán đổi giá trị nếu giá trị đầu tiên lớn hơn giá trị tiếp theo. Vòng lặp này cần lặp qua ít hơn một giá trị sau mỗi lần chạy.
Một vòng lặp bên ngoài (for i) để kiểm soát số lần chạy của vòng lặp bên trong. Với một mảng có n giá trị, vòng lặp bên ngoài này cần chạy n-1 lần.

Mã nguồn TypeScript sau đây sẽ cho ra kết quả như mong đợi:

import { expect } from 'jsr:@std/expect';

function bubbleSort(nums: number[]): number[] {
  // Nếu mảng có độ dài 1 hoặc rỗng, không cần sắp xếp, trả về mảng như ban đầu.
  if (nums.length <= 1) return nums;

  // Vòng lặp ngoài để duyệt qua từng phần tử trong mảng.
  for (let i = 0; i < nums.length; i++) {
    // Biến swapped để kiểm tra xem có phần tử nào được hoán đổi trong vòng lặp này không.
    let swapped = false;

    // Vòng lặp trong để duyệt qua các phần tử còn lại trong mảng, trừ phần tử cuối cùng đã được sắp xếp.
    for (let j = 0; j < nums.length - i - 1; j++) {
      // So sánh hai phần tử liền kề, nếu phần tử hiện tại lớn hơn phần tử kế tiếp thì hoán đổi vị trí của chúng.
      if (nums[j] > nums[j + 1]) {
        // Thực hiện hoán đổi vị trí của hai phần tử.
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];

        // Đánh dấu là có hoán đổi.
        swapped = true;
      }
    }

    // Nếu không có phần tử nào được hoán đổi trong vòng lặp, mảng đã được sắp xếp xong, thoát khỏi vòng lặp ngoài.
    if (!swapped) break;
  }

  // Trả về mảng đã được sắp xếp.
  return nums;
}

Deno.test('test', () => {
  const input = [3, 15, 7, 1, 12, 19, 5, 8, 2, 10];
  const output = input.toSorted((a, b) => a - b);

  expect(bubbleSort(input)).toStrictEqual(output);
});

Biến swapped dùng để kiểm tra xem trong vòng lặp hiện tại có xảy ra hoán đổi nào không; nếu không có (tức là swapped vẫn là false), mảng đã được sắp xếp và thuật toán có thể dừng sớm để tiết kiệm thời gian.

Big O

Trong trường hợp tốt nhất, độ phức tạp thời gian của Sắp Xếp Nổi Bọt là O(n), khi danh sách đã sắp xếp từ trước. Khi đó, thuật toán chỉ duyệt qua một lần mà không cần hoán đổi giá trị nào. Đây là trường hợp tối ưu của Sắp Xếp Nổi Bọt.

Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán là O(n²), khi danh sách hoàn toàn ngược với thứ tự sắp xếp mong muốn. Thuật toán phải thực hiện rất nhiều lần so sánh và hoán đổi để đưa các phần tử về đúng vị trí.

Trong trường hợp trung bình, độ phức tạp thời gian của Sắp Xếp Nổi Bọt cũng là O(n²). Điều này là do số lần so sánh và hoán đổi vẫn cao, vì thuật toán phải kiểm tra từng cặp phần tử một cách tuần tự.

Độ phức tạp không gian của Sắp Xếp Nổi Bọt là O(1), vì thuật toán chỉ sử dụng một bộ nhớ phụ trợ cho các biến tạm thời khi hoán đổi giá trị, không cần thêm bộ nhớ cho danh sách mới.

Toàn Cảnh

Sắp Xếp Nổi Bọt là một phần nhỏ trong số nhiều thuật toán sắp xếp hiện có. Trong bức tranh tổng thể của các thuật toán sắp xếp, nó được coi là thuật toán cơ bản, thường dùng để minh họa các khái niệm về sắp xếp và tối ưu hóa.

Mặc dù không hiệu quả cho các danh sách lớn, nhưng trong các ứng dụng nhỏ hoặc đơn giản, Sắp Xếp Nổi Bọt vẫn là một giải pháp hợp lý. Đặc biệt, nó dễ hiểu và là một bước đệm tốt để người học tiếp cận các thuật toán phức tạp hơn.

Nhìn rộng hơn, Sắp Xếp Nổi Bọt thuộc loại thuật toán dựa trên so sánh. Nó không phải là lựa chọn duy nhất khi nói về sắp xếp, nhưng lại là bước đầu tiên để hiểu các thuật toán như Sắp Xếp Nhanh hay Sắp Xếp Trộn.

Việc nắm vững Sắp Xếp Nổi Bọt giúp bạn hiểu rõ về cách so sánh và hoán đổi, một nền tảng vững chắc để tiếp cận các giải pháp tối ưu hóa sắp xếp khác.

Ứng Dụng

Sắp Xếp Nổi Bọt thường không được dùng trong thực tế cho các danh sách lớn vì độ phức tạp cao, nhưng trong các trường hợp nhỏ, nó vẫn có giá trị. Chẳng hạn, trong lập trình nhúng với bộ nhớ hạn chế, Sắp Xếp Nổi Bọt có thể được áp dụng.

Ngoài ra, Sắp Xếp Nổi Bọt hữu ích trong việc sắp xếp các danh sách dữ liệu nhỏ trong các ứng dụng tạm thời, nơi hiệu quả không phải là yếu tố hàng đầu.

Nó còn được dùng trong các ứng dụng giáo dục, dạy lập trình và thuật toán cơ bản, giúp người học hiểu về khái niệm sắp xếp dữ liệu. Trong môi trường học thuật, đây vẫn là công cụ tốt để khơi gợi tư duy.

Cuối cùng, khi cần sắp xếp những dữ liệu có kích thước nhỏ hoặc khi muốn kiểm tra tính chính xác của thuật toán, Sắp Xếp Nổi Bọt có thể được sử dụng như một phương pháp kiểm tra nhanh.

Hiểu Lầm

Một hiểu lầm phổ biến là nghĩ rằng Sắp Xếp Nổi Bọt có thể hiệu quả với bất kỳ kích thước dữ liệu nào, nhưng thực tế là nó rất chậm với danh sách lớn. Độ phức tạp O(n²) khiến nó không thích hợp cho các trường hợp dữ liệu lớn.

Ngoài ra, nhiều người mới học thường nhầm lẫn giữa Sắp Xếp Nổi Bọt và các thuật toán sắp xếp dựa trên so sánh khác. Sự khác biệt nằm ở nguyên lý so sánh từng cặp và hoán đổi “nổi bọt”.

Có người cho rằng Sắp Xếp Nổi Bọt là thuật toán tối ưu nhất vì dễ viết và dễ hiểu, nhưng điều này không đúng khi so với các thuật toán hiện đại như Sắp Xếp Nhanh hay Sắp Xếp Trộn.

Cuối cùng, một hiểu lầm khác là nghĩ rằng Sắp Xếp Nổi Bọt không có ứng dụng thực tế. Mặc dù ít hiệu quả, nhưng nó vẫn có vai trò riêng trong giáo dục và một số ứng dụng nhỏ.

Tóm Tắt

Sắp Xếp Nổi Bọt là thuật toán sắp xếp đơn giản, dễ hiểu, hoạt động dựa trên nguyên tắc so sánh và hoán đổi. Nó là bài học đầu tiên giúp bạn tiếp cận với khái niệm sắp xếp dữ liệu.

Tuy nhiên, độ phức tạp cao khiến nó không phù hợp cho dữ liệu lớn, nhưng trong những trường hợp nhỏ hoặc khi dạy lập trình, đây vẫn là lựa chọn lý tưởng.

Sắp Xếp Nổi Bọt nhấn mạnh nguyên tắc “từng bước một,” giúp bạn làm quen với cách suy nghĩ về các vấn đề phức tạp trong lập trình.

Hiểu Sắp Xếp Nổi Bọt giúp bạn dễ dàng tiến đến các thuật toán sắp xếp phức tạp hơn, mở rộng tầm nhìn trong việc tối ưu hóa dữ liệu.

Nguồn: Viễn Đinh - Cách Giải Sắp Xếp Nổi Bọt