2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Внешняя сортировка прямым слиянием
Сообщение23.04.2022, 16:20 


24/01/22
61
Никак не получается обрабатывать серии.

Например исходный файл f содержит числа: 1, 2, 3, 100, 4. А длина текущей серии - 3;
Тогда f разобьется на файлы f1: 1, 2, 3 - и f2: 100, 4.
И вот никак у меня не получается правильно сделать слияние двух файлов, если в одном из них не полная серия.

код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
//слияние
    for var i := 1 to min(n1 div n, n2 div n) do
    begin
      count1 := 0;
      while count1 < n do
      begin
        read(f1, a);
        read(f2, b);
        c1 := min(a, b);
        c2 := max(a, b);
        write(ouf, ' ', c1, ' ', c2);
        count1 += 1;
      end;
    end;
   
    flag1 := true;
    flag2 := true;
    while (not eof(f2)) and (not eof(f1)) do
    begin
      if flag1 and flag2 then
      begin
        read(f2, b);
        read(f1, a);
        if a < b then
        begin
          write(ouf, ' ', a);
          flag2 := false;
        end
        else
        begin
          write(ouf, ' ', a);
          flag1 := false;
        end;
      end
      else
        if not flag2 then
        begin
          read(f1, a);
          if a < b then
            write(ouf, ' ', a)
          else
          begin
            flag2 := true;
            flag1 := false;
            write(ouf, ' ', b)
          end;
        end
        else
          if not flag1 then
          begin
            read(f1, b);
            if b < a then
              write(ouf, ' ', b)
            else
            begin
              flag1 := true;
              flag2 := false;
              write(ouf, ' ', a);
            end;
          end;
    end;
   
    if not eof(f1) then
      while not eof(f1) do
      begin
        read(f1, a);
        write(ouf, ' ', a);
      end
    else
      if not eof(f2) then
        while not eof(f2) do
        begin
          read(f2, b);
          write(ouf, ' ', b);
        end;
 


-- 23.04.2022, 16:21 --

n1 и n2 - это число элементов в файлах f1 и f2, n - длина текущей серии.

-- 23.04.2022, 16:34 --

Сейчас если воспользоваться этим алгоритмом для сортировки файла 1, 2, 3, 100, 4, то получится 1, 2, 3, 4. И я даже знаю, где ошибка - она заключается в том, что в переменную b уже записано значение 100, а здесь я не вывожу его, а сразу считываю следующее. Но никак не могу это исправить, и вообще мне кажется, что можно проще сделать.

Используется синтаксис Pascal
if not eof(f1) then
      while not eof(f1) do
      begin
        read(f1, a);
        write(ouf, ' ', a);
      end
    else
      if not eof(f2) then
        while not eof(f2) do
        begin
          read(f2, b);
          write(ouf, ' ', b);
        end;
 

 Профиль  
                  
 
 Re: Внешняя сортировка прямым слиянием
Сообщение23.04.2022, 18:41 
Заслуженный участник
Аватара пользователя


16/07/14
8632
Цюрих
Тут проблема не в неполноте серии, а в том, что после цикла неизвестно - считано ли хоть одно значение из например первого файла, или нет. Без флагов "в a лежит действительно считанное значение" и аналогичного для b это поправить вряд ли удастся.
С ними зато получится без лишних циклов в конце: сначала всё инициализируем, потом, если оба флага установлены - сравниваем значения и выясняем, что выводить и откуда читать дальше, иначе просто читаем из того файла, флаг которого установлен. Ну и цикл идет до тех пор, пока хотя бы один из файлов установлен.

Первый цикл делает что-то невнятное (выводит минимум/максимум по каждой строке), нигде в слиянии ничего подобного не нужено.
XeuTeP_KoLLIu в сообщении #1553288 писал(а):
Тогда f разобьется на файлы f1: 1, 2, 3 - и f2: 100, 4.
После разбиения и перед слиянием нужно каждый файл отсортировать отдельно.

 Профиль  
                  
 
 Re: Внешняя сортировка прямым слиянием
Сообщение23.04.2022, 19:11 


24/01/22
61
У меня элементы сортируются при слиянии. Берется пара элементов из f1 и f2 и записывается в порядке возрастания в f.

 Профиль  
                  
 
 Re: Внешняя сортировка прямым слиянием
Сообщение23.04.2022, 20:03 
Аватара пользователя


28/10/21
99
XeuTeP_KoLLIu в сообщении #1553298 писал(а):
У меня элементы сортируются при слиянии. Берется пара элементов из f1 и f2 и записывается в порядке возрастания в f.


Так а какой алгоритм внешней сортировки вы пытаетесь реализовать?

Вы пишете: "Берется пара элементов ... и записывается в порядке возрастания." И что дальше? Что дает такая "попарная" сортировка в рамках всего алгоритма?

 Профиль  
                  
 
 Re: Внешняя сортировка прямым слиянием
Сообщение23.04.2022, 22:07 


24/01/22
61
Сначала обрабатываются полные серии. Берутся серии файлов f1 и f2 с одинаковыми номерами и их элементы записываются в порядке возрастания в f. Если получилось так, что в одном из файлов серия закончилась, а в другом нет, то элементы из серии этого файла просто записываются подряд в f (так можно делать потому что элементы в серии уже упорядочены). Затем записываются неполные серии (только шаг серии будет x2 а не +1, как у меня написано в заголовке). Тоже самое, что и с полными сериями, только элементы обрабатываются уже до конца файлов.

-- 23.04.2022, 22:58 --

можете не отвечать, я уже сам разобрался, всем спасибо

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group