[C++]Thuật toán insertion sort (Sắp xếp chèn) thực hiện trên codeblock

Posted by : 86Gems 30 March 2014

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

Thuật toán:
Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu $a_1,...,a_{k}$ . Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu $a_1,...,a_{k-1}$ đã được sắp. Để sắp xếp phần tử $a_k=x$ ta tìm vị trí thích hợp của nó trong dãy $a_1,...,a_{k-1}$ . Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Các phần tử ≤x			Vị trí thích hợp	Các phần tử>x			Các phần tử chưa sắp
$a_1$	...	$a_{i-1}$	x	$a_{i+1}$	...	$a_{k-1}$	$a_{k+1}$	...	$a_n$

Code:

#include <iostream>
using namespace std;
void insertion_sort(int a[], int n)
{
     int i,tg,x;
     for (i=1;i<n;i++)
      {
        tg=a[i];
        x=i-1;
        while((x>=0)&&(a[x]>tg))
            {
            a[x+1] = a[x];
            x--;
            }
        a[x+1] =tg;
     }
}
int main()
{
    int n;
    cout <<"Nhap so cac so hang can sap xep: ";
    cin >> n;
    int a[n];
    cout<<"Nhap cac so hang: "<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<"a"<<i+1<<": " ;
        cin >>a[i];
        cout << endl;
    }
    insertion_sort(a,n);
    cout<<"Day sau khi sap xep: ";
    for(int i=0;i<n;i++)
        cout<<a[i] << " ";
}

{ 1 nhận xét... read them below or add one }

AnonymousWednesday, March 30, 2022
[C++]Thuật Toán Insertion Sort (Sắp Xếp Chèn) Thực Hiện Trên Codeblock >>>>> Download Now

>>>>> Download Full

[C++]Thuật Toán Insertion Sort (Sắp Xếp Chèn) Thực Hiện Trên Codeblock >>>>> Download LINK

>>>>> Download Now

[C++]Thuật Toán Insertion Sort (Sắp Xếp Chèn) Thực Hiện Trên Codeblock >>>>> Download Full

>>>>> Download LINK
ReplyDelete
Replies

Add comment

[C++]Thuật toán insertion sort (Sắp xếp chèn) thực hiện trên codeblock

{ 1 nhận xét... read them below or add one }

Popular Posts

Blogger news