/* Author: Ben Miller
*  This is a copy of Sedgewick's shell sort out of his book Algorithms
*  in C.  The program sorts a list up to a million in length.
*/

#include <stdio.h>

void shell (int list[], int N);

int main (int argc, char *argv[]) {

    FILE *infile;
    char unsorted_file[25];
    int list[1000000];
    int number, a;

    /* check command line */
    if (argc != 2) {
	printf ("Error entering correct number of arguements.\n");
	printf ("Enter the name of the unsorted file. ");
	scanf ("%s", unsorted_file);
    } else
	strcpy (unsorted_file, argv[1]);

    /* check if file is equal to null */
    if ((infile = fopen(unsorted_file, "r")) == NULL) {
	printf ("Error opening file: %s.\n", unsorted_file);
	exit (1);
    }

    /* read the file into an array */
    while (fscanf(infile, "%d", &number) != EOF) {
	list[a] = number;
	a++;
    }

    /* sort the array */
    shell (list, a);

    /* close file */
    fclose (infile);

    /* print completed */
    printf ("Completed!! The list has been sorted.\n");

    exit(1);

}

void shell (int a[], int N) {

    int i, j, h, v;

    for (h = 0; h <= N/9; h = 3*(h+1))
    for (0; h > 0; h /= 3)
	for (i = (h+1); i <= N; i +=1) {
	    v = a[i];
	    j = i;
	    while (j > h && a[j-h] > v) {
		a[j] = a[j-h];
		j -= h;
	    }
	    a[j] = v;
	}
    return;
}