отсортировать недосортированный файл

319

30 января 2017, 18:01

здравствуйте, есть файл, который до этого частично сортировывался. частично значит файл состоит, допустим, из такого порядка чисел: 1 2 3 3 5 6 6...max 1 2 2 4 5 5...max и так далее т.е. сортированные числа до определенного максимального, затем опять отсортированные (количество чисел в этих частях одинаковое, но сами числа могут отличаться ) и так до конца файла... помогите пожалуйста отсортировать такой файл. понимаю, что нужно как-то слиянием этих частей, но как...

Answer 1

Вобщем, так.
Если есть возможность считать все это хозяйство в память и сортировать - лучше делать это именно таким образом. Быстрее и проще.
Способ с работой непосредственно в файле - только для учебных целей. Потому что он оказывается тормознутым, особенно при большом количестве серий - так как на каждом шаге нужно искать минимум среди всех серий... Глобально - время работы алгоритма O(Nk), где k - количество серий, так что оно не должно превышать log N, особенно если учесть большую константу за счет большого количества дисковых операций...

Если это реальная работа - возьмите GNU sort и не мучайтесь :)

Ну, а если хочется помучиться - то вот нечто работающее, но написанное, как говорится, на коленке...

#include <vector>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <limits>
#include <algorithm>
using namespace std;
void makeFile()
{
    ofstream out("data");
    for(int i = 0; i < 30; ++i)
    {
        int curval = rand()%100;
        for(int j = 0; j < 10000+rand()%100; ++j)
        {
            out << curval << "\n";
            curval += rand()%100;
        }
    }
}
struct Getter
{
    streamoff pos;
    int       val;
};
int main(int argc, const char * argv[])
{
    makeFile();
    vector<Getter> ps;
    ifstream in("data");
    int last = numeric_limits<int>::max(), val;
    while(in >> val)
    {
        if (val >= last)
        {
            last = val;
            continue;
        }
        last = val;
        Getter g{in.tellg(), val};
        ps.push_back(g);
    }
    in.clear();
    in.seekg(0);
    ofstream out("sort");
    for(;ps.size();)
    {
        auto g = min_element(ps.begin(), ps.end(),
                             [](const Getter&g1, const Getter&g2) { return g1.val < g2.val; });
        out << g->val << "\n";
        int x;
        if (in.seekg(g->pos) && (in >> x) && (x >= g->val))
        {
            g->val = x;
            g->pos = in.tellg();
        }
        else
        {
            in.clear();
            ps.erase(g);
        }
    }
}

Answer 2

Вариант:

#include <iostream>
#include <algorithm>
int main () {
  std::vector<int> A = {1,2,2,3,3,5,6,6,12};
  std::vector<int> B = {1,2,2,4,5,5,7};
  std::vector<int> R;
  R.reserve(A.size()+B.size());
  std::merge(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(R));
  for(const auto &i:R) std::cout << i << " ";  
  return 0;        
}