Внешняя сортировка естественным слиянием PascalABC.Net

РЕФЕРАТ

Отчет  16с., 2р., 5 источников, 1 прил.

ЕСТЕСТВЕНОЕ СЛИЯНИЕ; ВНЕШНЯЯ СОРТИРОВКА

Объектом исследования являются алгоритм сортировки естественным слиянием.

Цель работы – реализация сортировки естественного слияния.

В работе рассматриваются  теоретические и практические вопросы реализации сортировки, предназначенной для работы с файлами.

В результате проделанной  работы была реализована сортировка естественного слияния.

 

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…………………………………………………………………………5

1 ПОСТАНОВКА ЗАДАЧИ…………………………………………………….....7

2 АЛГОРИТМИЧЕСКОЕ КОНСТРУИРОВАНИЕ………………………………8

2.1 ОБЩАЯ СХЕМА

               ФУНКЦИОНИРОВАНИЯ………………………………………………8

2.2 ОЦЕНКА АЛГОРИТМА

 СОРТИРОВКИ…………………………………………………………..................11

3 ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ……………………………………..12 

4 КОНТРОЛЬНЫЙ ПРИМЕР……………………………………………………...13

5 ЗАКЛЮЧЕНИЕ…………………………………………………………………...14

6 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ…………………………… 15

ПРИЛОЖЕНИЕ А. ТЕКСТЫ ОСНОВНЫХ ПРОГРАММНЫХ МОДУЛЕЙ….16

 

ВВЕДЕНИЕ

Алгоритмы внешней сортировки:

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

Данные, хранящиеся на внешних устройствах, имеют большой объем, что не позволяет их целиком переместить в оперативную память, отсортировать с использованием одного из алгоритмов внутренней сортировки, а затем вернуть их на внешнее устройство. В этом случае осуществлялось бы минимальное количество проходов через файл, то есть было бы однократное чтение и однократная запись данных. Однако на практике приходится осуществлять чтение, обработку и запись данных в файл по блокам, размер которых зависит от операционной системы и имеющегося объема оперативной памяти, что приводит к увеличению числа проходов через файл и заметному снижению скорости сортировки.

Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.

Количество элементов в серии  называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены).

В основе большинства методов внешних  сортировок лежит процедура слияния и процедура распределения. 

Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. 

Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.

Фаза – это действия по однократной обработке всей последовательности элементов. 

Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. 

Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.

Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла.

Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.

 

1. ПОСТАНОВКА ЗАДАЧИ

Реализация алгоритма  внешней сортировки естественным слиянием.  

 

2. АЛГОРИТМИЧЕСКОЕ КОНСТРУИРОВАНИЕ

2.1 ОБЩАЯ СХЕМА ФУНКЦИОНИРОВАНИЯ

Данная сортировка является улучшением сортировки слиянием и относится к внешним сортировкам.

Алгоритм сортировки слиянием был  предложен Джоном фон Нейманом в 1945 году и является одним из самых  простых алгоритмов сортировки среди  «быстрых» алгоритмов.

Особенностью этого алгоритма  является то, что он работает с элементами преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями.

Сортировка слиянием относится  к устойчивым методам сортировки.

Общий алгоритм сортировки слиянием

Сначала серии распределяются на два  или более вспомогательных файлов. Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл, вторая – во второй и так далее до последнего вспомогательного файла. Затем опять запись серии начинается в первый вспомогательный файл. После распределения всех серий, они объединяются в более длинные упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются. Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется. В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл, либо в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. И так до тех пор, пока все данные не будут отсортированы.

Выделим основные характеристики сортировки слиянием:

• количество фаз в реализации сортировки;
• количество вспомогательных файлов, на которые распределяются серии.

 

 

Сортировка естественным слиянием

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

Сортировка, при которой всегда сливаются две самые длинные из возможных последовательностей, является естественным слиянием. В данной сортировке объединяются серии максимальной длины.

Алгоритм сортировки естественным слиянием

Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2. Распределение происходит следующим образом: поочередно считываются записи a_i исходной последовательности (неупорядоченной) таким образом, что если значения ключей соседних записей удовлетворяют условию f(a_i)<=f(a_i+1), то они записываются в первый вспомогательный файл f1. Как только встречаются f(a_i)>f(a_i+1), то записи a_i+1 копируются во второй вспомогательный файл f2. Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом серии образуют упорядоченные последовательности.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2.

Шаг 4. Повторяя шаги, сливаем упорядоченные  серии до тех пор, пока не будет  упорядочен целиком весь файл.

Символ "`" обозначает признак  конца серии.

Признаками конца сортировки естественным слиянием являются следующие условия:

• количество серий равно 1 (определяется на фазе слияния).
• при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
• Естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга не более чем на единицу, называется сбалансированным слиянием, в противном случае – несбалансированное слияние.

 

Рис. 1 Иллюстрация действия алгоритма сотрировки естественным слиянием

 

 

 

 

 

2.2 ОЦЕНКА АЛГОРИТМА СОРТИРОВКИ

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью.

При сортировке естественным слиянием слиянию подвергаются упорядоченные подпоследовательности, называемые «сериями», длинной m и n, содержащиеся в двух файлах,  и дающие результирующую последовательность из m+n элементов. В каждой серии элемент r_i не больше, чем r_i+1. Если сливаются две последовательности,  каждая из n серий, то результирующая также содержит ровно n серий.

Следовательно, при каждом проходе общее число серий  уменьшается вдвое и общее число пересылок в самом плохом случае равно n * log(n), а в среднем даже меньше. Ожидаемое число сравнений, однако, значительно больше, поскольку кроме сравнений, необходимых для отбора элементов при слиянии, нужны еще дополнительные сравнения между последовательными элементами каждого файла, чтобы определить конец серии.

Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Алгоритм сортировки естественным слиянием требует для своей работы создания двух вспомогательных файлов, содержащих в среднем по n\2 элементов исходного набора, в худшем случае один из  файлов содержит n-1 элементов, а второй всего один. Дополнительных переменных для хранения промежуточных результатов не требуется.

 

 

 

 

3.ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ

ТАБЛИЦА ПРОЦЕДУР И ФУНКЦИЙ

В данной таблице будет  представлено две процедуры. Процедура  сортировки Шелла и процедура  сортировки вставками.

Процедуры и функции	Передаваемые параметры	Возвращаемое значение	Описание
Init	-	-	Связывание файлов и файловых переменных
Copy	x, y: tape	-	Копирование элемента из файла x в файл y
CopyRun	x, y: tape	-	Копирование содержимого файла x в файл y
Merge	-	-	Слияние серии
MergeRun	-	-	Сортировка естественным слиянием
Distribute	-	-	Распределение

 

 

 

 

6. КОНТРОЛЬНЫЙ ПРИМЕР

 

 

Рис. 2 Алгоритм естественного  слияния в действии 

5. ЗАКЛЮЧЕНИЕ

 

Выполнение курсовой работы позволило более подробно изучить механизм работы и эффективность внешней сортировки естественным слиянием.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6 .СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Сайт «Википедиа» [Электронный ресурс]-URL:http:/ru.wikipedia.org

2. www.cyberforum.ru

3. Вирт Н. «Алгоритмы и структуры данных программ»

4. Ахо А.В. Хопкрофт Д.Э. Ульман Д.Д. «Структура данных и алгоритмы»

5. Царев Р.Ю.  «Структуры и алгоритмы обработки данных»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ А. КОД ПРОГРАММЫ

program NaturalMerge;

 

uses

  CRT;

 

type

  item = record

    key: integer;

  end;

 

  tape = file of item;

 

var

  a, b, c: tape;

  fin, res: text;

  x: item;

  n, p: char;

  eor: Boolean;

  l: integer;

 

procedure Init;

var

  nameoffile: string;

begin

  Writeln('Введите путь до файла:');

  Read(nameoffile);

  Assign(fin, nameoffile + '.txt');

  Assign(a, 'a.txt');

  Assign(b, 'b.txt');

  Assign(c, 'c.txt');

  Assign(res, 'res.txt');

  reset(fin);

  rewrite(c);

  rewrite(res);

end;

 

procedure Copy(var x, y: tape);

var

  bufa, bufb: item;

begin

  read(x, bufa);

  write(y, bufa);

  if not eof(x) then

  begin

    read(x, bufb);

    eor := bufa.key > bufb.key;

    seek(x, filepos(x) - 1);

  end

  else

    eor := true;

end;

 

procedure CopyRun(var x, y: tape);

begin

  repeat

    copy(x, y);

  until eor;

end;

 

procedure MergeRun;

var

  bufa, bufb: item;

begin

  repeat

    read(a, bufa);

    read(b, bufb);

    seek(a, filepos(a) - 1);

    seek(b, filepos(b) - 1);

    if bufa.key < bufb.key then

    begin

      copy(a, c);

      if eor then

        copyrun(b, c);

    end

    else

    begin

      copy(b, c);

      if eor then

        copyrun(a, c);

    end;

  until eor;

end;

 

procedure Merge;

begin

  repeat

    mergerun;

    l := l + 1;

  until eof(b) or eof(a);

  while not (eof(a)) do

  begin

    copyrun(a, c);

    l := l + 1;

  end;

  while not eof(b) do

  begin

    copyrun(b, c);

    l := l + 1;

  end;

end;

 

procedure Distribute;

begin

  repeat

    copyrun(c, a);

    if not (eof(c)) then

      copyrun(c, b);

  until eof(c);

end;

 

begin

  try

    clrscr;

   

    Init;

    WriteLn;

    Writeln('=====================================================');

    Writeln;

   

    Writeln('Начальная последовательность: ');

   

    while not eof(fin) do

    begin

      read(fin, x.key);

      write(c, x);

      write(x.key, ' ');