// quicksort for files
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
const int maxStringSize = 1024;
int compareElements(char* a, char* b)
{
return strcmp (a, b);
}
int getValue(FILE* tmp, int n)
{
int pos = 0;
fseek(tmp, n * sizeof(int), SEEK_SET);
fread(&pos, sizeof(int), 1, tmp);
return pos;
}
void setValue(FILE* tmp, int n, int pos)
{
fseek(tmp, n * sizeof(int), SEEK_SET);
fwrite(&pos, sizeof(int), 1, tmp);
}
char* loadString(FILE* input, int pos, char* str)
{
fseek(input, pos, SEEK_SET);
fgets(str, maxStringSize, input);
return str;
}
// 2 KB
char midValue[maxStringSize];
char tmpValue[maxStringSize];
void quickSort(FILE* tmp, FILE* input, int start, int end)
{
int mid = (start + end) / 2;
loadString(input, getValue(tmp, mid), midValue);
int tmpPos = 0;
int i = start, j = end;
while (i <= j) {
while (compareElements( loadString(input, getValue(tmp, i), tmpValue), midValue ) < 0) {
i++;
}
while (compareElements( loadString(input, getValue(tmp, j), tmpValue), midValue ) > 0) {
j--;
}
if (i <= j) {
tmpPos = getValue(tmp, i);
setValue(tmp, i, getValue(tmp, j));
setValue(tmp, j, tmpPos);
i++;
j--;
}
}
if (start < j) {
quickSort(tmp, input, start, j);
}
if (i < end) {
quickSort(tmp, input, i, end);
}
}
const char *inputFileName = "input.txt";
const char *outputFileName = "output.txt";
const char *tmpFileName = "tmp.bin";
int prepareSort(FILE* tmp, FILE* input)
{
char s[maxStringSize];
int pos = 0;
int N = 0;
fseek(tmp, 0, SEEK_SET);
fseek(input, 0, SEEK_SET);
while (!feof(input)) {
fgets(s, maxStringSize, input);
if (feof(input)) break;
fwrite(&pos, sizeof(int), 1, tmp);
pos = ftell(input);
N++;
}
fseek(tmp, 0, SEEK_SET);
fseek(input, 0, SEEK_SET);
return N;
}
void saveStringsAfterSort(FILE* input, FILE* output, FILE* tmp)
{
fseek(input, 0, SEEK_SET);
fseek(tmp, 0, SEEK_SET);
char str[maxStringSize];
int pos = 0;
while (!feof(tmp)) {
fread(&pos, sizeof (int), 1, tmp);
if (feof(tmp)) break;
loadString(input, pos, str);
fputs(str, output);
}
}
void runFileSort()
{
FILE* input = fopen(inputFileName, "r");
FILE* output = fopen(outputFileName, "w");
FILE* tmp = fopen(tmpFileName, "wb+");
int N = prepareSort(tmp, input);
quickSort(tmp, input, 0, N - 1);
saveStringsAfterSort(input, output, tmp);
fclose(tmp);
fclose(output);
fclose(input);
}
void prepareTestFiles(int N)
{
const char* symbols = "0123456789abcdefghijklmnopqrstuvwxyz";
srand(time(NULL));
int i, j;
const int maxStringLen = 20;
char str[maxStringLen + 1];
FILE* input = fopen(inputFileName, "w");
for (i = 0; i < N; i++)
{
int sLen = (rand() % maxStringLen) + 1;
str[sLen] = '\0';
for (j = 0; j < sLen; j++) {
str[j] = symbols[rand() % 36];
}
fputs(str, input);
fputs("\n", input);
}
fclose(input);
}
/*
char** loadStringsFromFile(int N, const char* filename)
{
FILE* input = fopen(filename, "r");
char** strings = new char*[N];
for (int i = 0; i < N; i++)
{
strings[i] = new char[1024];
fgets(strings[i], 1024, input);
strings[i][strlen(strings[i]) - 1] = '\0';
}
fclose (input);
return strings;
}
int getTime ()
{
struct timeval tp;
gettimeofday(&tp, NULL);
long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;
return ms;
}
static int compareStrings(const void* a, const void* b)
{
return strcmp(*(const char **)a, *(const char **)b);
}
void checkSorting(int N, int dt)
{
char** strings = loadStringsFromFile(N, inputFileName);
int i;
char* systemSortedStrings[N];
for (i = 0; i < N; i++) {
systemSortedStrings[i] = strings[i];
}
qsort(systemSortedStrings, N, sizeof(const char *), compareStrings);
char** quickSortSortedStrings = loadStringsFromFile(N, outputFileName);
printf ("\n");
printf ("quickSort\n");
for (i = 0; i < N; i++) {
if (strcmp(quickSortSortedStrings[i], systemSortedStrings[i]) != 0) {
printf("ERROR: incorrect sorting\n");
break;
}
}
if (i == N) {
printf("correct sorting\n");
}
printf("%d ms / %d elements\n", dt, N);
delete[] strings;
delete[] quickSortSortedStrings;
}
*/
int main ()
{
const int N = 1000;
prepareTestFiles(N);
// int t1, t2;
// t1 = getTime();
runFileSort();
// t2 = getTime();
// checkSorting(N, t2 - t1);
return 0;
}
