Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.52/21: Рейтинг темы: голосов - 21, средняя оценка - 4.52
1 / 1 / 0
Регистрация: 02.05.2015
Сообщений: 105

Внешняя сортировка с слиянием

24.04.2019, 16:58. Показов 4293. Ответов 4

Студворк — интернет-сервис помощи студентам
Сначала считываются первые 4 числа, из них какое-то записывается в 5 файл, потом считываем следующее число из файла, в котором был минимальный, и вновь выбираем наименьшее из 4 чисел, где 3 числа останутся теми же, а 1 будет новое.

(2) Потом из 5 файла числа распределяются по 4 файлам, и сливаются заново. Каждый раз длина отрезка упорядоченных чисел увеличивается.
Проблемы:
- не происходит запись в 5 файл;
- не понял, как сделать (2)
Код функции
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
void sort(vector<fstream*> &files) {
 //minNumberArr(numbers, position) - возвращает наименьшее число, position - позиция числа
 
    int numbers[4], minNumber,  position;
 
    for (int i = 0; i < 4; i++) {
        *files[i] >> numbers[i];
    }
    minNumber = minNumberArr(numbers, position);
    *files[4] << minNumber;
    
 
    //пока хоть один из 4х файлов не закончился
    while (isNotEofAny(files))
    {
        if (!files[position]->eof()) { //если файл с мин. числом не закончился
            *files[position] >> numbers[position]; // считываем следующее число из файла с наименьшим;
            //для отладки
            minNumber = minNumberArr(numbers, position);
            cout << minNumber;
            //записываем в пятый файл
            *files[4] << minNumber;
        }
        // если файл закончился, но элемент минимальный
        else {
            for (int i = 0; i < 4; i++) {
                if (!files[i]->eof()) *files[i] >> numbers[i];//пропускаем все завершившиеся
            }
        }
        
    }
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
24.04.2019, 16:58
Ответы с готовыми решениями:

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

Сортировка Слиянием vs Быстрая Сортировка - что лучше
Народ, помогите разобраться какой из методов сортировки лучше &quot;Сортировка Слиянием&quot; или &quot;Быстрая Сортировка&quot;: у быстрой...

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

4
863 / 513 / 215
Регистрация: 19.01.2019
Сообщений: 1,216
24.04.2019, 17:13
https://github.com/nalbe/PasswdParser
Там то, что вам надо: внешняя сортировка + мердж.
0
1 / 1 / 0
Регистрация: 02.05.2015
Сообщений: 105
24.04.2019, 17:24  [ТС]
Цитата Сообщение от nalbe666 Посмотреть сообщение
внешняя сортировка
Не совсем понял, где конкретно внешняя сортировка.
0
863 / 513 / 215
Регистрация: 19.01.2019
Сообщений: 1,216
24.04.2019, 17:54
Если файлы небольшие, читайте их все, складывайте в контейнер типа set. Оно само там пропесочится, остаётся только слить в итоговый файл. Если файлы массивные, то считывайте сколько сможете в тот же set, сливайте во временные файлы. А потом читаете по строке из каждого временного, например в map, где key это строка, value это индекс файла из которого пришла эта строка. Выпихиваете наименьшую строку в итоговый файл, и так по кругу.
0
1 / 1 / 0
Регистрация: 02.05.2015
Сообщений: 105
24.04.2019, 18:19  [ТС]
Цитата Сообщение от nalbe666 Посмотреть сообщение
А потом читаете по строке из каждого временного, например в map, где key это строка, value это индекс файла из которого пришла эта строка. Выпихиваете наименьшую строку в итоговый файл, и так по кругу.
Какое отношение имеют словари к внешней сортировке чисел?
Цитата Сообщение от nalbe666 Посмотреть сообщение
Если файлы небольшие, читайте их все, складывайте в контейнер типа set. Оно само там пропесочится, остаётся только слить в итоговый файл. Если файлы массивные, то считывайте сколько сможете в тот же set, сливайте во временные файлы.
Есть только 5 файлов без всяких временных.
Необходимо слить в 5 файл из 4'х, на каждом из n шагов происходит сортировка в 5 файл по описанному в начале темы алгоритму, между шагами происходит перезалив из 5 файла в 4 остальных. На каждом новом шаге длина упорядоченной последовательности увеличивается, в конце - будут записаны все числа по-возрастанию.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
24.04.2019, 18:19
Помогаю со студенческими работами здесь

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

Внешняя сортировка
Подскажите, как реализовать внещную сортировку массива?

Внешняя сортировка
Здравствуйте!) Прочёл статью на хабре (https://habrahabr.ru/post/268535/) про внешнюю сортировку. Хотелось бы узнать насколько вообще...

Внешняя сортировка
Подскажите, если не сложно как лучше реализовать внешнюю сортировку с 10 файлами для чисел?

Внешняя сортировка
Здравствуйте, уважаемые форумчане! Есть несколько вопросов по заданию моей курсовой. Надеюсь получить советы/помощь от Вас. Собственно...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Киев стоит - украинская песня
zorxor 28.01.2026
wfWdiRqdTxc О Господи, Вечный, Ты . . . Я помоги, Бесконечный. . . Я прошу Ты. . . Я погибаю, спаси. . . Я прошу Тебя Вечный. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru