Алгоритмы упорядочивания (сортировки)

на языке Глагол

 

Проектное исследование по информатике

выполнено учеником 9 класса

 


Оглавление

Определение алгоритма

Знакомство с языком Глагол

Оболочка Глагола

Оболочка Турбо Паскаля

Необходимость упорядочивания данных

Выбор алгоритмов и видов данных

Приложение для испытания алгоритмов

Разбор главного отдела приложения

Алгоритм упорядочивания вставкой

Алгоритм упорядочивания двоичной вставкой

Алгоритм упорядочивания выбором

Алгоритм упорядочивания простым обменом ("пузырьковая сортировка")

Алгоритм упорядочивания быстрым обменом ("быстрая сортировка")

Испытание алгоритмов

Сравнение производительности на короткой последовательности

Сравнение производительности на длинной последовательности

Заключение

Список источников и литературы


Определение алгоритма

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

Само слово алгоритм происходит от algorithmi, являющегося, в свою очередь, латинской транслитерацией арабского имени хорезмийского математика IX в. аль-Хорезми. В средневековой Европе алгоритмом называлась десятичная позиционная система счисления и искусство счёта в ней, поскольку именно благодаря латинскому переводу (XII в.) трактата аль-Хорезми Европа познакомилась с позиционной системой.


Знакомство с языком Глагол

В 1970 году Никлаус Вирт создал язык программирования Паскаль. В 1975 году он разработал язык Модула. Его доработанная версия - Модула-2 (1980 г.) стала довольно известной, хотя и не превзошла по популярности Паскаль фирмы Borland.

В 1988 году  Вирт разработал язык программирования Оберон, основой которого стала Модула-2, существенно упрощённая, но при этом дополненная новыми возможностями. В 1992 году Вирт и Х. Мёссенбёк сообщили о новом языке программирования - Оберон-2, - минимально расширенной версии Оберона.

Язык программирования Глагол был опубликован отечественными разработчиками в 2003 году. Этот язык очень похож на Оберон. Основное отличие Глагола от Оберона состоит в том, что в нём используются только русские служебные слова.

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

Преобразователь Глагола (компилятор языка программирования Глагол) на данный момент реализован только под платформу Windows, но есть возможность создавать программы сокращённого Глагола для КПК. Сокращённый Глагол представляет собой упрощённую версию языка, разработанного с целью повысить быстродействие программ и уменьшить нагрузку на процессор. Сборник "Разработки на Глаголе" распространяется свободно. Среду разработки приложений на Глаголе можно изменять по своему усмотрению.

Запись программы на языке Глагол достаточно ясно показывает структуру алгоритма, поэтому графические блок-схемы алгоритмов в данной работе не используются. Описание языка будет приводиться по мере необходимости. С полным описанием языка Глагол и основами программирования на нём можно познакомиться на сайте http://www.glagol.nad.ru.


Оболочка Глагола


Оболочка Турбо Паскаля


Необходимость упорядочивания данных

В современном мире человек окружен океаном информации. Для того, чтобы воспользоваться нужной информацией, надо уметь её быстро находить. А искать данные гораздо проще, если они упорядочены. Упорядочивание возможно только тогда, когда задан закон сравнения. Например, текстовую информацию упорядочивают по алфавиту. Также часто упорядочивают данные по числовому значению какой-либо величины. Для удобства доставки почты почтальоны предварительно раскладывают корреспонденцию в своих сумках в порядке возрастания номеров домов и квартир. Мы встречаемся с упорядоченными объектами в телефонных справочниках, в оглавлениях книг, в библиотеках, в словарях, в расписаниях, на складах - почти везде, где нужно искать хранимые объекты.

Упорядочивать объекты не так трудно. Даже малыши могут собирать матрёшку и пирамидку из разных по размеру предметов,

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

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


Выбор алгоритмов и видов данных

Существует множество алгоритмов упорядочивания данных. Выбор того или иного алгоритма зависит от структуры и объёма упорядочиваемых данных, доступных вычислительных ресурсов и др. Наилучшего алгоритма упорядочивания нет ввиду множества параметров оценки его работы:

Ещё одним важным свойством алгоритма является область его применения:

В нашей работе мы рассмотрим основные классы алгоритмов, работающих только с теми данными, которые умещаются в оперативной памяти компьютера, что при современных объёмах этой памяти достаточно для многих прикладных задач. Это такие алгоритмы как упорядочивание простой вставкой, двоичной вставкой, простым выбором, простым обменом ("пузырьковая сортировка"), быстрым обменом ("быстрая сортировка").

Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явное значение в наборе данных объекта. Это значение называется ключом объекта, поэтому для представления объектов хорошо подходит такой вид данных языка Глагол как НАБОР. Например, можно описать объект следующим образом:

ВИД

  Объект = НАБОР

    ключ:ЦЕЛ;

    (* описание других данных, характеризующих объект *)

  КОН;

Говоря об алгоритмах упорядочивания, мы будем обращать внимание лишь на значение ключа объекта, другие же данные объекта можно даже и не определять. Поэтому из наших дальнейших рассмотрений все сопутствующие объекту данные опускаются, и мы считаем, что вид объекта определён как ЦЕЛ:

ВИД

  Объект = ЦЕЛ;


Приложение для испытания алгоритмов

Обычно исходный текст приложения разбивается на несколько отделов. Из главного отдела нашего приложения "Упорядочивание" будут осуществляться проверочные вызовы рассматриваемых алгоритмов. Сами же алгоритмы упорядочивания будут располагаться в особых отделах с соответствующими названиями: "Вставкой", "Вставкой2", "Выбором", "Обменом", "ОбменомБ".


Разбор главного отдела приложения

В начале отдела записывается его название:

ОТДЕЛ Упорядочивание+;

Знак "+" означает, что этот отдел является главным, т.е. его указания начнут выполнятся в первую очередь при запуске приложения.

Далее записываются отделы, которые использует данный отдел в своей работе:

ИСПОЛЬЗУЕТ
  Вставкой,
  Вставкой2,
  Выбором,
  Обменом,
  ОбменомБ,
  Матем ИЗ "...\Отделы\Числа\",
  ОС    ИЗ "...\Отделы\Обмен\",
  Вывод ИЗ "...\Отделы\Обмен\";

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

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

ПОСТ
  упВставкой = 0;
  упВставкой2= 1;
  упВыбором  = 2;
  упОбменом  = 3;
  упОбменомБ = 4;
 

  Повторов = 10000;

Наши алгоритмы мы будем проверять на коротких и длинных рядах объектов. Ранее мы договорились, что наши объекты будут представлены целыми числами. Поэтому переменные рядов будут описываться следующим способом:

ПЕР
  короткийРяд:РЯД 30    ИЗ ЦЕЛ;
  длинныйРяд :РЯД 30000 ИЗ ЦЕЛ;

Основная задача нашего приложения, которая испытывает все наши алгоритмы, выглядит так:

ЗАДАЧА Испытания;
ПЕР
  алгоритм:ЦЕЛ;
УКАЗ
  ОТ алгоритм:=упВставкой ДО упОбменомБ ВЫП
    ВЫБРАТЬ алгоритм ИЗ
    | упВставкой: Испытание(Вставкой.Упорядочить)
    | упВставкой2:Испытание(Вставкой2.Упорядочить)
    | упВыбором:  Испытание(Выбором.Упорядочить)
    | упОбменом:  Испытание(Обменом.Упорядочить)
    | упОбменомБ: Испытание(ОбменомБ.Упорядочить)
    КОН
  КОН
КОН Испытания;

В конце отдела идут указания, которые запускают нашу основную задачу. Конец отдела определяется повтором его названия и заключительной точкой.

УКАЗ
  Испытания
КОН Упорядочивание.


Алгоритм упорядочивания вставкой

Ряд делится на уже упорядоченную (готовую) последовательность р0...рi-1 и неупорядоченную (исходную) последовательность рi...рn-1. При каждом шаге, начиная с i=1, и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-е число и вставляется в нужное место готовой последовательности.

Для просмотра работы алгоритма нажмите кнопку (>) в правом углу рисунка.



Алгоритм упорядочивания двоичной вставкой

В алгоритме упорядочивания простой вставкой место вставки определялось простым перебором чисел в готовой последовательности. Этот алгоритм не трудно улучшить, если обратить внимание на то, что готовая последовательность р0...рi-1, в которую нужно вставить новое число, сама уже упорядочена. Проще всего использовать метод двоичного поиска, при котором делается попытка сравнения с серединой готовой последовательности, затем сравнение продолжается в выбранной половине последовательности до тех пор, пока не будет найдена требуемая точка вставки.

Для просмотра работы алгоритма нажмите кнопку (>) в правом углу рисунка.



Алгоритм упорядочивания выбором

Ряд делится на уже упорядоченную (готовую) последовательность р0...рi-1 и неупорядоченную (исходную) последовательность рi...рn-1. При каждом шаге, начиная с i=1 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается наибольшее число и меняется с рi-1 числом готовой последовательности.

Для просмотра работы алгоритма нажмите кнопку (>) в правом углу рисунка.



Алгоритм упорядочивания простым обменом ("пузырьковая сортировка")

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

Для просмотра работы алгоритма нажмите кнопку (>) в правом углу рисунка.



Алгоритм упорядочивания быстрым обменом  ("быстрая сортировка")

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

ЗАДАЧА Упорядочить-(ряд+:РЯД ИЗ ЦЕЛ);
(* Цель:  упорядочивание с помощью разделения на участки (Ч.Хоар)
 * До:    <ряд> - исходный ряд
 * После: <ряд> - упорядоченный ряд *)
ПЕР
  Л,П:ЦЕЛ;    (* текущий участок *)
  л,п:ЦЕЛ;    (* новый участок *)
  граница:ЦЕЛ;(* граничное значение для разделения *)
  рядл:ЦЕЛ;   (* промежуточное значение для обмена *)
  глубина:ЦЕЛ;(* текущая глубина стека *)
  стек:РЯД 32 ИЗ НАБОР Л,П:ЦЕЛ КОН; (* стек для новых участков *)
УКАЗ
  глубина:=0;
  стек[0].Л:=0;
  стек[0].П:=РАЗМЕР(ряд)-1;
  ПОВТОРЯТЬ
    (* выбор из стека последнего запроса *)
    Л:=стек[глубина].Л;
    П:=стек[глубина].П;
    УМЕНЬШИТЬ(глубина);
    ПОВТОРЯТЬ
      (* разделение ряд[Л]..ряд[П] *)
      л:=Л; п:=П;
      граница:=ряд[(Л+П) ДЕЛИТЬ 2];
      ПОВТОРЯТЬ
        ПОКА ряд[л] > граница ВЫП УВЕЛИЧИТЬ(л) КОН;
        ПОКА граница > ряд[п] ВЫП УМЕНЬШИТЬ(п) КОН;
        ЕСЛИ л <= п ТО (* обмен ряд[л] с ряд[п] *)
          рядл:=ряд[л];
          ряд[л]:=ряд[п];
          ряд[п]:=рядл;
          УВЕЛИЧИТЬ(л);
          УМЕНЬШИТЬ(п)
        КОН
      ДО л > п;
      ЕСЛИ п-Л < П-л ТО
        ЕСЛИ л < П ТО (* запись в стек запроса на упорядочивание правой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=л;
          стек[глубина].П:=П
        КОН;
        П:=п (* продолжение упорядочивания левой части *)
      ИНАЧЕ
        ЕСЛИ Л < п ТО (* запись в стек запроса на упорядочивание левой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=Л;
          стек[глубина].П:=п
        КОН;
        Л:=л (* продолжение упорядочивания правой части *)
      КОН
    ДО Л >= П
  ДО глубина < 0
КОН Упорядочить;

 


Испытание алгоритмов

Папку \Упорядочивание\ с исходными текстами рассматриваемых алгоритмов перепишите в папку \Глагол\Приложения\ сборника разработок  с сайта http://www.glagol.nad.ru.

После этого в папке \Глагол\Приложения\Упорядочивание\ окажутся исходные тексты двух приложений ("Упорядочивание.отд" и "ИзФайла.отд") и отделы с вышеперечисленными алгоритмами.

Приложение "Упорядочивание" служит для сравнения производительности всех рассматриваемых алгоритмов. Приложение "ИзФайла" считывает ряд данных из заданного входного файла (пример такого файла - "НеупРяд.txt"), упорядочивает его  алгоритмом быстрого обмена и записывает его в выходной файл.

Для получения исполняемых файлов "Упорядочить.exe" и "ИзФайла.exe" необходимо запустить командный файл "Построить.bat" или воспользоваться оболочкой программирования языка Глагол.


Сравнение производительности на короткой последовательности

Скорость работы алгоритмов зависит нелинейно от размера упорядочиваемых данных, поэтому для сравнения рассматриваемых алгоритмов задавалось два ряда данных: короткий (из 30 случайных чисел) и длинный (из 30000 случайных чисел). Испытания проводились на процессоре PIII 1133МГц под управлением Windows XP. Один короткий ряд упорядочивался настолько быстро, что время его работы не удавалось измерить, и для получения значимого времени этот ряд пришлось упорядочивать 10000 раз.

 

Алгоритм упорядочивания 10000 раз 30 чисел
Время, мс % Место
Вставкой 50 63 4
Двоичной вставкой 40 50 2(3)
Выбором 40 50 2(3)
Простым обменом ("пузырьковая сортировка") 80 100 5
Быстрым обменом ("быстрая сортировка") 30 38 1

 


Сравнение производительности на длинной последовательности

 

Алгоритм упорядочивания 1 раз 30000 чисел
Время, мс % Место
Вставкой 4055 42 4
Двоичной вставкой 2433 25 2
Выбором 3194 33 3
Простым обменом ("пузырьковая сортировка") 9654 100 5
Быстрым обменом ("быстрая сортировка") 10 0,1 1

 


Заключение

Алгоритмы упорядочивания данных могут быть представлены в ясной и доступной форме посредством языка Глагол. Сравнительный анализ приведённых алгоритмов позволил прийти к следующим выводам:

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


Список источников и литературы

  1. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. СПб.: Невский диалект, 2001.

  2. Немнюгин С.А. Turbo Pascal. СПб.: Издательство "Питер", 2001.

  3. Алгоритм // БСЭ.

  4. Разработки на Глаголе. http://www.glagol.nad.ru.

  5. Турбо Кириллица // Software. 2006. № 21, http://www.kv.by/index2006211106.htm.

  6. Материал из Википедии. http://ru.wikipedia.org/wiki/Алгоритм_сортировки.

  7. Материал из Традиции. http://traditio.ru/index.php/Глагол_(язык_программирования).

  8. Материал из Википедии. http://ru.wikipedia.org/wiki/Вирт,_Никлаус