Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Blekzet
3 / 3 / 0
Регистрация: 21.12.2015
Сообщений: 173
1

Сортировка слиянием?

17.06.2016, 22:37. Просмотров 311. Ответов 6
Метки нет (Все метки)

Условие задачи "Элементы файлов f1 и f2 упорядочены по не убыванию. Объединить эти элементы в один файл f3, также упорядоченный по не убыванию" предполагает, что данные , которые записаны в файлах, не загружаются в ОП. Условие задачи похоже на СОРТИРОВКУ СЛИЯНИЕМ...
Проблема вот в чем, я чет не могу понять как можно такое реализовать... ну то есть просто как можно такое сделать не нагружая память?

(Брать элементы из файлов, сравнивать, заносить в 3? Я чет реально даже не могу представить)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2016, 22:37
Ответы с готовыми решениями:

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит...

2 сортировки: пирамидальная сортировка и сортировка слиянием
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма...

Шейкерная сортировка + сортировка слиянием
вот часть когда,которая выполняет шейкерную сортировку : для символьного и...

Сортировка слиянием
Здравствуйте, изучая сортировку, в интернете наткнулся на код сортировки...

Сортировка с слиянием
Добрый вечер! Помогите с подсчетом перестановок и сравнений при сортировке с...

6
olya7
494 / 310 / 232
Регистрация: 18.02.2013
Сообщений: 744
17.06.2016, 22:59 2
выгружать по одному из каждого файла, в результирующий файл записывать меньшее из них.. то есть слияние, с выгрузкой по одному элементу, пока не дошли до конца файла
0
Blekzet
3 / 3 / 0
Регистрация: 21.12.2015
Сообщений: 173
17.06.2016, 23:40  [ТС] 3
Хмм... То есть взять первый элемент из первого файла и первый элемент из второго, меньший занести в результат, потом взять (если 1 из 1 был меньшим) второй элемент из первого и первый элемент из второго и т.д.?
0
olya7
494 / 310 / 232
Регистрация: 18.02.2013
Сообщений: 744
17.06.2016, 23:44 4
типа того
0
Blekzet
3 / 3 / 0
Регистрация: 21.12.2015
Сообщений: 173
18.06.2016, 02:01  [ТС] 5
Вот даже не знаю как это сделать, просто не могу понять как играть с позицией указателя текстового файла... Проще говоря, не могу понять как сравнивать, к примеру, второй элемент 1 файла с первым элементом 2-го...
Через fseek нельзя, так как файл текстовый, а не бинарный...
Через fget(set)pos тоже нельзя, так как потом не вернуть к предыдущему значению указателя... (Ну или можно, просто я не могу представить как)
Вот уже прям не знаю...
0
Геомеханик
788 / 595 / 937
Регистрация: 26.06.2015
Сообщений: 1,409
18.06.2016, 20:50 6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <fstream>
#include <sstream>
 
template<typename T>
class reader {
private:
    std::istream* pin;
    T    val;
    bool ok;
public:
    reader(std::istream& _in):pin(&_in), ok(false), val(0){
        ++*this;
    }
    
    reader& operator ++ (void){
        if(((*pin) >> val) && !pin->fail())
            ok = true;
        else
            ok = false;
        return *this;
    }
 
    T& operator *(void) { return val; }
    bool isNext(void) const { return ok; }
};
 
template<typename T>
void merge_stms(std::istream& _in1, std::istream& _in2, std::ostream& _out, char delim = ' '){
    reader<T> st1(_in1);
    reader<T> st2(_in2);
 
    while(st1.isNext() && st2.isNext()){
        if(*st1 < *st2){
            _out << *st1;
            ++st1;
        } else if(*st2 < *st1){
            _out << *st2;
            ++st2;
        } else {
            _out << *st1 << delim << *st2;
            ++st1;
            ++st2;
        }
        _out << delim;
    }
 
    for(; st1.isNext(); ++st1)
        _out << *st1 << delim;
 
    for(; st2.isNext(); ++st2)
        _out << *st2 << delim;
}
 
int main(void){
    char s1[] = "0 2 4 6 8 8.5 9.9 10";
    char s2[] = "-1.3 1 3 5 7 333";
    std::istringstream sp1(s1);
    std::istringstream sp2(s2);
    merge_stms<float>(sp1, sp2, std::cout);
 
/*  работа с файлами
    std::ifstream fin1("input1.txt");
    std::ifstream fin2("input2.txt");
    std::ofstream fout("output.txt");
    merge_stms<int>(fin1, fin2, fout);
    fout.close();
    fin1.close();
    fin2.close();
*/
    return 0;
}
0
avgoor
1041 / 609 / 157
Регистрация: 05.12.2015
Сообщений: 1,732
18.06.2016, 21:32 7
Геомеханик, Чем не устраивает std::merge:
C++
1
2
3
4
5
6
7
8
9
#include <fstream>
#include <iterator>
#include <algorithm>
int main()
{
    std::merge(std::istream_iterator<int>(std::ifstream("file1.txt")), std::istream_iterator<int>(),
        std::istream_iterator<int>(std::ifstream("file2.txt")), std::istream_iterator<int>(),
        std::ostream_iterator<int>(std::ofstream("file3.txt"), " "));
}
0
18.06.2016, 21:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.06.2016, 21:32

Сортировка слиянием
Требуется отсортировать слиянием массив структур. По одному из элемерту...

Сортировка слиянием
Нужно сделать счётчик который будет считать количество приравниваний в...

Сортировка слиянием
Даны два текстовых файла f1.txt и f2.txt, состоящие из целых чисел, которые...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru