#include <iostream>



using namespace std;



void insertSort(int a[], int n)

{

    for(int i=1;i<n;++i)

    {

        if(a[i]<a[i-1])

        {

            int temp = a[i];



            int j;

            for(j=i-1;j>=0&&temp<a[j];--j)

            {

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

            }

            a[j+1] = temp;

        }

    }



}

int main()

{

    const int N=7;

    int a[]={3,1,7,9,2,5,4};

    insertSort(a,N);

    for(int i=0;i<N;++i)

    {

        cout<<a[i]<<" "<<endl;

    }

    return 0;

}