CODEWITHSUNDEEP
c++sorting
malhobayyeb
malhobayyeb

Reputation: 2873

How do I sort a file that has a very long list of items?

I have a text file that has a very long list of items. So I want to sort them alphabetically but I do not want to load all the file into the memory (RAM).

I tried loading all the contents of the file to an array and sort them just like I do normally. But the system complains that there are no much memory!!

Thanks, Mohammad

Upvotes: 7

Views: 1372

Answers (4)

Klark
Klark

Reputation: 8280

If you are using some unix-like OS you can use sort command. It will take care about memory consumption. For an example something like "cat large_file | sort" will do the job.

Or you can write your own / use external sorting from the library. Tell us what language are you using and maybe someone will tell you exact library to use.

Upvotes: 0

Martijn Courteaux
Martijn Courteaux

Reputation: 68847

You don't have to hold the whole file in memory. If this is a task you don't have to do very often, you can write an application that sorts it very slow. Something like this (pseudo):

vector<int> linesProcessed;
for (int i = 0; i < lineCount; i++)
{
   if (linesProcessed contains i) continue;
   string alphabeticalFirstLine;
   int lineIndex;
   foreach line in oldFile
   {
       if (line is before alphabeticalFirstLine)
       {
            alphabeticalFirstLine = line;
            lineIndex = i;
       }
   }
   write alphabeticalFirstLine to newFile;
   vector.add(lineIndex);
}
clear vector;
delete oldFile;
rename newFile to oldFile;

Upvotes: 0

stephan
stephan

Reputation: 10265

Maybe the STXXL (Standard Template Library for Extra Large Data Sets) helps.

STXXL offers external sorting amongst others.

Upvotes: 4

Jason S
Jason S

Reputation: 189626

You'll need to read up on external sorting. The basic approach is to use some sort of divide-and-conquer routine like merge sort, where you read and sort a portion of the file, then read and sort another portion of the file, etc. and when you get to the end you merge the sorted portions together.

Upvotes: 7

Related Questions