Pascaler
О проекте Теоретический материал Тестирование Архив задач
Войти в личный кабинет



О проекте


Преподавателям


Тема: Сортировка методом слияний.

Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным.

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

Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.

Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.

Рассмотрим пример работы алгоритма слияния.

Пусть в массиве А содержатся 3 элемента: {5, 13, 14}, а в массиве В - 4 элемента: {7, 9, 10, 12}. Внимательно рассмотрите таблицу, в которой по шагам показано изменение переменных i, i1, i2 и действия с массивами.

Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно n1 и n2 элементов. Результирующий массив С будет содержать n1+n2 элементов.

. . .
i1 := 1;
i2 := 1;
for i := 1 to n1+n2 do
  if i1>n1
    then
      begin
        C[i] := B[i2];
        i2 := i2+1;
      end
    else
      if i2>n2
        then
          begin
            C[i] := A[i1];
            i1 := i1+1;
          end
        else
          if A[i1]<=B[i2]
            then
              begin
                C[i] := A[i1];
                i1 := i1+1;
              end
            else
              begin
                C[i] := B[i2];
                i2 := i2+1;
              end;
. . .

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

Рекурсивная сортировка слиянием (для любопытных)

Задача. Напишите программу, содержащую алгоритм слияния в процедуре Sort(A, B, b1, e1, e2). Алгоритм должен копировать со слиянием два упорядоченные куска из массива А с номерами от b1 до e1 и от e1+1 до e2 соответственно в массив В с номерами элементов от b1 до e2.

Предположив, что Вы правильно выполнили предыдущую задачу, алгоритм сортировки можно определить очень просто:

  1. если длина сортируемого массива 1, то ничего не делается;


  2. в противном случае массив делится на две одинаковые (или почти одинаковые) части, к каждой части применяется алгоритм сортировки, после чего эти упорядоченные части сливаются в один упорядоченный кусок.

Рассмотрите процедуру сортировки слиянием. На вход процедуры сортировки поступает неупорядоченный кусок массива А с номерами элементов от b до e, на выходе - тот же кусок, но упорядоченный. Массив С - вспомогательный.

Procedure Sort2(Var A, C : Array1; b, e : integer);
Var
  i, d : integer;
Begin
  if b<e
    then
      begin
        d := (b+e) div 2;
        Sort2(A, C, b, d);
        Sort2(A, C, d+1, e);
        Sort(A, C, b, d, e);
        for i := b to e do
          A[i] := C[i]
      end;
End;
Вернуться назад
2003—2012 © Группа «Vimedia»
Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.