СОРТИРОВКИ

    •  В данной теме мы рассмотрим некоторые методы сортировки массивов порядка n2. Проведет анализ производительности алгоритмов. Покажем, как путем улучшений алгоритма можно добиться некоторого выигрыша в эффективности.
    •  
      •  
          1. Дан массив a:array [1..n] of integer. Отсортировать его различными методами и сравнить затраченное время.
          2. Таблица выиграшей денежной лтереи представлена массивом выигравших билетов и соответствующем массивом выиграшей в рублях. Определить суммарный выигрыш, выпавший на билеты с номерами b(1),b(2),...,b(m) (номера не упорядочены).
          3. Дан массив некоторых числовых данных. Удалить из него все повторяющиеся элементы, отсортировав его одним из методов.
          4. Дан текст. Составить таблицу частот повторений различных символов этого текста.
      • Упражнения:
  •  Сортировка - это процесс перегруппировки заданного множества объектов в некотором определенном порядке. Рассмотрим некоторые методы сортировки массивов.

    Основное условие: выбранный метод должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте (в одном и том же массиве). Сначала разберем простые методы, их называют прямыми, где требуется порядка n2 сравнений.

    Методы сортировки "на том же месте" можно разбить на три основные категории:

    Все методы будем рассматривать на элементах массива

    a:array[1..n] of integer.

     


    СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.
    Алгоритм: элементы массива мысленно делятся на уже "готовую" и исходную последовательности. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

    В процессе поиска подходящего места для элемента х удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, т.е. х сравнивается с очередным элементом aj, а затем либо х вставляется на свободное место, либо aj сдвигается вправо и процесс "уходит" влево.

    Процесс просеивания может закончиться при выполнении одного из двух условий:

    Повторяющийся процесс с двумя условиями окончания позволяет воспользоваться приемом "барьера", поставив барьер a0 со значением х.

    for i:=2 to 10 do
    begin
    x:=a[i]; a[0]:=x; j:=i;
    while x<a[j-1] do
    begin
    a[j]:=a[j-1]; j:=j-1;
    end;
    a[j]:=x;
    end;

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

    For i:=2 to 10 do
    begin
    c:=a[i]; l:=1; r:=i;
    while l<r do
    begin
    m:=(l+r) div 2;
    if a[m]<=c then l:=m+1 else r:=m;
    end;
    for j:=i downto r+1 do
    a[j]:=a[j-1];
    a[r]:=c;
    end;

     


    АНАЛИЗ МЕТОДОВ ПРЯМОГО И ДВОИЧНОГО ВКЛЮЧЕНИЯ
    Число сравнений (С) при i-м просеивании самое большее равно i-1, самое меньшее - 1. Число присваиваний элементов (М) равно Ci+2 (включая барьер). Поэтому общее число сравнений и число присваиваний:



    Cmin=n-1 Mmin=3(n-1)
    Cmax=(n2+n-4)/4 Mmax=(n2+3n-4)/2

    Для двоичного включения: место включения обнаружено, если l=r. Таким образом, интервал должен быть единичной длины. Число сравнений фактически не зависит от начального порядка элементов. Однако, из-за того, что при делении происходит отбрасывание дробной части, истинное число сравнений может оказаться на единицу больше. В нижней части последовательности место включения отыскивается в среднем несколько быстрее, чем в верхней части, поэтому предпочтительна ситуация, в которой элементы немного упорядочены. Улучшения касаются лишь числа сравнения:
    C=n(log(n)-log(e)±0.5).

    А число передвижений М продолжает оставаться порядка n2.

     


    СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВЫБОРА
    Алгоритм: for i:=1 to n-1 do
    begin
    x:=a[i]; k:=i;
    for j:=i+1 to n do
    if a[j]<x then begin k:=j; x:=a[k] end;
    a[k]:=a[i];a[i]:=x;
    end;

     


    АНАЛИЗ ПРЯМОГО ВЫБОРА
    Число сравнений С не зависит от начального порядка элементов.
    С=(n2-n)/2
    Число перестановок минимально в случае изначально упорядоченных элементов и максимально, если первоначально они располагались в обратном порядке.



    Mmin=3(n-1) Mmax=n2/4+3(n-1)

     


    СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА
    Алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы. Повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Такой метод широко известен под названием "пузырьковая сортировка".

    for i:=2 to n do
    for j:=n downto i do
    if a[j-1]>a[j] then
    begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; end;

    Очевидный прием улучшения этого алгоритма - запоминать, были или не были перестановки в процессе некоторого прохода. Если в последнем проходе перестановок не было, то алгоритм можно заканчивать.

    w:=true;
    while w do
    begin
    w:=false;
    for j:=1 to n-1 do
    if a[j]>a[j+1] then
    begin
    w:=true; x:=a[j+1];
    a[j+1]:=a[j]; a[j]:=x;
    end;
    end;

    Улучшая "пузырьковую" сортировку (будем чередовать направление последовательных просмотров), получаем новый алгоритм - "шейкерную" сортировку.

    l:=2;r:=n;
    repeat
    for j:=r downto l do
    if a[j-1]>a[j] then
    begin
    x:=a[j-1]; a[j-1]:=a[j];
    a[j]:=x; k:=j;
    end;
    l:=k+1;
    for j:=l to r do
    if a[j-1]>a[j] then
    begin
    x:=a[j-1]; a[j-1]:=a[j];
    a[j]:=x; k:=j;
    end;
    r:=k-1;
    until l>r;

     


    АНАЛИЗ ПУЗЫРЬКОВОЙ И ШЕЙКЕРНОЙ СОРТИРОВОК
    Число сравнений в пузырьковом алгоритме С=(n2-n)/2, а минимальное и максимальное число перемещений элементов (присваиваний) равно соответственно Mmin=0 и Mmax=3(n2-n)/4

    Анализ же шейкерной сортировки довольно сложен. Минимальное число сравнений С=n-1. Обратим внимание на то, что усовершенствования не влияют на число перемещений, они лишь сокращают число излишних двойных проверок.

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

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

    В следующей теме мы рассмотрим некоторые улучшенные методы сортировки, требующие шагов порядка n·log(n).

     

Другие записи

10.06.2016. Задачи без массивов
В данной теме предлагаются решения простых задач с наименьшим числом действий (выполяемых операторов присваивания). Задача 1. Дано число а и натуральное число n. Вычислить аn (a в степени n). Решение:…
10.06.2016. МАССИВЫ
  В этом разделе предлагаются задачи, в которых реализуются алгоритмы работы с массивами (упорядоченными и неупорядоченными). Для решения задач достаточно уметь пользоваться основными конструкциями…
10.06.2016. РАЗМЕЩЕНИЯ. ПЕРЕСТАНОВКИ. СОЧЕТАНИЯ
В этой теме рассматриваются элементы комбинаторики и алгоритмы решения комбинаторных задач. Имеется n различных предметов. Сколько из них можно составить k-расстановок? При этом две расстановки считаются…
10.06.2016. ОБХОД ДЕРЕВА. ПЕРЕБОР С ВОЗВРАТАМИ
    1. Приведенная программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n). Изменить реализацию…
10.06.2016. Cписок литературы
  1. Александров В.В. Рисунок, чертеж, картина на ЭВМ. - Л., Машиностроение, 1987г. 2. Аммерал Л. Принципы программирования в машинной графике. -М., Сол Систем, 1992г. 3. Арсак Ж. Программирование игр…