Code C/C++: Thuật toán sắp xếp nổi bọt (Bubble Sort Algorithm)


Ý tưởng thuật toán: xuất phát từ phần tử cuối danh sách ta tiến hành so sánh với phần tử bên trái của 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 chương trình:
#include<math.h>
#include<iostream>
#include<conio.h>
#define max 100
using namespace std;
//Nhập mảng
void NhapMang(int A[],int n){
for(int i=0; i<n;  i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
//Xuất mảng
void XuatMang(int A[],int n){
cout<<endl;
for(int i=0; i<n;  i++)
cout<<A[i]<<"\t";
//Hoán vị 2 phần tử
void Swap(int &a,int &b){
int temp = a;
a = b;
b =  temp;
}
//Sắp xếp các phần tử theo Bubble Sort
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]);
}
//Chương trình chính
int main(){
int A[max],n;
cout<<"Nhap so phan tu:";
cin>>n;
NhapMang(A,n);
cout<<"\nMang vua nhap la:";
XuatMang(A,n);
cout<<endl;
BubbleSort(A,n);
cout<<"\nMang vua sap xep la:";
XuatMang(A,n);
getch();
return 0;
}
Kết quả chương trình:

Từ khóa: Sắp xếp, nổi bọt, Bubble sort, thuật toán.

Related Posts
Previous
« Prev Post

5 comments