Insertion Sort

Thuật toán Insertion Sort

1.      Ý tưởng:

Chèn từng phần tử một vào dãy đã được sắp xếp đến bước hiện tại, vào đúng vị trí của nó để bảo đảm sau khi chèn dãy vẫn có thứ tự

2.      Thuật toán:

lgorithm bubleSort(A)

            Input: Một mảng n phần tử số A

            Output: Mảng A đã được sắp xếp tăng dần.

             ForA i ← 1 to n-1 do

                        For j ← n downto i+1 do

                                    if A[j] < A[j-1] then

                                                swap(A,j-1,j)

            Return array A

3.      Mã nguồn bằng C:

#include<stdio.h>   

#include<conio.h>

void bubble(int a[],int n)   

  {   

        int i,j,t;   

         for(i=n-2;i>=0;i--)   

         {   

            for(j=0;j<=i;j++)  

              {   

                    if(a[j]>a[j+1])   

                                    {   

                                      t=a[j];   

                                     a[j]=a[j+1];   

                                     a[j+1]=t;   

                                    }   

                   }   

           }     

  }     

  void main()   

  {     

      int a[100],n,i;   

      clrscr();      

      scanf("%d",&n);   

        for( i=0;i<=n-1;i++)   

            { printf("\n\n Enter integer value for element no.%d : ",i+1);   

              scanf("%d",&a[i]);   

            }   

         bubble(a,n);    

       for( i=0;i<=n-1;i++)   

       printf("%3d",a[i]);   

    }