#include <fstream.h>
#include <string.h>

const int MAX_LENGTH = 35;
typedef char string[MAX_LENGTH];

int swapCount = 0;
int partCount = 0;
int sortCount = 0;
string lines[10];

void Swap(string& X, string& Y) {
	string temp;
	strcpy(temp, X);
	strcpy(X, Y);
	strcpy(Y, temp);
	swapCount++;
}

void ChoosePivot(string A[], int F, int L) {
	int M = (F + L) / 2;
	if ( strcmp(A[F], A[M]) > 0 )
		Swap(A[F], A[M]);
	if ( strcmp(A[M], A[L]) > 0 )
		Swap(A[M], A[L]);
}

void Partition(string A[], int F, int L, int& iPivot) {
	ChoosePivot(A, F, L);
	string sPivot = "";
	strcpy(sPivot, A[F]);
	int LastS1 = F;
	int FirstUnknown = F + 1;
	for (; FirstUnknown<=L; FirstUnknown++) {
		if ( strcmp(A[FirstUnknown], sPivot) < 0 ) {
			LastS1++;
			Swap(A[FirstUnknown], A[LastS1]);
		}
	}
	Swap(A[F], A[LastS1]);
	iPivot = LastS1;
	partCount++;
}

void QuickSort(string A[], int F, int L) {
	int Pivot;

	if ( F<L ) {
		Partition(A, F, L, Pivot);
		QuickSort(A, F, Pivot-1);
		QuickSort(A, Pivot+1, L);
	}

	sortCount++;
}

void main() {
	int index = 0;
	int line = 0;

	ifstream InFile("otherSorts.txt");
	while ( InFile.peek() != EOF ) {
		InFile.getline(lines[line++], MAX_LENGTH);
	}
	InFile.close();
	QuickSort(lines, 0, line-1);
	ofstream OutFile("9.txt");
	for (int i=0; i<10; i++) {
		OutFile << lines[i] << "\n";
	}
	OutFile << "\nSwap Count = " << swapCount;
	OutFile << "\nPart Count = " << partCount;
	OutFile << "\nSort Count = " << sortCount;
	OutFile.close();
}