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

Рейтинг: 1Ответов: 1Опубликовано: 05.11.2014

Здравствуйте.

Подскажите, пожалуйста, как исправить данный код.
Ошибка в том, что каждый раз обрезается по 2 последних значения при записи в исходный файл (как я понял). Дело в том, что внутри while оно считывает последнее значение из файла, а потом условие eof(f1) (или f2) становится true, и происходит недозапись.
Возможно, я неправильно нашел ошибку, но вроде бы так. Дебажу уже третий час и не могу понять, как исправить.

    while (not EOF(f1))and (not EOF(f2)) do
    begin
      i:=0;
      j:=0;
      while (i<series) and(j<series) and (not eof(f1)) and (not eof(f2)) do
      begin
        if tmp1<tmp2 then
        begin
          write(f,tmp1);
          read(f1,tmp1);
          inc(i);
          inc(count);//--
        end
        else
        begin
          write(f,tmp2);
          read(f2,tmp2);
          inc(j);
          inc(count);//--
        end;
      end;

      while (i<series) and (not eof(f1)) do   //55
      begin
        write(f,tmp1);
        read(f1,tmp1);
        inc(i);
        inc(count);//--
      end;

      while (j<series) and (not eof(f2)) do   //55
      begin
        write(f,tmp2);
        read(f2,tmp2);
        inc(j);
        inc(count);//--
      end;
      //////////////////cортирует и выписывает^
    end;

    while (not eof(f1)) do
    begin
      write(f,tmp1);
      read(f1,tmp1);
      inc(count);//--
    end;

    while (not eof(f2)) do
    begin
      write(f,tmp2);
      read(f2,tmp2);
      inc(count);//--
    end;
    //////////////////дописывает остатки из файлов^
    CloseFile(f);
    CloseFile(f1);
    CloseFile(f2);

    series:=series*2;
  end;

end.

Обновление

Алгоритмически - это, по сути, та же самая сортировка слиянием (где массив разделяем на две части, а потом сливаем в исходный), только без использования озу. Серия - это как бы размер массива. В сортировке слиянием мы делим массивы до мельчайших массивов - массивов с единственным элементом. А затем слияем их. А затем слияем слитые и т.д. Так моя серия = 1 изначально и while (внешний, я его убрал, т.к. попросили выложить кусочек, где ошибка) работает до того момента, пока серия<изначальный_размер_массива.

Ответы

▲ 1Принят

@111xbot111, у Вас в обоих последних while написано not eof(f1).

Наверное, в одном из них должно быть not eof(f2).


Вообще-то я delphi не знаю, но чисто алгоритмически идею с сериями я не понял.


По идее, у Вас в этом фрагменте кода сливаются 2 отсортированных файла. Или это разные участки одного и того же файла?

Обновление

IMHO, обычно эти серии сливают из 2-х файлов (образуются с сериями размера 1 из исходного при начальном распределении) в 2 других файла (уже с сериями вдвое большего размера). И так делают (переоткрывая уже только что прочитанные 2 файла на запись), пока оба не станут упорядоченными (размер серии станет n/2).

А на последнем этапе (тут размер серии уже не важен) сливают их в один файл (результат).


Впрочем, видимо у Вас какой-то похожий, но несколько другой алгоритм, который я не понимаю
(не понимаю, как из промежуточного f потом Вы опять будете делать f1 и f2 для след. цикла).

Обновление 2

Теперь понятно. Только так никто не делает, это ведь неэффективно.


Вообще стараются сначала рассортировать исходный файл по частям в памяти, каждую часть пишут в отдельный файл, потом эти файлы сливают n-путевым слиянием.


Наверное, если Вы хотите остаться в рамках алгоритма сбалансированного слияния (Ваш случай), то имеет смысл при первом проходе разбивать файл (с сортировкой частей в памяти) на уже большие серии в 2 разных файла, а потом сливать их.

И может быть, лучше не делать этот лишний проход разделения, сливать сразу 2 в 2 (а потом менять файлы местами).

Обновление 3

@111xbot111, вот не помню. Наберите в гугле

sorting algorithms external

Наверное, найдете в http://en.wikipedia.org/wiki/External_sorting

А вообще мне понравилось http://web.eecs.utk.edu/~leparker/Courses/CS302-Fall06/Notes/external-sorting2.html