Сортировка файла на месте с помощью Shell sort
Меня попросили отсортировать файл на месте, используя сортировку оболочки (и быструю сортировку, но я думаю, что если я найду способ сделать это, я смогу сделать их оба). Я думал, что может быть полезным, но я не могу найти способ сделать это. У меня есть алгоритм для массива, но я не могу придумать способ заставить его работать с файлом.
Есть ли способ сделать это?
Редактировать:
С помощью кода, опубликованного Андре Пуэлем, я смог написать код, который работает на данный момент, вот он, если вы хотите проверить его:
#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;
}
Решение
Когда вы открываете файл в C ++, у вас есть два указателя. Указатель получения и указатель установки. Они указывают, где в файле вы пишете и читаете.
С помощью seekp, Вы можете сказать, где вы хотите написать. С помощью tellp Вы знаете, где вы собираетесь написать. Каждый раз, когда вы пишете что-либо, указатель клюшки автоматически выдвигается.
То же самое относится и к указателю получения, функции seekg а также tellg.
Используя эти операции, вы можете легко смоделировать массив. Позвольте мне показать вам некоторый код:
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;
}
Это наивный способ иметь дело с файлом, потому что вы предполагаете произвольный доступ. Ну, случайный доступ — это правда, но он может быть медленным. Файловые потоки работают быстрее, когда вы получаете доступ к данным, расположенным рядом (пространственное расположение).
Несмотря на то, что это хороший способ начать заниматься своей проблемой, у вас есть опыт работы с файловым вводом-выводом, и вы в конце концов придумаете способы повысить производительность для вашей конкретной проблемы. Давайте держать шаги ребенка.
Еще одна вещь, на которую я хочу обратить ваше внимание, это то, что когда вы выполняете запись, данные перенаправляются в поток, который будет записывать в файл. Я знаю, что ядро будет пытаться кешировать эти вещи и оптимизировать скорость, но все же было бы лучше, если бы у вас был какой-то слой кеша, чтобы избежать записи непосредственно на диск.
Наконец, я предположил, что вы имеете дело с символами (потому что это будет проще), но вы можете иметь дело с другими типами данных, вам просто нужно быть осторожным с индексированием и размером типа данных. Например, long long type имеет размер 8 байт, если вы хотите получить доступ к первому элементу в вашем Файл-массив Вы получите доступ к позиции 8 * 0, и вам нужно будет прочитать 8 байтов. Если вы хотите 10-й элемент, вы получите доступ к позиции 8 * 10 и снова прочитаете 8 байтов данных, чтобы построить long long значение.
Другие решения
Других решений пока нет …