// IMPLEMENTACJA SORTOWANIA PRZEZ WSTAWIANIE - INSERTIONSORT
// www.algorytm.org

#include <iostream>
// BIBLIOTEKI NIEZBEDNE DO WYPELNIENIA TABLICY PSEUDOLOSOWYMI LICZBAMI
#include <cstdlib>
#include <ctime>

using namespace std;

// DEKLARACJA FUNKCJI SORTUJACEJ TABLICE PRZYJMUJACA PARAMETRY TAKIE JAK TABLICA I LICZBA JEJ ELEMENTOW
void sort(int tab[], int w);

int main()
{
    // ZDEFINIOWANIE STALEJ 'W' ORAZ TABLICY O WIELKOSCI 'W'
    const int w = 10;
    int tab[w];
    // WYWOLANIE FUNKCJI ZAPEWNIAJACEJ LOSOWANIE ROZNYCH WARTOSCI PRZY KAZDYM URUCHOMIENIU PROGRAMU
    srand(time(NULL));
    // WYPPELNIENIE TABLICY WYLOSOWANYMI WARTOSCIAMI Z PRZEDZIALU OD 1 DO 100
    for(int i = 0; i < w; i++)
        tab[i] = 1+rand()%100;
    // WYWOLANIE ZDEFINIOWANEJ PRZEZ NAS FUNKCJI 'SORT' SORTUJACEJ ELEMENTY TABLICY
    sort(tab,w);
    // WYPISANIE POSORTOWANEJ JUZ TABLICY NA EKRAN
    for(int i = 0; i < w; i++)
        cout << tab[i] << endl;

    return 0;
}

// DEFINICJA FUNKCJI SORTUJACEJ TABLICE PRZYJMUJACA PARAMETRY: TABLICA I LICZBA JEJ ELEMENTOW
void sort(int tab[], int w)
{
    // ZADEKLAROWANIE ZMIENNEJ POMOCNICZEJ NA PRZECHOWYWANIE WARTOSCI AKTUALNEJ CYFRY
    int x,k;
    // PETLA PRZECHODZACA PO INDEKSACH OD 1 DO 'N' TABLICY CYFR
    for(int i = 1; i < w; i++)
    {
        // ZMIENNEJ POMOCNICZEJ PRZYPISUJEMY WARTOSC CYFRY O AKTUALNYM INDEKSIE
        x = tab[i];
        // SZUKAMY MIEJSCA WSROD POPRZEDZAJACYCH AKTUALNY INDEKS CYFR W KTORYM KOLEJNA Z CYFR BEDZIE WIEKSZA OD TEJ O AKTUALNYM INDEKSIE I TUZ ZA NIA WSTAWIAMY DANA CYFRE
        for(k = i-1; k >= 0; k--)
        {
            if(x < tab[k])
            {
                tab[k+1] = tab[k];
            }
            else
                break;
        }
        tab[k+1] = x;
    }
}