CODEWITHSUNDEEP
algorithmperformancesortingtimequicksort
user10080061
user10080061

Reputation:

Sorting with low memory size

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)

Upvotes: 0

Views: 2897

Answers (2)

Jaco Van Niekerk
Jaco Van Niekerk

Reputation: 4182

If you can't fit it all in memory, a file-based merge sort will work well.

Upvotes: 2

OmG
OmG

Reputation: 18838

In-place algorithms are your solution. Find more here:

As another example, many sorting algorithms rearrange arrays into sorted order in-place, including bubble sort, comb sort, selection sort, insertion sort, heapsort, and Shell sort. These algorithms require only a few pointers, so their space complexity is O(log n).

Upvotes: 0

Related Questions