/*
* Mateusz Soroka grupa 5
* nr indeksu 250999
* Algorytmy i struktury danych
* HeapSort
* Dane zostają wczytane z pliku "unsorted.txt"
* Wynik zostaje zapisany do pliku "sorted.txt"
*/


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void Swap(int *a, int *b){
	int temp = *a;
	*a = *b;
	*b = temp;
}

void Heapify(int Array[], int i, int HeapSize){

while(true){

	int Largest = 0;
	int LeftSon = 2 * i;
	int RightSon = 2 * i + 1;

	if( LeftSon <= HeapSize && Array[LeftSon-1] > Array[i-1] ) Largest = LeftSon;
	else Largest = i;
	if( RightSon <= HeapSize && Array[RightSon-1] > Array[Largest-1]) Largest = RightSon;
	if( Largest != i){
		Swap( &Array[i-1], &Array[Largest-1]);
		i = Largest;
	}
	else break;
}
}

void BuildHeap(int Array[], int HeapSize){

	int i;
	for( i=HeapSize/2; i>0; i--) Heapify(Array, i, HeapSize);
}

void HeapSort(int Array[], int HeapSize){

	int i;
	BuildHeap(Array, HeapSize);
	for( i=HeapSize; i>1; i--){
		Swap( &Array[i-1], &Array[0]);
		HeapSize--;
		Heapify( Array, 1, HeapSize);
	}
}


int main(void){

	int i;
	int HeapSize = 0;

	FILE *before = fopen("unsorted.txt", "r");
	if( before == NULL){
		printf("Błąd odczytu pliku lub plik nie istnieje..\n");
		exit(0);
	}
	else{
		char ch;
		while( ch!= EOF ){
			ch = fgetc( before );
			if( ch == '\n' ) HeapSize++;
		}
		printf("Pomyślne otworzenie pliku, rozpoczynanie sortowania..\n");
	}

	int Array[HeapSize];

	for( i=0; i<HeapSize; i++){
		fscanf( before, "%d", &Array[i]);
	}

	fclose( before );

	HeapSort( Array, HeapSize );


	for(i=0;i<HeapSize;i++){
	printf("%d\n",Array[i]);
	}

	/*FILE *after = fopen("sorted.txt","w");
	for( i = 0; i<HeapSize; i++){
		fprintf( after, "%d\n", Array[i]);
	}


	if( after == NULL){
		printf("Sortowanie niepomyślne lub błąd pliku wyjściowego..\n");
		exit(0);
	}
	else printf("Sortowanie pomyślne, dane zapisane w 'sorted.txt'..\n");

	fclose( after );*/

	return 0;
}