#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

void bubble(char *items, int count);
void shaker(char *items, int count);
void shell(char *items, int count);

int main(void)
{
	FILE *fp;
	FILE *s1;
	FILE *s2;
	FILE *s3;
	char s[255];
	time_t start, end;
	volatile long unsigned t;

	printf("read file");

	if((fp = fopen("mass.txt", "r")) == NULL) {
		printf(" : error.\n");
		exit(1);
	}

	printf(" : ok.\n\n");

	while(!feof(fp)) {
		fgets(s, 253, fp);
	}

	start = time(NULL);
	bubble(s, strlen(s));
	end = time(NULL);
	s1 = fopen("bubble.txt", "w");
	fputs(s, s1);
	printf("Bubble sort : ok.\n");
	printf("time: %f s.\n\n", difftime(end, start));

	start = time(NULL);
	shaker(s, strlen(s));
	end = time(NULL);
	s2 = fopen("shaker.txt", "w");
	fputs(s, s2);
	printf("Cocktail shaker sort : ok.\n");
	printf("time: %f s.\n\n", difftime(end, start));

	start = time(NULL);
	shaker(s, strlen(s));
	end = time(NULL);
	s3 = fopen("shell.txt", "w");
	fputs(s, s3);
	printf("Donald Lewis Shell sort : ok.\n");
	printf("time: %f s.\n\n", difftime(end, start));

	fclose(fp);
	fclose(s1);
	fclose(s2);
	fclose(s3);
	return 0;
}

// bubble sort
void bubble(char *items, int count)
{
	register int a, b;
	register char t;

	for(a = 1; a < count; ++a)
		for(b = count-1; b >= a; --b) {
			if(items[b-1] > items[b]) {
				t = items[b-1];
				items[b-1] = items[b];
				items[b] = t;
			}
		}
}

// cocktail shaker sort
void shaker(char *items, int count)
{
	register int a;
	int exchange;
	char t;

	do{
		exchange = 0;
		for(a = count-1; a >0; --a) {
			if(items[a-1] > items[a]) {
				t = items[a-1];
				items[a-1] = items[a];
				items[a] = t;
				exchange = 1;
			}
		}

		for(a = 1; a < count; ++a) {
			if(items[a-1] > items[a]) {
				t = items[a-1];
				items[a-1] = items[a];
				items[a] = t;
				exchange = 1;
			}
		}
	} while(exchange);
}

// Donald Lewis Shell sort
void shell(char *items, int count)
{
	register int i, j, gap, k;
	char x, a[5];

	a[0] = 9; a[1] = 5; a[2] = 3; a[3] = 2; a[4] = 1;

	for(k = 0; k < 5; k++) {
		gap = a[k];
		for(i = gap; i < count; ++i) {
			x = items[i];
			for(j=i-gap; (x < items[j]) && (j >= 0); j = j-gap)
				items[j+gap] = items[j];
			items[j+gap] = x;
		}
	}
}