2014 dxdy logo

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

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




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

Например исходный файл 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 
Аватара пользователя
Тут проблема не в неполноте серии, а в том, что после цикла неизвестно - считано ли хоть одно значение из например первого файла, или нет. Без флагов "в a лежит действительно считанное значение" и аналогичного для b это поправить вряд ли удастся.
С ними зато получится без лишних циклов в конце: сначала всё инициализируем, потом, если оба флага установлены - сравниваем значения и выясняем, что выводить и откуда читать дальше, иначе просто читаем из того файла, флаг которого установлен. Ну и цикл идет до тех пор, пока хотя бы один из файлов установлен.

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

 
 
 
 Re: Внешняя сортировка прямым слиянием
Сообщение23.04.2022, 19:11 
У меня элементы сортируются при слиянии. Берется пара элементов из f1 и f2 и записывается в порядке возрастания в f.

 
 
 
 Re: Внешняя сортировка прямым слиянием
Сообщение23.04.2022, 20:03 
Аватара пользователя
XeuTeP_KoLLIu в сообщении #1553298 писал(а):
У меня элементы сортируются при слиянии. Берется пара элементов из f1 и f2 и записывается в порядке возрастания в f.


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

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

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

-- 23.04.2022, 22:58 --

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group