Cách Giải Sắp Xếp Nổi Bọt (Bubble Sort), Dể Hiểu
Sắp Xếp Nổi Bọt là một thuật toán sắp xếp đơn giản, thường được sử dụng để giới thiệu các khái niệm cơ bản trong lập trình và thuật toán. Thuật toán này hoạt động dựa trên việc so sánh và hoán đổi vị trí của các phần tử trong một danh sách cho đến khi chúng được sắp xếp theo thứ tự mong muốn.
Định Nghĩa
Sắp Xếp Nổi Bọt (Bubble Sort) là thuật toán sắp xếp các phần tử trong mảng từ thấp đến cao. Điểm đặc biệt ở đây là thuật toán này đi qua mảng và so sánh từng cặp phần tử kế cận.
Mỗi lần phát hiện phần tử trước lớn hơn phần tử sau, nó sẽ hoán đổi hai phần tử đó để đảm bảo phần tử lớn hơn dần “nổi” lên cuối mảng.
Quá trình này được lặp lại cho đến khi không còn cặp phần tử nào cần hoán đổi, nghĩa là mảng đã sắp xếp xong.
Sắp Xếp Nổi Bọt rất dễ hiểu, nhưng không phải lúc nào cũng là lựa chọn nhanh nhất cho mảng lớn.
Bản Chất
Sắp Xếp Nổi Bọt hoạt động trên nguyên tắc lặp lại và hoán đổi. Mỗi lần duyệt qua mảng, nó cố gắng đưa phần tử lớn nhất trong mảng chưa sắp xếp về cuối.
Cứ mỗi lần duyệt, số phần tử cần xét giảm đi một vì phần tử lớn nhất đã “nổi” lên cuối.
Điều này tạo ra một quá trình sắp xếp dần dần, từng bước một, mang lại sự ổn định cho thuật toán.
Với mảng đã sắp xếp gần đúng, Sắp Xếp Nổi Bọt có thể hoàn thành nhanh hơn vì ít hoán đổi hơn.
Để dể hình dung hơn, bạn có thể xem diễn họa của các thuật toán sắp xếp 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
Sắp Xếp Nổi Bọt có độ phức tạp thời gian là O(n²) trong trường hợp xấu nhất. Khi bạn duyệt qua từng phần tử và thực hiện hoán đổi, thuật toán phải thực hiện số lần so sánh và hoán đổi rất lớn.
Điều này có nghĩa rằng với mảng lớn, Sắp Xếp Nổi Bọt sẽ chạy chậm hơn nhiều so với các thuật toán khác như Sắp Xếp Nhanh hoặc Sắp Xếp Trộn.
Trong trường hợp tốt nhất, khi mảng đã gần sắp xếp hoàn toàn, độ phức tạp thời gian có thể giảm xuống O(n).
Dẫu vậy, độ phức tạp trung bình vẫn khiến Sắp Xếp Nổi Bọt không phải lựa chọn tối ưu cho các ứng dụng lớn.
Toàn Cảnh
Sắp Xếp Nổi Bọt chỉ là một trong nhiều thuật toán sắp xếp, và mỗi thuật toán có ưu, nhược điểm riêng.
Sắp Xếp Nổi Bọt phù hợp với các tình huống học thuật hoặc các bài toán nhỏ yêu cầu thuật toán dễ hiểu, dễ triển khai.
Trong hệ thống lớn, các thuật toán phức tạp hơn như Sắp Xếp Nhanh hay Sắp Xếp Trộn thường được ưu tiên nhờ tính hiệu quả về thời gian.
Hiểu rõ sự khác biệt giữa các thuật toán sắp xếp giúp bạn chọn được công cụ phù hợp nhất cho từng bài toán cụ thể.
Ứng Dụng
Một ví dụ điển hình của Sắp Xếp Nổi Bọt là trong giáo dục lập trình, nơi nó được dùng để minh họa khái niệm sắp xếp.
Thuật toán này cũng hữu dụng khi bạn cần kiểm tra một mảng có được sắp xếp hay chưa mà không quá quan tâm đến hiệu suất.
Với mảng nhỏ hoặc khi ưu tiên tính dễ hiểu hơn tốc độ, Sắp Xếp Nổi Bọt trở thành lựa chọn đơn giản và hiệu quả.
Ngoài ra, trong trường hợp dữ liệu chỉ cần thay đổi đôi chút, Sắp Xếp Nổi Bọt có thể hoàn thành việc sắp xếp với ít bước hơn.
Hiểu Lầm
Một hiểu lầm phổ biến về Sắp Xếp Nổi Bọt là cho rằng nó hiệu quả với mọi loại dữ liệu.
Thực tế, Sắp Xếp Nổi Bọt không phải là lựa chọn tốt nhất khi hiệu suất và thời gian chạy là yếu tố quan trọng.
Nhiều người cũng nhầm lẫn rằng thuật toán này sẽ dừng ngay khi không còn phần tử cần hoán đổi, nhưng cần đảm bảo thuật toán đã kiểm tra kỹ lưỡng toàn bộ mảng.
Cuối cùng, Sắp Xếp Nổi Bọt dễ hiểu nhưng không phù hợp với các bài toán đòi hỏi hiệu suất cao, và đó là giới hạn cần lưu ý.
Tóm Tắt
Hiểu rõ về Sắp Xếp Nổi Bọt giúp bạn nắm bắt các bước cơ bản trong lập trình thuật toán sắp xếp.
Thuật toán này dễ tiếp cận, nhưng cần hiểu rằng nó có giới hạn về hiệu suất.
Với mảng nhỏ và nhu cầu dễ hiểu, Sắp Xếp Nổi Bọt là lựa chọn hợp lý, nhưng không nên áp dụng cho các ứng dụng lớn.
Tóm lại, Sắp Xếp Nổi Bọt là công cụ học thuật hữu ích giúp bạn xây dựng nền tảng về thuật toán sắp xếp trong lập trình.