АНАЛИЗ  РАБОТЫ  SBC  СОРТИРОВОК  НА  РЕАЛЬНЫХ  СТАТИСТИЧЕСКИХ  МОДЕЛЯХ

Орлов  Андрей  Геннадьевич

студент  3  курса,  кафедра  КС  СНУЯЭиП,  Украина  г.  Севастополь

E-mail:  orel777@mail.ru

Моисеев  Дмитрий  Владимирович

научный  руководитель,  канд.  техн.  наук,  доцент  каф.  КС,  Украина  г.  Севастополь

Введение

В  настоящее  время  множество  программистов-теоретиков,  а  так  же  разработчиков  ПО  во  всём  мире  занимаются  проблемой  оптимизации  работы  с  данными.  Одна  из  таких  проблем  —  это  сортировка  данных.  За  последние  пол  века  бурного  развития  компьютерных  наук  наш  мир  претерпел  значительные  изменения,  между  тем  многие  проблемы  сортировок  так  не  решены.  На  данный  момент  программисты  работая  с  сортировками  данных  пользуются  О-нотацией,  которая  показывает  лучшее  и  худшее  теоретическое  время  работы  алгоритма,  но  не  показывает  зависимость  между  временем  сортировки  и  размером  входных  данных.  В  данной  статье  будет  рассмотрена  группа  обменных  сортировок  SBC  в  которую  войдут:  глупая  сортировка  (англ.  stupid  sort),  пузырьковая  сортировка  (англ.  bubble  sort),  шейкерная  сортировка  (англ.  cocktail  sort).  Группу  SBC  так  же  будем  называть  группой  пузырькового  типа,  по  той  причине,  что  все  3  алгоритма  построены  по  одному  принципу  –  принципу  «всплывающего»  значения  (пузырька).

Цель  данной  статьи:  проанализировать  работу  SBC  сортировок  на  реальных  статистических  моделях  и  на  основе  этого  установить  зависимость  между  длинной  входных  данных  и  временем  сортировки  для  каждого  алгоритма.  Для  реализации  построения  статистической  модели  автором  была  разработана  программа  «Model1»  на  платформе  Microsoft  Visual  Studio  Express  2013  (яз.  C#). 

Описание  модели

Как  видно  из  общей  схемы  модели  процесса  сортировки  (рис.  1)  на  конечный  результат  сортировки  (массив  B)  влияют  два  фактора:  массив  входных  значений  А  и  алгоритм  сортировки. 

Рисунок  1.  Модель  процесса

Алгоритм  сортировки  будет  рассматривается  в  нашем  эксперименте  как  черный  ящик,  нас  не  интересует  те  процессы  которые  в  нём  происходят,  так  как  это  не  входит  в  тему  данной  статьи.  Однако  он  содержит  2  интересующих  нас  выхода:  это  кол-во  операций  сравнения  (N_com)  и  кол-во  операций  замены  (N_rep).  Скорость  работы  алгоритма  мы  будем  измерять  по  тактам,  а  не  по  реально  засекаемому  таймером  временю  выполнения.  Иными  словами,  каждый  шаг  алгоритма  будет  увеличивать  соответствующий  счётчик  (сравнения,  замены).  Таким  образом  мы  получим  наиболее  точную  картину  работы  алгоритма,  откинув  различного  рода  «помехи»  от  действия  ОС,  программ  и  физических  элементов.  Так  же  для  того,  чтобы  максимально  точно  определить  N_com  и  N_rep  для  последовательностей  длинною  L_gen,  будет  произведено  кол-во  генераций  входных  данных  P_gen  раз.  Стоит  отметить,  что  в  увеличение  P_gen  позволяет  получать  наиболее  точные  результаты,  однако  на  последовательностях  длинной  L_gen  >  1000,  время  анализа  будет  крайне  велико,  поэтому  было  выбрано  оптимальное  значение  P_gen  =  100.  Таким  образом  время  работы  алгоритма  будет  представляться  в  виде  2-х  значного  контейнера  T_alg  (1).

В  нашем  эксперименте  поток  входных  данных  будет  параллельно  обрабатываться  3-мя  алгоритмами  сортировки.  Иначе  говоря  набор  всех  входных  данных  поступающих  на  «вход»  каждого  алгоритма  на  каждом  шаге  будет  одинаков.  Это  в  свою  очередь  позволит  повысить  точность  сравнения  скоростей  алгоритмов  между  собою.

Результаты  эксперимента

Как  было  отмечено  в  начале,  для  построения  статистической  модели  было  разработано  специальное  ПО,  позволяющее  просчитать  огромное  кол-во  операций  сортировок.  (рис.  2). 

Рисунок  2.  Скриншот  программы

В  программе  было  предусмотрено  введение  P_gen  —  поле  «Кол-во  проходов»  и  L_gen  —  поле  «Длина  последовательности».  В  поле  чуть  ниже  отображены  все  анализируемые  последовательности,  а  в  3-х  соответствующих  таблицах  отображены  значения  N_com  и  N_rep  на  каждой  итерации  к  соответствующей  сортировке.  Под  каждой  таблицей  располагаются  средние  значения  N_com  и  N_rep,  т.е  T1_alg  (T1  —  для  глупой  сортировки),  T2_alg  (T2  —  для  сортировки  пузырьком),  T3_alg  (T3  —  для  шейкерной  сортировки).

Путём  последовательного  изменения  L_gen  были  сняты  значения  T1_alg[N_com],  T2_alg[N_com],  T3_alg[N_com]  и  построен  график.  (рис.  3).  Так  же  на  основе  полученных  значений  были  составлены  формулы  зависимости  T_alg  от  L_gen  . 

Рисунок  3.  Зависимость  T_alg[N_com]  от  L_gen  ,

Стоит  отметить  очень  важную  особенность,  что  при  любом  значении  L_gen,  N_rep  во  всех  трёх  алгоритмах  одинаковое(2).  Это  позволяет  сделать  вывод,  что  N_rep  можно  не  учитывать  при  сравнении  T_alg  (3).

Ниже  приведены  эмпирические  формулы  расчёта  T_alg  от  L_gen  полученные  в  ходе  эксперимента.  Для  того,  чтобы  повысить  точность  расчёта  для  каждой  формулы  в  круглых  скобках  указано  максимально  используемое  автором  значение  L_gen.

Для  глупой  сортировки:

Для  сортировки  пузырьком:

Для  шейкерной  сортировки:

Согласно  формулами  2,3  можно  сделать  вывод:

Вывод

В  ходе  эксперимента  удалось  получить  точную  формульную  зависимость  между  значением  количества  элементов  массива  и  скоростью  его  обработки  для  каждого  SBC  алгоритма.  За  счет  обнаруженного  равенства  N_rep  (кол-во  замен)  во  всех  случаях,  можно  сравнивать  скорости  алгоритмов  непосредственно  по  N_com  (кол-во  сравнений).  Таким  образом  был  впервые  получен  универсальный  и  достоверный  критерий  сравнения  алгоритмов.

Список  литературы:

1.Ананий  В.  Левитин.  Глава  3.  Метод  грубой  силы:  Пузырьковая  сортировка  //  Алгоритмы:  введение  в  разработку  и  анализ  =  Introduction  to  The  Design  and  Analysis  of  Algorithms.  М.:  Вильямс,  2006.  —  С.  144—146.  —  ISBN  5-8459-0987-2.

2.Грин  Д.,  Кнут  Д.  Математические  методы  анализа  алгоритмов.  Пер.  с  англ.  М.:  Мир,  1987.  —  120  с.

3.Макконелл  Дж.  Основы  современных  алгоритмов.  Изд.  2  доп.  М.:  Техносфера,  2004.  —  368  с.  —  ISBN  5-94836-005-9.