Thuật toán Bubble-Sort
Ý tưởng thuật toán:
- Nếu phần tử đang xét có khóa nhỏ hơn phần tử bên trái của nó ta tiến đưa nó về bên trái của dãy bằng cách hoán vị với phần tử bên trái của nó.
- Tiếp tục thực hiện như thế đối với bài toán có n phần tử thì sau n – 1 bước ta thu được danh
sách tăng dần.
Ví dụ: sử dụng thuật toán Bubble Sort sắp xếp dãy số {3, 10, 4, 6, 2, 6, 15, 3, 9,7} theo thứ tự tăng dần.
Sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 3, 4, 6, 6, 7, 9, 10, 15}.
Cài đặt thuật toán:
[ Code Turbo C++]
#include <iostream.h>// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác
#include <conio.h>
#define max 100
//nhap day
void NhapDay(int a[],int n) {
for(int i=0; i<n; i++) {
cout<<"\n a["<<i<<"] =";
cin>>a[i];
}
}
//xuat day
void XuatDay(int a[],int n) {
cout<<"\n IN DAY: ";
for(int i=0; i<n; i++)
cout<<a[i]<<"\t";
}
//hoan vi 2 phan tu
void Swap(int &a,int &b) {
int t = a;
a = b;
b = t;
}
//sap xep cac phan tu
void BubbleSort(int a[],int n) {
for(int i = 0; i < n-1; i++)
for(int j = n-1; j > i; j--)
if(a[j]<a[j-1])
Swap(a[j-1],a[j]);
}
//chuong trinh chinh
void main() {
int a[max],n;
clrscr();
cout<<"\n Nhap so phan tu:";
cin>>n;
NhapDay(a,n);
XuatDay(a,n);
cout<<"\n Sap xep Bubble-Sort: \n";
BubbleSort(a,n);
cout<<"\n Day vua sap xep la:";
XuatDay(a,n);
getch();
}
--------------------------------------------
Xem thêm các thuật toán khác:
* Có thể bạn quan tâm:
- Những cuốn sách mà các bạn không thể bỏ qua khi còn trẻ
- Khoá học tin học văn phòng tốt nhất
* Có thể bản quan tâm: [MMO] Hướng Dẫn *Kiếm Tiền Tự Động* Với Các Ứng Dụng Treo Máy *CỰC KỲ ĐƠN GIẢN VÀ HIỆU QUẢ*
Chúc các bạn thành công!