I was trying to sort a massive file of successive chars in C. I did some research and found a few file sorting algorithms that look the same. Their main idea is to read an amount of data to memory, sort them using one of classic sort algorithms, write them to a new file, then repeat the process and merge the two files and so on. You can find more here
I tried to make a new algorithm that does not require a lot of memory. I ended up with this code that actually works and is inspired from Bubble sort algorithm:
#include<stdio.h>
int main()
{
char a,b;
FILE *f,*aux;
int sorted;//BOOLEAN
do
{
f = fopen("ltr.txt","r"); //Assuming that the file exists
aux = fopen("aux.txt","w+");
a = getc(f);
sorted = 1;
while ( (b = getc(f)) != EOF )
{
if (b < a)
{
fputc(b, aux);
sorted = 0;
}
else
{
fputc(a, aux);
a = b;
}
}
fputc(a, aux);
fclose(f);
fclose(aux);
remove("ltr.txt");
rename("aux.txt","ltr.txt");
}while(!sorted);
return 0; //EXIT_SUCCESS
}
The algorithm works but is improvable and can be optimized, however I'm asking for help by reviewing complexity, performance, read/write to disk, disk management, memory management and comparison to other sorting algorithms.
I can list some disadvantages:
- requires disk space of file_size*2 (can be improved by deleting original char each time we write it to aux.txt)
- file will be written to disk several times and the original will be deleted
- execution time looks to be too long (yet I didn't measure it)