Thuật toán InsertSort

Trước hết ta xem phần tử  a[1] là một dãy đã có thứ tự.
               -- Bước 1, xen phần tử a[2] vào danh sách đã có thứ tự a[1] sao cho a[1], a[2] là một danh sách có thứ tự.
               -- Bước 2, xen phần tử a[3] vào danh sách đã có thứ tự a[1], a[2] sao cho a[1], a[2], a[3] là một danh sách có thứ tự.
               -- Tổng quát, bước i, xen phần tử a[i+1] vào danh sách đã có thứ tự a[1],a[2],..a[i] sao cho a[1], a[2],.. a[i+1] là một danh sách có thứ tự.
               -- Phần tử đang xét a[j] sẽ được xen vào vị trí thích hợp trong danh sách các phần tử đã được sắp trước đó a[1],a[2],..a[j-1] bằng cách so sánh khoá của a[j] với khoá của a[j-1] đứng ngay trước nó. Nếu khoá của a[j] nhỏ hơn khoá của a[j-1] thì hoán đổi a[j-1] và a[j] cho nhau và tiếp tục so sánh khoá của a[j-1] (lúc này a[j-1] chứa nội dung của a[j]) với khoá của a[j-2] đứng ngay trước nó...

>...Tải về Full Code .CPP...

>(Click vào đây)

/*
Name: Thuat toan Insert Sort
Copyright: None
Author: Tran Anh
Description: https://gimi.vn
*/
#include<conio.h>
#include<stdio.h>
#include<iostream>
using namespace std;

void swap(int &a, int &b)
{
 int temp;
 temp=a;
 a=b;
 b=temp;
}

void InsertSort(int a[], int n)
{
 for(int i=1;i<n;i++)
  for(int j=i;j>0;j--)
   if(a[j]<a[j-1])
    swap(a[j],a[j-1]);
}

main()
{
 int n=8;
 int a[]={1,5,3,4,9,7,3,4};

 for(int i=0;i<n;i++)
  cout<<a[i]<<"  ";

 cout<<endl<<"Insert Sort: "<<endl;

 InsertSort(a,n);

 for(int i=0;i<n;i++)
  cout<<a[i]<<"  ";

 getch();
 return 0;
}