Chào mừng các bạn quay trở lại với code từ tâm. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++.
Bài viết đầu tiên này chúng ta sẽ cùng tìm hiểu về thuật toán sắp xếp bubble sort hay còn gọi là sắp xếp nổi bọt. Nội dung bài viết bao gồm các phần sau:
- Ý tưởng của thuật toán
- Các bước mô phỏng
- Code thuật toán bằng C++
- Cách tối ưu thuật toán
- Đánh giá thuật toán
- Một vài ứng dụng của thuật toán
Ý tưởng của thuật toán bubble sort
- Bubble Sort là thuật toán sắp xếp đơn giản nhất hoạt động bằng cách hoán đổi nhiều lần các phần tử liền kề nếu chúng sai thứ tự.
- Mục đích sau các vòng chạy là tìm được phần tử lớn nhất đưa về trị cuối cùng của dãy.
Các bước mô phỏng thuật toán sắp xếp nổi bọt
- 1. Bắt đầu chọn phần tử tại vị trí đầu tiên, rồi so sánh phần tử đầu tiên và phần tử thứ hai. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng sẽ được hoán đổi.
– Tiếp theo sẽ so sánh giá trị tài vị trí thứ hai và thứ ba. Hoán đổi giá trị của chúng nếu chúng không theo thứ tự.
– Quá trình trên cứ tiếp tục cho đến phần tử cuối cùng. - 2. Quá trình tương tự diễn ra cho các lần lặp còn lại. Sau mỗi lần lặp, phần tử lớn nhất trong số các phần tử chưa được sắp xếp được đặt ở cuối.
– Trong mỗi lần lặp, việc so sánh diễn ra cho đến phần tử chưa được sắp xếp cuối cùng.
– Mảng được sắp xếp khi tất cả các phần tử chưa được sắp xếp được đặt đúng vị trí của chúng.
Triển khai code thuật toán sắp xếp nổi bọt với C++
Thuật toán sắp xếp nổi bọt có thể triển khai 1 cách đơn giản như sau:
#include <iostream>
using namespace std;
void swap(int* x, int* y) {
int t;
t = *x;
*y = *x;
*y = t;
}
void printAray(int* arr, int n) {
cout << "Giá tri của mảng sau khi sắp xếp là" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
void bubleSortArray(int* arr, int n) {
for (int i = 0; i < n - 1; i++){
for (int j = 0; j < n - i - 1; j++){
if (arr[j] > arr[j + 1]){
swap(arr[j], arr[j + 1]);
}
}
}
printAray(arr, n);
}
int main()
{
int arr[100];
int n;
cout << "Nhap vao so phan tu cua mang" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "nhap phan tu arr[" << i << "]" << endl;
cin >> arr[i];
}
bubleSortArray(arr, n);
}Tối ưu thuật toán sắp xếp nổi bọt
- Trong đoạn mã trên, tất cả các so sánh có thể được thực hiện ngay cả khi mảng đã được sắp xếp. Điều này làm tăng thời gian thực hiện.
- Mã có thể được tối ưu hóa bằng cách chúng ta khai báo thêm một biến $swap chẳng hạn tùy bạn đặt có giá trị bằng 0. Sau mỗi lần lặp, nếu không có lần swap nào diễn ra thì không cần thực hiện thêm các vòng lặp nữa.
Code minh họa.
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i= 0; i< n- 1; ++i) {
int swap = 0;
for (int j = 0; j < n- i - 1; ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swap = 1;
}
}.
if (swapped == 0)
break;
}
}
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << array[i];
}
cout << "\n";
}
int main() {
int data[] = {-2, 45, 0, 11, -9};
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
printArray(data, size);
}
Đánh giá thuật toán sắp xếp bubble
Độ phức tạp
- Thấy ngay số phép so sánh là luôn không đổi, tức không phụ thuộc vào tình trạng ban đầu của dãy. Với i bất kỳ, ta luôn phải so sánh V[j] với V[j-1], mà j chạy từ n đến i+1, tức ta tốn n-i phép so sánh. Thêm nữa, i chạy từ 1 đến n-1. Vậy ta tính được số phép so sánh tổng cộng: ∑(n-i) với i chạy từ 1 đến n-1 = (n-1) + (n-2) + … + 1 = n(n-1)/2.
- Số phép hoán vị (tương đương 3 phép gán) lại phụ thuộc vào tình trạng ban đầu của dãy. Cụ thể như sau: § Trường hợp tốt nhất: Dãy ban đầu đã có thứ tự. Ta thấy ngay ta không tốn một phép hoán vị nào.§ Trường hợp xấu nhất: Dãy ban đầu có thứ tự ngược. Xét i bất kỳ, ta thấy rằng mỗi lần so sánh a[j] với a[j-1], ta đều phải thực hiện hoán vị. Điều này có nghĩa là số phép hoán vị bằng n(n-1)/2.
- Tổng kết lại, ta có độ phức tạp của Bubble Sort thuộc O(n2) trong mọi trường hợp.
Ưu điểm & Nhược điểm
- Ưu điểm: Code ngắn gọn nhất.
- Nhược điểm: Hiệu suất thấp.
Các thuật toán liên quan
Tổng kết
Hy vọng qua bài viết về giải thuật sắp xếp Bubble Sort (Sắp xếp nổi bọt) này sẽ giúp các bạn hiểu và vận dụng tốt vòng lặp for cũng như hiểu được ý tưởng của giải thuật này. Cũng khá thú vị đấy chứ nhỉ!
Cảm ơn các bạn đã theo dõi series thuật toán này.
Bình luận: