#include <stdio.h>

/*
    Insertion sort.
    Vidi funkcije insertion_sort i insert (sve ostale funkcije su pomocne). Unutar insertion_sort mozete zakomentirati poziv funkcije detaljni_ispis.

    Ideja:
        1. Ubaci u sortirano polje { x[0] } element x[1] tako da polje ostane sortirano.
        2. Ubaci u sortirano polje { x[0], x[1] } element x[2] tako da polje ostane sortirano.
        3. Ubaci u sortirano polje { x[0], x[1], x[2] } element x[3] tako da polje ostane sortirano.
        ...
      n-1. Ubaci u sortirano polje { x[0], x[1], x[2], ..., x[n-2] } element x[n-1] tako da polje ostane sortirano.
*/ 

void ispis( char poruka[], int x[], int n )
{
    printf( "%s\n", poruka );

    int i;
    for( i = 0; i < n; ++i )
        printf( "%d ", x[i] );
    printf( "\n\n" );
}


void detaljni_ispis( int x[], int n, int novi )
{
    printf( "Do sada je sortirano prvih %d elemenata: ", n );
    
    int k;
    for( k = 0; k < n; ++k )
        printf( " %d ", x[k] );

    printf( "\n -> ubacujem element x[%d]=%d.", n, novi );

    printf( "            ...Pritisni enter..." );
    scanf( "%*c" );

    printf( "\n\n" );
}


void insert( int x[], int n, int novi )
{
    // Polje x duljine n je vec sortirano. Ubaci novi element tako da ostane sortirano.
    
    int i = n-1;
    while( i >= 0 && x[i] > novi )
    {
        x[i+1] = x[i];
        --i;
    }

    // Sada je i=-1 ili je x[i] <= novi.
    x[i+1] = novi;
}


void insertion_sort( int x[], int n )
{
    int i;

    for( i = 1; i < n; ++i )
    {
        detaljni_ispis( x, i, x[i] );

        insert( x, i, x[i] );
    }
}


int main( void )
{
    int x[7] = {6, 1, 8, 3, 9, 4, 7}, n = 7;

    ispis( "Prije sortiranja", x, n );
    insertion_sort( x, n );
    ispis( "Poslije sortiranja", x, n );

    return 0;
}