/*
Project SORT

Demonstration of sorting algos

Version 1.0 / 2002.03.13
Autor: pstrainer@gmx.net

Files:
sort.h, sort_main.cpp, sort_input.cpp, sort_sort.cpp,
sort_output.cpp, ps_trainer.cpp
This file: sort_sort.cpp:
Performs sorting of data

Warning: This project contains only experimental code.
The code may contain errors or may produce erroneous results.
If you use any part, do it at your own risk !
*/

#include "sort.h"

void bubblesort (int, int*);
int bubblesort_up (int, int, int*);
int bubblesort_down (int, int, int*);
void selectsort (int, int*);
void bucketsort (int, int*);
void insertsort (int, int*);
void quicksort(int, int, int*);
void swap_array (int, int, int*);

void print_zeile (int *array);

void sort_data(int anz, int *zahlenfeld) {
	// perform sort, run timer and display time_per_sort
	// dev. pipeline: other sort algos can be installed here
	double tpl;
	int std,invalid;
	char option;
	clock_t ta,tz;

	printf("\nSortierung der %d Rohdaten:\n",anz);
	option='*';
	invalid=-2;			// counter for invalid user input

	while ((option!='1') && (option!='2') && (option!='3') && (option!='4') && (option!='5') && (option!='A')) {
		printf("(1)BubbleSort, (2)SelectSort, (3)BucketSort\n");
		printf("(4)InsertSort, (5)QuickSort,  (A)bbruch ?    ");
		option = _getche();
		if (option==EOF) option='1';	// EOF equivalent to BubbleSort
		option =mychar_upper(option);	// convert to uppercase
		printf("\n");
		if ((option!='1') && (option!='2') && (option!='3') && (option!='4') && (option!='5') && (option!='A')) {
			printf("\nUngueltige Option !\n");
			invalid++;
			if (invalid>0) option='A';
		}
	}

	// Branch to data sort functions
	ta=clock();			// start timer
	switch (option) {
		case '1': {bubblesort(anz,zahlenfeld);break;}
		case '2': {selectsort(anz,zahlenfeld);break;}
		case '3': {bucketsort(anz,zahlenfeld);break;}
		case '4': {insertsort(anz,zahlenfeld);break;}
		case '5': {printf(" QuickSort: ");quicksort(0,anz-1,zahlenfeld);break;}
		default: {printf(" Keine Sortierung.\n");}
	}
	tz=clock();			// stop timer
	// Calc time per loop in microseconds
	tpl=double(tz-ta)/double(CLOCKS_PER_SEC)*1000000.0/anz;
	std=int(sqrt(tpl)/tpl*100.0);	// calc accuracy in %
	if (tpl<=0.0) printf(" Sort-Zeit zu gering fuer Zeitmessung\n");
	else printf(" Zeit pro sortierter Zahl = %f us +/- %d%c\n",tpl,std,'%');
}

void bubblesort (int anz, int *zahlenfeld) {
/*	BubbleSort int array of size anz
	Sort alternating up & down and keep track of the swaps performed.
	Loop the algo as long as swaps>0, exit if swaps=0
	Mind: after each run the max /min positions are fixed
	anz...size of data in array zahlenfeld (NOT size of array !)
	zahlenfeld...array containing the data to sort
*/
	int swaps,runs,pl,pr;
	printf(" BubbleSort: ");
	runs=0;
	swaps=1;
	pl=0;
	pr=anz-1;
	while (swaps>0) {
		// run alogo upwards
		runs++;
		swaps=bubblesort_up(pl,pr,zahlenfeld);
		if (swaps>0) {
			// run algo downwards
			runs++;
			swaps=bubblesort_down(pl,pr,zahlenfeld);
		}
		// next run in reduced range:
		pl++;
		pr--;
	}
	printf(" %d runs wurden ausgefuehrt.\n",runs);
}

int bubblesort_up (int pl, int pr, int *array) {
	// BubbleSort int array of size anz UP
	// pl,pr... left & right ranges of array to scan
	int i,swaps;
	swaps=0;
	for (i=pl;i<pr;i++) {
		if (array[i+1]<array[i]) {
			swap_array(i,i+1,array);
			swaps++;
		}
	}
	return swaps;
}

int bubblesort_down (int pl, int pr, int *array) {
	// BubbleSort int array of size anz DOWN
	// pl,pr... left & right ranges of array to scan
	int i,swaps;
	swaps=0;
	for (i=pr;i>pl;i--) {
		if (array[i-1]>array[i]) {
			swap_array(i,i-1,array);
			swaps++;
		}
	}
	return swaps;
}

void selectsort (int anz, int *zahlenfeld) {
/*	SelectSort int array of size anz
	Find the first element (minimum), swap it into place.
	Do so with each element until done.
	anz...size of data in array zahlenfeld (NOT size of array !)
	zahlenfeld...array containing the data to sort
*/
	int i,j,the_min,minpos;
	printf(" SelectSort: ");
	for (i=0;i<anz;i++) {
		the_min=zahlenfeld[i];
		minpos=i;
		for (j=(i+1);j<anz;j++) {
			if (zahlenfeld[j]<the_min) {
				the_min=zahlenfeld[j];
				minpos=j;
			}
		}
		swap_array(i,minpos,zahlenfeld);
	}
}

void bucketsort (int anz, int *zahlenfeld) {
#define maxcounters 1000
/*	BucketSort int array of size anz
	Set up counters for each possible value.
	Run through array and count each value.
	Expand counters to create sorted array.
	anz...size of data in array zahlenfeld (NOT size of array !)
	zahlenfeld...array containing the data to sort
*/
	int i,j,k,min,max,nctr,z;
	int counter[maxcounters];
	printf(" BucketSort: ");
	// Test to find number of counters:
	min=0;max=0;
	for (i=0;i<anz;i++) {
		if (zahlenfeld[i]<min) min=zahlenfeld[i];
		if (zahlenfeld[i]>max) max=zahlenfeld[i];
	}
	nctr=max-min+1;		// number of counters needed
	printf("%d counters verwendet\n",nctr);
	if (nctr<=maxcounters) {
		// Reset counters
		for (i=0;i<nctr;i++) counter[i]=0;
		// count elements
		for (i=0;i<anz;i++) {
			z=zahlenfeld[i]-min;
			counter[zahlenfeld[i]-min]++;
		}
		// expand counters to array
		k=0;
		for (i=0;i<nctr;i++) {
			z=counter[i];
			for (j=0;j<z;j++) {
				zahlenfeld[k++]=i+min;
			}
		}
	}
	else {
		printf(" Zu viele moegliche Zahlenwerte fuer BucketSort\n");
		printf(" Zahlenfeld wird nicht sortiert !\n");
	}
#undef maxcounters
}

void insertsort (int anz, int *zahlenfeld) {
/*	InsertSort int array of size anz
	Sort the first 2 elements of the list.
	Now find the right place for element 3 to insert in this ordered list.
	Then you have a sorted list of 3 elements.
	Do so with elements 3...n
	anz...size of data in array zahlenfeld (NOT size of array !)
	zahlenfeld...array containing the data to sort
*/
	int i,pr,pl,er,el;
	printf(" InsertSort: ");
	// Start with first 2 elements
	if (zahlenfeld[1]<zahlenfeld[0]) swap_array(0,1,zahlenfeld);
	// Get the next element
	for (i=2;i<anz;i++) {
		pr=i;
		pl=pr-1;
		er=zahlenfeld[pr];
		el=zahlenfeld[pl];
		// Insert element
		while ((er<el) && (pl>=0)) {
			swap_array(pr,pl,zahlenfeld);
			er=zahlenfeld[--pr];
			el=zahlenfeld[--pl];
		}
	}

}

void quicksort(int pl, int pr, int *array) {
/*
This code SEEMS to run correctly, but produces erroneous results !!!
Be careful not to use it in critical situations !
Will try to provide a better code in updates.
*/
	int links, rechts, mitte;
	links = pl;
	rechts = pr;
    mitte = int((pl + pr) / 2);      //	Start in the middle
	do {
		for (;array[links] < array[mitte]; links++);	//	Left border
		for (;array[mitte] < array[rechts]; rechts--);	//	Right border
			if (links <= rechts) {
				swap_array(links,rechts,array);
				links++; 
				rechts--;
            }
	}
	while (links <= rechts);
	if (pl < rechts) quicksort(pl, rechts, array);		//	Recursive call (new limits)
	if (links < pr) quicksort(links, pr, array);		//	Recursive call (new limits)
}

void swap_array (int a, int b, int *array) {
	// swap elements a & b of an int array
	int c;
	c=array[a];
	array[a]=array[b];
	array[b]=c;
}