What is the best way to sort a dictionary with 1Gbyte size(255 char for each word) with 2G of RAM? I have already tried quicksort and didn't get the acceptable result. This the quicksort code:
#include <iostream>
#include <fstream>
#include <cstring>
#define MAXL 4000000
using namespace std;
void swap(char *&ch1,char *&ch2)
{
char *temp = ch1;
ch1 = ch2;
ch2 = temp;
}
int partition (char **arr, int low, int high)
{
string pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(char **arr, int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main()
{
fstream file("input.txt",ios::in|ios::out|ios::app);
fstream o("output.txt",ios::out);
char **arr = new char*[MAXL];
for(int i=0;i<MAXL;i++)
arr[i] = new char[255];
long long i=0;
while(file)
{
//words are sepearated by spcae
file.getline(arr[i],256,' ');
i++;
}
file.close();
quickSort(arr, 0, i-2);
for(long long j=0;j<i-1;j++)
{
o << arr[j] << "\n";
}
}
It takes more than 10 minutes to sort the mentioned list but it shouldn't take more than 20 seconds. (MAXL is the number of words in the 1G file and input words are stored in a text file)
