NỘI DUNG
Thuật toán sắp xếp nổi bọt (Bubble Sort) là một thuật toán đơn giản trong việc sắp xếp các phần tử của một mảng. Thuật toán hoạt động bằng cách so sánh các phần tử liên tiếp của mảng, nếu phần tử sau nhỏ hơn phần tử trước thì hoán đổi chúng cho nhau. Thuật toán này lặp lại quá trình này cho đến khi không còn phần tử nào cần được hoán đổi nữa.
Lịch sử thuật toán sắp xếp nổi bọt
Thuật toán sắp xếp nổi bọt được đề xuất bởi John von Neumann vào những năm 1940. Tuy nhiên, không ai biết chắc chắn người đầu tiên tìm ra thuật toán này là ai.
Ban đầu, thuật toán sắp xếp nổi bọt được sử dụng để sắp xếp các thẻ bài trong trò chơi bài. Trong những năm 1950, thuật toán này được sử dụng trong các máy tính đầu tiên để sắp xếp các tập tin và cơ sở dữ liệu.
Tuy nhiên, với sự phát triển của các thuật toán sắp xếp khác, như thuật toán sắp xếp chọn (Selection Sort) và thuật toán sắp xếp nhanh (Quick Sort), thuật toán sắp xếp nổi bọt đã không còn được sử dụng nhiều trong thực tế vì tốc độ chậm hơn so với các thuật toán khác. Tuy nhiên, thuật toán sắp xếp nổi bọt vẫn được sử dụng để giới thiệu các khái niệm cơ bản trong giáo dục về khoa học máy tính.
Các bước thực hiện thuật toán sắp xếp nổi bọt
Các bước thực hiện thuật toán sắp xếp nổi bọt như sau:
Bước 1. Bắt đầu từ đầu mảng, so sánh phần tử đầu tiên với phần tử thứ hai. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, hoán đổi chúng cho nhau.
Bước 2. Tiếp tục so sánh phần tử thứ hai với phần tử thứ ba, nếu phần tử thứ hai lớn hơn phần tử thứ ba, hoán đổi chúng cho nhau.
Bước 3. Tiếp tục thực hiện như vậy cho đến khi so sánh được phần tử cuối cùng của mảng.
Bước 4. Khi kết thúc vòng lặp đầu tiên, phần tử lớn nhất của mảng sẽ được đưa về vị trí cuối cùng của mảng.
Bước 5. Tiếp tục lặp lại từ bước 1 đến bước 4 cho đến khi tất cả các phần tử được sắp xếp đúng thứ tự.
Ví dụ thuật toán sắp xếp nổi bọt
Giả sử chúng ta có một mảng số nguyên không âm như sau: [5, 3, 8, 4, 2]
Sau khi áp dụng thuật toán sắp xếp nổi bọt, ta sẽ có kết quả như sau:
// Lần lượt làm việc với các phần tử của mảng
// Lần lượt đưa phần tử lớn nhất về cuối mảng
// Đưa từng phần tử lớn nhất về cuối mảng, đến khi mảng được sắp xếp hoàn toàn
// Lặp qua toàn bộ mảng để sắp xếp
// So sánh và hoán đổi các phần tử để đưa phần tử lớn nhất về cuối mảng
// Đưa từng phần tử lớn nhất về cuối mảng, đến khi mảng được sắp xếp hoàn toàn
// Kết quả sắp xếp: [2, 3, 4, 5, 8]
// Bước 1: [5, 3, 8, 4, 2] -> [3, 5, 8, 4, 2]// Bước 2: [3, 5, 8, 4, 2] -> [3, 5, 4, 8, 2]// Bước 3: [3, 5, 4, 8, 2] -> [3, 5, 4, 2, 8]
// Phần tử lớn nhất của mảng hiện tại là 8, đã được đưa về cuối mảng
// Bước 4: [3, 5, 4, 2, 8] -> [3, 4, 5, 2, 8]// Bước 5: [3, 4, 5, 2, 8] -> [3, 4, 2, 5, 8]
// Phần tử lớn nhất của mảng hiện tại là 5, đã được đưa về cuối mảng
// Bước 6: [3, 4, 2, 5, 8] -> [3, 2, 4, 5, 8]
// Phần tử lớn nhất của mảng hiện tại là 4, đã được đưa về cuối mảng
// Bước 7: [3, 2, 4, 5, 8] -> [2, 3, 4, 5, 8]
// Mảng đã được sắp xếp hoàn toàn
Như vậy, sau khi áp dụng thuật toán sắp xếp nổi bọt vào mảng arr, chúng ta đã có một mảng mới được sắp xếp theo thứ tự tăng dần như sau: [2, 3, 4, 5, 8].
Cài đặt thuật toán sắp xếp nổi bọt với Python
def bubble_sort(arr):
n = len(arr)
# Lặp qua toàn bộ mảng
for i in range(n):
# Lặp qua các phần tử từ 0 đến n-i-1
# Vì các phần tử cuối cùng đã được sắp xếp rồi
for j in range(0, n-i-1):
# So sánh 2 phần tử kế tiếp
if arr[j] > arr[j+1]:
# Hoán đổi 2 phần tử
arr[j], arr[j+1] = arr[j+1], arr[j]
# Ví dụ
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Mảng đã sắp xếp:")
for i in range(len(arr)):
print("%d" % arr[i])
Cài đặt thuật toán sắp xếp nổi bọt với C++
#include <iostream>
using namespace std;
void bubble_sort(int arr[], int n) {
// Lặp qua toàn bộ mảng
for (int i = 0; i < n; i++) {
// Lặp qua các phần tử từ 0 đến n-i-1
// Vì các phần tử cuối cùng đã được sắp xếp rồi
for (int j = 0; j < n-i-1; j++) {
// So sánh 2 phần tử kế tiếp
if (arr[j] > arr[j+1]) {
// Hoán đổi 2 phần tử
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
// Ví dụ
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr, n);
cout << "Mang da sap xep: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Đánh giá độ phức tạp của thuật toán sắp xếp nổi bọt
Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n^2) trong trường hợp xấu nhất, trung bình và trong trường hợp tốt nhất. Điều này có nghĩa là với một mảng có n phần tử, thuật toán sẽ thực hiện n*(n-1)/2 lần so sánh và hoán đổi.
Vì vậy, nếu số lượng phần tử cần sắp xếp là lớn, thì sử dụng thuật toán sắp xếp nổi bọt sẽ không hiệu quả. Trong trường hợp này, ta nên sử dụng các thuật toán sắp xếp khác như sắp xếp chọn, sắp xếp chèn hoặc sắp xếp nhanh.