/***********************************************************************/
/* Author: Ben Miller                                                  */
/* Purpose: sorts a list of numbers in increasing order                */
/* Input:                                                              */
/*   data: an unsorted array of numbers                                */
/*   begin: the beginning index of "data"                              */
/*   end: the final index of "data"                                    */
/* Output:                                                             */
/*   upon termination of the subroutine, "data" contains the sorted    */
/*     list of numbers                                                 */
/***********************************************************************/

#include <stdio.h>

#define NAME_LENGTH 20
#define FILE_LENGTH 1000000

void quicksort(int *data, int begin, int end);

int main(int argc, char *argv[])
{
	FILE *infile;
	char unsorted_file[NAME_LENGTH];
	int begin = 0, end = FILE_LENGTH, data[1000000];
	int number, i;

	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]);

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

	/* read unsorted file */
	while (fscanf(infile, "%d", &number) != EOF) {
                data[i] = number;
		i++;
	}

	/* sort list */
	quicksort(data, begin, end);

	fclose(infile);

	printf("Done!!\n");
	exit();
}

void quicksort(int *data, int begin, int end) {

	int leftarrow, rightarrow;
	float temp, pivot;

	leftarrow = begin;
	rightarrow = end;
	pivot = data[(begin+end)/2];
	while (1) {
		while (data[rightarrow] > pivot)
		  rightarrow = rightarrow - 1;

		while (data[leftarrow] < pivot)
		  leftarrow = leftarrow + 1;

		if (leftarrow <= rightarrow) {
		  temp = data[leftarrow];
		  data[leftarrow] = data[rightarrow];
		  data[rightarrow] = temp;
		  leftarrow = leftarrow + 1;
		  rightarrow = rightarrow - 1;
		}

		if (rightarrow < leftarrow)
		  break;
	} 

	if (begin < rightarrow)
	  quicksort(data, begin, rightarrow);
	if (leftarrow < end)
	  quicksort(data, leftarrow, end);

	return;
}