Thuật toán nổi bọt là một thuật toán nổi tiếng trong công nghệ thông tin, code phần mềm. Đây là thuật ngữ mà những người học lập trình nhất định phải biết. Dù rất phổ biến, nổi tiếng nhưng thuật ngữ này lại vô cùng đơn giản. Vậy thuật toán nổi bọt là gì? Và cách giải thích thuật toán này thế nào? Hãy cùng tìm hiểu chi tiết dưới đây nhé.
Khái niệm thuật toán nổi bọt
Thuật toán nổi bọt hay còn gọi là sắp xếp nổi bọt. Đây là một thuật ngữ đơn giản, được tiến hành dựa trên việc so sánh các phần tử đứng ngay cạnh nhau. Đồng thời, người thực hiện cũng sẽ tiến hành so sánh sau khi đã trao đổi thứ tự của các phần tử.
Đây là thuật toán được sử dụng với các dữ liệu hơn, có độ phức tạp cao lên tới n phần tử. Tuy nhiên, các giải thuật nổi bọt lại khá đơn giản. Người thực hiện cần biết cách giải thuật toán này để biết được các giải thuật sắp xếp cơ bản.
Cách thuật toán sắp xếp nổi bọt làm việc
Để hiểu rõ về thuật toán này, chúng ta cần hiểu rõ cách thuật toán làm việc và hoạt động. Sắp xếp nổi bọt được lên ý tưởng từ việc cho số i chạy từ 0, 1…, n – 1. Nếu 2 phần tử đứng liền kề nhau không đúng theo thứ tự, tức là số bên trái lớn hơn số bên phải thì ta sẽ phải tiến hành tráo đổi 2 phần tử. Tiếp tục rà soát cho đến khi phần tử cuối cùng có giá trị lớn nhất.
Để hiểu rõ hơn, hãy cùng tìm hiểu ví dụ thông qua một mảng phần tử không theo thứ tự dưới đây:
Mảng gồm 5 phần tử: 14 | 33 | 27 | 35 | 10. Vậy khi áp dụng thuật toán sắp xếp nổi bọt với 2 phần tử đầu tiên, ta thấy 33 lớn hơn 14, tức là 2 phần tử này đã đứng đúng thứ tự. Tiếp theo so sánh đến 33 và 27, ta thấy 27 đang nhỏ hơn 33, do đó, ta cần tráo đổi thứ tự của 2 phần tử này. Lúc này, mảng mới sẽ có thứ tự là:
14 | 27 | 33 | 35 | 10
Tiếp theo so sánh 2 phần tử 33 và 35, ta thấy 2 phần tử đã đứng thứ tự. Sau đó so sánh đến 2 phần tử cuối là 35 và 10. 10 < 35 nên 2 phần tử này đang sai thứ tự. Ta cần đổi chỗ thành: 14 | 27 | 33 | 10 | 35. Lúc này, 10 lại nhỏ hơn phần tử đứng trướ nó, ta sẽ phải so sánh lần lượt và đổi chỗ cho đến khi 10 lớn hơn phần tử đứng trước nó. Đến cuối cùng, mảng sẽ có thứ tự là:
10 |14 | 27 | 33 | 35 |
Đây là ví dụ cho 5 phần tử. Phần tử càng nhiều thì cách giải thuật càng phức tạp. Vì thế, người ta cần sắp xếp và tạo thành một mã code tự động. Sau đó, mã code này sẽ tự chạy và dãy số sẽ được sắp xếp tự động.
Tổng quát cách giải thuật với thuật nổi bọt
Sau khi nghiên cứu, sắp xếp, người ta đã tổng kết cách giải thuật cho thuật nổi bọt thành 3 trường hợp tổng quát dưới đây:
Sắp xếp từ trên xuống dưới
Chẳng hạn mảng của bạn có n phần tử. Vậy bạn cần so sánh 2 phần tử đầu, nếu vị trí của chúng đang sai, hãy tiến hành đổi chỗ. Tiếp tục so sánh với phần tử thứ 2 và thứ 3 cho đến khi hết mảng dữ liệu.
Trong quá trình so sánh bạn hãy đổi chỗ nếu cần. Đến phần tử n – 1 và n, nếu phần tử n lớn hơn n – 1 tức là bạn đã tìm được phần tử có giá trị lớn nhất. Tiếp theo so sánh và đổi chỗ nếu phần tử bên trái lớn hơn phần tử bên phải, kết thúc ở phần tử n – 2.
Sắp xếp từ dưới lên
Ngược lại với sắp xếp từ trên xuống, khi sắp xếp từ dưới lên, bạn cần so sánh từ phần tử n – 1 và n. Tiếp theo so sánh phần tử n – 2 với n – 1 cho đến phần tử thứ nhất và thứ 2. Lúc này, phần tử nhỏ nhất sẽ ở trên cùng. Để tạo thành mảng đúng, bạn cần tiếp tục so sánh các phần tử từ thứ 2 đến thứ n và đổi chỗ nếu cần.
Giảm bớt vòng duyệt
Đây là cách giải thích khá mới và có phần khó hiểu hơn so với 2 cách trên. Với cách làm này, bạn cần duyệt một số i cố định cho đến khi vòng j kết thúc. Nếu không phải đổi chỗ bất cứ phần tử nào thì bạn có thể kết thúc dãy đó và không cần đến vòng lặp tiếp theo.
Các bạn có thể xem hướng dẫn chi tiết trong video dưới đây
Thuật toán nổi bọt mới nghe thì có phần khó hiểu. Tuy nhiên, nếu tìm hiểu kỹ, bạn sẽ thấy cách giải thuật toán này tương đối đơn giản. Đặc biệt là khi áp dụng vào các mã code của C+
Chỉ với vài bước tạo code đơn giản, bạn đã có thể giải thành công thuật toán nổi bọt này. Nếu yêu thích công nghệ thông tin, chắc chắn bạn sẽ không thể bỏ qua thuật toán này đâu nhé. Hãy áp dụng vào các mã code, bạn sẽ cảm thấy thuật toán này cực kỳ dễ hiểu.
