[Phần 1] Thuật toán sắp xếp lựa chọn (selection sort)

1. Tư tưởng của thuật toán sắp xếp lựa chọn.

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]. Okey, tiếp đến lấy từ phần tử a[2] -> a[n]. Phần tử nào nhỏ hơn phần tử a[1] thì đổi chỗ chúng cho nhau (giả sử a[6]<a[1] thì đổi chỗ a[6] cho a[1], sau đó duyệt tiếp từ a[7]->a[n] và so sánh với a[1]). Cứ như thế, khi đi hết từ a[2] -> a[n] thì sẽ tìm được phần tử nhỏ nhất trong n phần tử đã cho.

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]. Okey, tiếp đến lấy từ phần tử a[3] -> a[n]. Phần tử nào nhỏ hơn phần tử a[2] thì đổi chỗ chúng cho nhau (giả sử a[6]<a[2] thì đổi chỗ a[6] cho a[2], sau đó duyệt tiếp từ a[7]->a[n] và so sánh với a[2]). Cứ như thế, khi đi hết từ a[3] -> a[n] thì sẽ tìm được 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ử. 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++.

#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 SelectionSort(int A[], int n){
    for(int i = 0; i <n-1; i++){
        for(int j = i+1; j<n; j++){
            if(A[i]> A[j]){
                HoanVi(A[i], A[j]);
            }
        }
    }
}

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
    SelectionSort (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/8b5o
3. Ví dụ minh họa

 

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

One Response to [Phần 1] Thuật toán sắp xếp lựa chọn (selection sort)

  1. Pingback: [Phần 2] Thuật toán sắp xếp nổi bọt (bubble sort) | HanhTrinhTuoiTre.Com

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 »