#include<stdio.h>

#define M1 20
#define M2 10

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

/** 1. feladat **/
void fiboK(int t[], int k, int n){
	int i, j;	
	for (i=0; i<k; i++){	// az elso k elemet feltoltjuk 1-esekkel
		t[i] = 1;
	}
	
	for (i=k; i<n; i++){	// n-edik elem szamolasa: i=k..n
		t[i] = 0;	// kinulazzuk az aktulis elemet, hogy ide tudjuk osszegezni a megelozo k elemet
		for (j=i-k; j<i; j++){	//	visszalepunk k elemnyit (i-k), es az aktualis elemig (i) osszegzunk
			t[i] += t[j];
		}
	}
	
	kiir(t, n);
}

/** 2. feladat **/
void beszuroRendezes(int t[], int n){
	int	count = 0, // itt gyujtjuk majd, hogy a vizsgalt elem hany tombbeli elemnel nagyobb
		i, j, 	// indexvaltozok
		tmp;	// ide mentjuk majd ki a vizsgalt elemet
	kiir(t, n);
	for (i=1; i<n; i++){	// az osszes elemet meg kell vizsgalni egyszer (kiveve az elsot, mivel neki ugysincs balrol szomszedja)
		count = 0;	// minden elem eseten nullazas, hogy ujra gyujthessuk az aktualis osszeget	
		tmp = t[i];	// mentsuk ki a vizsgalt elemet, hogy a tomb eleminek mozgatasakor ne vesszen el
		
		for (j=0; j<i; j++){	// menjunk vegig az egesz tombon es vizsgaljuk meg, hogy az aktualis elem hany elemnel nagyobb
			if (tmp > t[j]){
				count++;	// ha nagyobb, akkor noveljuk a fenntartott valtozo erteket
			}
		}

		for (j=i; j>count; j--){	// ha balrol jobbra akarunk elemeket mozgatni, akkor jobbrol balra kell feldolgozni oket
			t[j] = t[j-1];	// jobbra mozgatas
		}
		t[count] = tmp;	// ahany elem nagyobb volt a vizsgalt elemnel, arra a poziciora kell tenni a muvelet vegen
		kiir(t, n);
		//getchar();	// komment kitorlesevel elemenkenti mozgatasonkent Enter utesevel engedhetjuk tovabb a program futasat
	}
	
	kiir(t, n);
}

int main(){
	int t1[M1], t2[M2] = {41,4,1,38,23,-12,78,12,-1000,2};
	
	/** Fuggvenyek hivasara pelda **/
	
//	fiboK(t1, 4, M1);
	// output: 1  1  1  1  4  7  13  25  49  94  181  349  673  1297  2500  4819  9289  17905  34513  66526
	
	beszuroRendezes(t2, M2);
	// output: -1000  -12  1  2  4  12  23  38  41  78
	
	return 0;
}