Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán sắp xếp nổi bọt (Bubble Sort)
Trong bài này mình sẽ giới thiệu đến các bạn thuật toán sắp xếp nổi bọt (Bubble Sort). Đây là một thuật toán sắp xếp khá đơn giản và dễ hiểu.
Chúng ta sẽ cùng nhau tìm hiểu về khái niệm sắp xếp nổi bọt (Bubble Sort), thuật toán sắp xếp và cách triển khai. Sau đó mình sẽ có một ví dụ đơn giản áp dụng thuật toán (mình sẽ sử dụng ngôn ngữ C++ để viết).
1. Sắp xếp nổi bọt (Bubble Sort) là gì?
Sắp xếp nổi bọt được hiểu đơn giản như sau:
Thuật toán sắp xếp nổi bọt (Bubble Sort) sẽ tiến hành việc so sánh các cặp phần tử liền kề nhau và tráo đổi vị trí của nó cho đúng thứ tự mà người dùng mong muốn.
Bài viết này được đăng tại [free tuts .net]
Ví dụ:
Chúng ta có một tập các số như sau: A = {20; 5; 25; 30; 22; 40}. Giả sử chúng ta muốn sắp xếp theo chiều tăng dần từ trái sang phải, thì thuật toán sẽ hoạt động như sau:
- Thuật toán sẽ bắt đầu với cặp phần tử đầu tiên là {20; 5}. Trong cặp phần tử này 20 > 5 vì vậy thuật toán sẽ hoán đổi vị trí số 20 cho vị trí số 5. Sau khi hoán đổi được cặp phần tử mới là {5; 20}.
- Tiếp đến thuật toán sẽ so sánh cặp phần tử {20;25}. Trong trường hợp này vị trí của hai phần tử đã đúng, vì vậy thuật toán sẽ giữ nguyên vị trí của nó.
- Cứ như vậy thuật toán sẽ so sánh đến hết các cặp phần tử của tập A. Sau khi so sánh đến hết sẽ được kết quả như sau: A = {5; 20; 22; 25; 30; 40}.
2. Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++
Giả sử:
- Chúng ta có arr là một mảng chứa n phần tử.
- Một hàm
Swap()để tráo đổi các phần tử (hàm này mình sẽ viết ở bên dưới).
Giải thích thuật toán
- Trong thuật toán chúng ta cần tạo một biến haveSwap để kiểm tra xem tại lần lặp hiện tại có xảy ra việc trao đổi hai số hay không.
- Sử dụng vòng lặp for để lặp tất cả các phần tử có trong mảng. Nếu phần tử thứ J > J + 1 thì tiến hành gọi hàm
Swap()để tráo đổi vị trí. Sau đó gán haveSwap = true và ngược lại. - Nếu không có Swap nào được thực hiện thì mảng đã được sắp xếp. Khi đó chúng ta sẽ thoát khỏi vòng lặp và không cần lặp thêm nữa.
Thuật toán sắp xếp nổi bọt C++
void bubbleSort(int arr[], int n)
{
int i, j;
bool haveSwap = false;
for (i = 0; i < n-1; i++){
// i phần tử cuối cùng đã được sắp xếp
haveSwap = false;
for (j = 0; j < n-i-1; j++){
if (arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
haveSwap = true; // Kiểm tra lần lặp này có swap không
}
}
// Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
if(haveSwap == false){
break;
}
}
}3. Ví dụ sắp xếp nổi bọt áp dụng với mảng
Chúng ta sẽ áp dụng thuật toán trên để làm một bài toán đơn giản. Cụ thể chúng ta sẽ sắp xếp các phần tử có trong một mảng được nhập tử bàn phím.
Gợi ý:
- Việc đầu tiên chúng ta cần tạo hàm
Swap()để thực hiện tráo đổi vị trí các phần tử. - Tiếp theo cần tạo hàm
bubbleSort()để thực hiện sắp xếp các phần tử. - Cuối cùng chỉ cần tạo hàm main và yêu cầu người dùng nhập vào các phần tử cho mảng. Sau đó gọi hàm
bubbleSort()để sắp xếp là xong.
Code Mẫu:
#include <iostream>
#include <stdio.h>
using namespace std;
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
// Hàm sắp xếp bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool haveSwap = false;
for (i = 0; i < n-1; i++){
// i phần tử cuối cùng đã được sắp xếp
haveSwap = false;
for (j = 0; j < n-i-1; j++){
if (arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
haveSwap = true; // Kiểm tra lần lặp này có swap không
}
}
// Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
if(haveSwap == false){
break;
}
}
}
/* Hàm xuất mảng */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++){
cout << arr[i];
cout<<"\t";
}
}
int main()
{
int n;
do{
cout << "\nNhập vào số lượng phần tử có trong mảng: ";
cin >> n;
}while(n <= 0);
int a[n];
for(int i = 0;i < n;i++){
cout<<"a["<<i<<"]=";
cin >> a[i];
};
bubbleSort(a, n);
cout<<"Mảng sau khi được sắp xếp: \n";
printArray(a, n);
cout<<"\n---------------------------------------\n";
cout<<"Chương trình này được đăng tại Freetuts.net";
}Kết quả:
Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử có trong mảng. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++. Chúc các bạn thực hiện thành công!!!.
