// Implementacja sortowania przez wstawianie - InsertionSort
// www.algorytm.org

#include <iostream>
#include <algorithm>

using namespace std;

void wyswietl(int *tab, int n)
    {
        cout << endl;
        for(int i=0; i<n; i++)
        {
            cout << tab[i] << " , ";
        }
        cout << endl;
    }

int insert_sort(int *tab, int n)
{
     int k,temp;

     for(int i=0; i<(n-1); i++)
     {
        if(tab[i+1]<tab[i])                   //Sprawdzamy czy element na nastepnej pozycji jest mniejszy od obencego.
          {
            k = i;
            while(k>=0 && tab[i+1]<tab[k])   //Wtedy zliczamy do poczatku ile jest mniejszych elementow
            {                                 //Zmienna k to wskaznik odpowiedniego miejsca.
                k--;
            }

            if(k==i-1) swap(tab[i], tab[i+1]);//Jezeli element przesuwamy tylko o jedno miejsce,
                                              //poprostu zamieniamy dwa sasiadujace.

            else                              //W innym wypadku, kopiujemy element do tempa, przesuwamy
            {                                 // wszytskie elementy w prawo, i wsadzamy go w odpowiednie miejsce.
                temp = tab[i+1];

                for(int l=i+1; l>k+1; l--)
                {
                    tab[l] = tab[l-1];
                }

                tab[k+1] = temp;
            }


          }
          wyswietl(tab, n);
     }


}

int main()

{
    int tab[8] = {4,3,6,7,5,8,1,2};

    cout << "Sortujemy ciag przez wstawianie" << endl;
    cout << "Wejsciowy ciag : "<<endl;
    wyswietl(tab, 8);

    insert_sort(tab, 8);

    cout << endl << "Posortowany ciag : " << endl;
    wyswietl(tab, 8);

    cin.get();
    return 0;
}