[Phần 2] Thuật toán sắp xếp nổi bọt (bubble sort)

1. Tư tưởng của thuật toán sắp xếp nổi bọt. (bubble sort)

Tư tưởng của thuật toán này không có gì khác biệt nhiều so với thuật toán sắp xếp lựa chọn trong phần 1-hanhtrinhtuoitre. Hãy cũng tìm hiểu về nó nhé!

Giả định có n phần tử, từ a[1]->a[n] và muốn sắp xếp tăng dần.

Bước 1: Tìm phần tử nhỏ nhất trong n phần tử đó bằng cách
– Chọn ra phần tử đâu tiên là a[1]. Bây giờ ta sẽ duyệt từ phần từ a[n] trở về a[2]. Phần tử a[x]<a[x-1] thì đổi chỗ chúng cho nhau (nếu a[x]>a[x-1] thì không làm gì cả). Sau đó, tiếp tục duyệt tiếp từ a[x-1] trở về a[2]. Cuối cùng của bước này là so sánh a[2] và a[1] để tìm ra phần tử nhỏ nhất trong n phần tử đó.

Bước 2: Như vậy, ta đã tìm được phần tử nhỏ nhất trong n phần tử đã cho qua bước 1. Bây giờ, ta giữ nguyên phần tử đó, và tìm phần tử nhỏ nhất trong n-1 phần tử còn lại.
– Chọn ra phần tử đâu tiên là a[2]. Bây giờ ta sẽ duyệt từ phần từ a[n] trở về a[3]. Phần tử a[x]<a[x-1] thì đổi chỗ chúng cho nhau (nếu a[x]>a[x-1] thì không làm gì cả). Sau đó, tiếp tục duyệt tiếp từ a[x-1] trở về a[3]. Cuối cùng của bước này là so sánh a[3] và a[2] để tìm ra phần tử nhỏ nhất trong n-1 phần tử đó.

Cứ tiếp tục lặp các bước, cho đến khi chỉ còn 2 phần tử (a[n] và a[n-1]). Lúc đó ta sắp xếp được 2 phần tử này là coi như bài toán đã có lời giải.

2. Mô tả thuật toán bằng ngôn ngữ C++.

//hanhtrinhtuoitre.com
#include <iostream>
using namespace std;

void NhapMang (int A[], int n){
    for(int i = 0; i < n; i++)
    {
        cout<<"Nhap phan tu thu A["<< i <<"] =";
        cin>>A[i];
    }
}

void XuatMang (int A[], int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << A[i]<< "  ";
    }
}

void HoanVi (int &a, int &b)
{
    //cho nay truyen tham chieu: (int &a, int &b)
    //Khong phai la truyen tham tri: (int a, int b)
    int temp = a;
    a = b;
    b = temp;
}

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]){
                HoanVi(A[j], A[j-1]);
            }
        }
    }
}

int main() {
    int A[100], n;
    cout<<"Nhap so phan tu:";
    cin>>n;
    NhapMang (A,n);
    cout<<"Mang vua nhap la: \n";  // \n tuc la xuong dong
    XuatMang (A,n);
    cout<<endl; // xuong dong
    BubbleSort (A,n);
    cout<<"Mang vua sap xep la: \n"; //  \n tuc la xuong dong
    XuatMang (A,n);
    return 0;
    
}

Nếu bạn muốn chạy trực tiếp các dòng lệnh để thử nghiệm tính chính xác thì có thể trùy cập vào đường link này: http://cpp.sh/26mz

3. Ví dụ minh họa

sap xep noi bot - bubble sort

This entry was posted in Kinh nghiệm - thủ thuật - tài liệu. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

:1: :2: :12: :46: :59: :51: :38: :31: :22: :15: :8: more »