Sorting a file in-place with Shell sort

Question

I have been asked to sort a file in-place using shell sort (and quick sort too, but I think that if I find the way to do one I will be able to do both of them). I have been thinking what could be helpful but I can't find a way to do it. I have the algorithm for an array, but I can't think a way to get it to work with a file.

Is there any way this can be done?

Edit:

With the help of the code posted by André Puel I was able to write some code that is working for the moment, here it is if you want to check it out:

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <sstream>
using namespace std;

int toNum(const string &s) {
  stringstream ss(s);
  int n;
  ss >> n;
  return n;
}

string toStr(int n) {
  stringstream ss;
  ss << n;
  string s;
  ss >> s;
  return string(5 - s.size(),' ') + s;
}

int getNum(fstream &f,int pos) {
  f.seekg(pos*5);
  string s;
  for(int i = 0; i < 5; ++i) s += f.get();
  return toNum(s);
}

void putNum(fstream &f, int pos,int n) {
  f.seekp(pos*5);
  f.write(toStr(n).c_str(),5);
}

int main() {
  fstream input("entrada1",fstream::in | fstream::out);
  string aux;
  getline(input,aux);
  int n = aux.size() / 5,temp,j;

  int gaps[] = {701,301,132,57,23,10,4,1};
  int g = sizeof(gaps)/sizeof(gaps[0]);
  for(int k = 0; k < g; ++k) {
    for(int i = k; i < n; ++i) {
      temp = getNum(input,i);
      for(j = i; j >= k and getNum(input,j - k) > temp; j -= k) {
        putNum(input,j,getNum(input,j - k));
      }
      putNum(input,j,temp);
    }
  }
  input.close();
  return 0;
}

Answer 1

When you open a file in C++ you have two pointers. The getter pointer and the putter pointer. They indicate where in the file you are writing and reading.

Using seekp, you may tell where you wanna write. Using tellp you know where you are going to write. Everytime you write something the putter pointer advances automatically.

The same goes to the getter pointer, the functions are seekg and tellg.

Using theses operations you may easily simulate an array. Let me show you some code:

class FileArray {
public:
    FileArray(const char* path) 
    : file(path, std::fstream::app|std::fstream::binary)
    {
        file.seekg(0,std::fstream::end);
        size = file.tellg();
    }

    void write(unsigned pos, char data) {
        assert(pos < size );
        file.tellp(pos);
        file.put(data);
    }

    char read(unsigned pos) {
        assert(pos < size);
        file.seekg(pos);
        return file.get();
    }
private:
    std::fstream file;
    std::size_t size;
}

This is a naive way to deal with a file because you are supposing random access. Well, random access is true, but it may be slow. File streams works faster when you access data that are near each other (spacial locality).

Even though, it is a nice way to start dealing with your problem, you with get experienced with file IO and you will end figuring out ways to improve the performance for your specific problem. Lets keep the baby steps.

Other thing that I want you to note is that when you perform a write, the data is redirected to the fstream that will write to the file. I know that the kernel will try to cache this stuff, and optimize the speed, but still would be better if you had some kind of cache layer to avoid writing directly to the disk.

Finally, I supposed that you are dealing with chars (because it would be easier), but you can deal with other data types, you will just need to be careful about the indexing and the size of the data type. For example, long long type does have size of 8 bytes, if you want to access the first element in your file-array you will access the position 8*0, and you will have to read 8 bytes. If you want the 10th element, you will access the position 8*10 and again read 8 bytes of data to construct the long long value.