Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Blekzet
3 / 3 / 0
Регистрация: 21.12.2015
Сообщений: 173
#1

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

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

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

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

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include <iostream> ...

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

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

Сортировка слиянием - C++
Нужен алгоритм сортировки массива слиянием. Массив из 1000 чисел, введенных рандомно. На visual c++ заранее большое спасибо.

Сортировка слиянием - C++
Всем доброго время суток, дана задача: Требуется упорядочить элементы некоторого массива целых чисел, который следует упорядочить по...

сортировка слиянием - C++
программа должна выполнять сортировку строк слиянием с использованием указателей. #include<iostream> #include<string.h> ...

6
olya7
489 / 306 / 92
Регистрация: 18.02.2013
Сообщений: 738
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
489 / 306 / 92
Регистрация: 18.02.2013
Сообщений: 738
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
Геомеханик
769 / 575 / 400
Регистрация: 26.06.2015
Сообщений: 1,373
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
967 / 601 / 130
Регистрация: 05.12.2015
Сообщений: 1,686
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
Привет! Вот еще темы с ответами:

Сортировка слиянием - C++
Всем привет.Требуется сортировка слиянием, для проверки скорости нескольких сортировок. Желательно,чтобы код был простой.

Сортировка слиянием - C++
На лабороторной задали написать сортировку массива слиянием, рабочую версию реализовать удалось, только вот она жрёт лишнюю память, которая...

Сортировка с слиянием - C++
Добрый вечер! Помогите с подсчетом перестановок и сравнений при сортировке с слиянием. Вот нашел код, и ищу легкий способ чтоб посчитать,...

Сортировка слиянием в С++ - C++
Вот такое задание: Составить программу реализации указанного метода сортировки и иллюстрации его выполнения. В программе предусмотреть...


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

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

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