1

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

4
  • Просто используете несколько указателей. Считали по одному значению, записали минимальное, сместили соответствующий указатель, считали новое значение. И так, пока все значения не будут записаны...
    – Harry
    29 янв 2017 в 12:08
  • @Harry, издеваешься?)) Есть же STL)
    – Majestio
    29 янв 2017 в 12:29
  • @Majestio Ну, лично я воспринял это как учебное задание. Тем более что речь идет о файле, так что если файл большой, то всасывать все в память может быть очень проблематично. И еще вдогонку - merge для двух диапазонов, - а сколько их в файле? Сказано, что много.
    – Harry
    29 янв 2017 в 12:37
  • @Harry, ааа ... ну тогда только строго "пузырек". Потому как файл может быть таким большим, что второй той же длины уже на носитель не поместиться)
    – Majestio
    29 янв 2017 в 13:03

2 ответа 2

2

Вобщем, так.
Если есть возможность считать все это хозяйство в память и сортировать - лучше делать это именно таким образом. Быстрее и проще.
Способ с работой непосредственно в файле - только для учебных целей. Потому что он оказывается тормознутым, особенно при большом количестве серий - так как на каждом шаге нужно искать минимум среди всех серий... Глобально - время работы алгоритма 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);
        }
    }
}
3
  • спасибо, буду въезжать
    – xperious
    29 янв 2017 в 16:21
  • Ну, я реализовал то, что говорил в комментарии - о поддержании в одном файле пачки указателей на отсортированные куски...
    – Harry
    29 янв 2017 в 16:40
  • спасибо за идею о том, что можно создать доп. структуру с позицией и значением... очень красивая и годная идея имхо
    – xperious
    29 янв 2017 в 16:47
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;        
}

Вывод:

1 1 2 2 2 2 3 3 4 5 5 5 6 6 7 12

На ideone.

8
  • спасибо, только вот сначало нужно весь файл обойти и образовать эти самые вектора A,B и так далее. дальше уже в выходной вектор... это, выходит, двухкратное использование памяти по сравнению с размером файла... можно ли как то поэффективнее?
    – xperious
    29 янв 2017 в 12:50
  • к тому же если векторов этак 50 то как сделать? я не въезжаю чет
    – xperious
    29 янв 2017 в 13:03
  • Используйте "пузырек". А если таких "векторов" 5000000? Какие накладные расходы будут на индексацию?
    – Majestio
    29 янв 2017 в 13:04
  • не совсем понял: в каком месте пузырьком пользоваться?
    – xperious
    29 янв 2017 в 13:15
  • Ну если файл большой, ресурсов мало, групп в файле много - сортировать весь файл пузырьком, и делов то.
    – Majestio
    29 янв 2017 в 13:33

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.