Сортировка. 1. 1 Основные классы методов сортировки 2 Сортировка подсчетом 3 Сортировка вставками

• Название: 1. 1 Основные классы методов сортировки 2 Сортировка подсчетом 3 Сортировка вставками
• Анкор: Сортировка
• Дата: 21.02.2022
• Размер: 166.96 Kb.
• Имя файла: 196039.docx
• Тип: Решение; #368548

Содержание
Введение

1. Классы методов сортировки

1.1 Основные классы методов сортировки

1.2 Сортировка подсчетом

1.3 Сортировка вставками

1.4 Обменная сортировка

1.5 Сортировка посредством выбора

1.6 Шаблоны функций С++

1.7 Итоги главы

2. Анализ выбранного метода

2.1 Теоретическое обоснование метода

2.2 Реализация алгоритма

2.3 Тестирование алгоритма

3. Итоги анализа алгоритма

Заключение

Список используемых источников

Приложение 1. Список иллюстраций

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

Актуальность решения технических задач в данной области сохраняется и на сегодняшний день. Дональд Кнут в книге «Сортировка и поиск» утверждает, что алгоритмы сортировки занимают половину времени исполнения всех процессов обработки данных вычислительной машиной. Автор привязывает это к трем основным причинам:

• 
  алгоритмы сортировки находят очень широкое применение
  
• 
  алгоритмы сортировки используются часто без надобности
  
• 
  используются несовершенные алгоритмы сортировки
  

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

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

Цель работы – анализ результатов тестирования рассматриваемого алгоритма, вывод о приоритетах и недостатках данного алгоритма и методах его реализации.
1. Классы методов сортировки

2. 1.1 Основные классы методов сортировки

В настоящее время существует огромное количество самых различных способов сортировки. Все они являются методами внутренней или внешней сортировки. Внутренней сортировкой называется сортировка, при которой все количество сортируемых записей помещается в оперативной памяти, а внешней – когда в оперативной памяти невозможно разместить все записи. Внутренняя сортировка позволяет создавать более гибкие и, следственно более выгодные методы сортировки. Методы же внешней сортировки зачастую основаны на методах внутренней, с тем лишь различием, что в них внесены некоторые дополнительные шаги. Поэтому мы не будем останавливаться на внешней сортировке и рассмотрим основные классы методов внутренней сортировки. Отметим, что рациональным можно считать алгоритм, время выполнения которого максимально приближено к формуле.
(1.1)
Все методы можно разделить на четыре основных класса:

• 
  Сортировка вставками
  
• 
  Сортировка подсчетом
  
• 
  Обменная сортировка
  
• 
  Сортировка посредством выбора
  

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

4. 1.2 Сортировка подсчетом

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

Для описания данного и других методов сортировки введем некоторые определения. Пусть дано N элементов, которые необходимо упорядочить назовем их записями. Также каждая запись имеет свой ключ , который и управляет процессом сортировки. На множестве элементов a, b, c вводится соотношение “ < ”, таки образом, что выполняется:

1. 
   справедливо только одно из соотношений: a < b, a = b, b < a
   
2. 
   если a < b и b < c то a < c
   

Эти два свойства однозначно определяют отношение, такое, что любое множество элементов, обладающее этим соотношением, поддается сортировке большинством методов. Задача сортировки состоит в том, чтобы упорядочить ключи в порядке неубывания: Теперь вернемся к нашему методу. Его смысл заключается в том, чтобы подсчитать количество ключей меньших каждого из ключей сортируемых элементов. То есть, если меньше ключа имеется j ключей, то его положение в таблице ключей должно быть j+1. Очевидно, такой подсчет можно выполнить путем сравнений: Но очевидно, что в этом алгоритме половина сравнений излишне, и его можно реализовать так: . Для реализации данного алгоритма целесообразно использовать дополнительную таблицу count[n]. В результате окончательное положение записи будет определено значением count[j] + 1. Итак, алгоритм (А) сортировки методом подсчета выглядит так:

А_1. Установить count[1] .. count[N] равными 0

А_2. [цикл по i] Выполнить шаг А_3 при i = N .. 2

А_3. [цикл по j] Выполнить шаг А_4 при j = N .. 1

А_4. если , то увеличить count[j] на 1; иначе увеличить count[i]

Отметим, что данный алгоритм не предусматривает перестановку самих записей. В чем то этот алгоритм похож на сортировку таблицы адресов, но в отличие от последней элемент count[j] указывает куда нужно отправить элемент , а не элемент, который нужно отправить на место . Скорость работы такого алгоритма выражается формулой.
(1.2)
Зависимость скорости от говорит о невысокой скорости выполнения алгоритма. Но с помощью некоторых усовершенствований скорость алгоритма можно привести к оптимальной зависимости (1.1)

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

5. 1.3 Сортировка вставками

Сортировка вставками является одним из важнейших классов методов внутренней сортировки. Идея этих методов заключается в том, что рассматриваемый в данный момент ключ подразумевает под собой, что все ключи уже упорядочены. То есть рассматриваемый элемент стоит поместить на полагающееся ему место в данном ряду. Рассмотрим, к примеру, простейший из методов вставок – метод простых вставок. Такой метод отражается в простейшем алгоритме (B):

В_1 [цикл по j] выполнить шаги В_2 – В_5 при j = 2 .. N

B_2 установить i = j-1,

B_3 если , то перейти к шагу В_5

В_4 установить если i < 0, то вернуться к В_3, если i=0, то установить

В_5 установить

Время выполнения такого алгоритма можно выразить формулой.
(1.3)
Квадратичная зависимость от числа элементов N показывает, что применение такого алгоритма невыгодно для большого числа записей. Это обусловлено двумя причинами. Первое: с каждым новым циклом алгоритма приходится просматривать все больше и больше записей, и второе: с каждым циклом необходимо перемещать все больший массив записей при вставке новой в отсортированный ряд.

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

Чтобы избежать постоянного перемещения записей в массиве с маленьким шагом, при котором каждый элемент проходит в среднем N/3 перемещений трудно избавиться от квадратичной зависимости. Но в 1959 году был предложен метод сортировки с убывающим шагом. Его предложил Дональд Шелл, в этом алгоритме заключена идея сортировки массива записей по частям, с последовательным увеличением числа записей в одной части в два раза. Такой подход позволяет максимально приблизить скорость работы алгоритма сортировки вставками до (1.1).

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

Метод пузырька – наиболее наглядный метод обменной сортировки, при котором последовательно выполняются сравнения соседних записей и в случае если ключ первого больше ключа второго, эти записи переставляются местами. Затем сравниваются и так далее, до тех пор, пока все записи не будут упорядочены. Алгоритм метода обменной сортировки с выбором (С) представлен ниже:

С_1 установить индекс верхнего элемента B = N

C_2 [цикл по j] установить t = 0. если В = 0 то перейти к шагу С_4, иначе выполнить шаг С_3 при j = 1 .. (B-1), затем перейти к шагу С_4.

C_3 сравнить если , то поменять местами установить t =j

C_4 если t = 0, то завершить алгоритм, иначе установить В = t и перейти к шагу С_2.

Программа, реализующая этот алгоритм получается более сложной, чем, к примеру, программа, реализующая алгоритм В сортировки простыми вставками, но выполняется в среднем более чем в два раза дольше. В среднем, время выполнения алгоритма С выражается формулой.
(1.4)
В связи с этим существует несколько усовершенствований метода пузырька. Первый подход заключается в том, чтобы снизить количество сравнений. Он также известен как метод Шейкер-сортировки. В отличие от простого метода пузырька сравнение происходит как в одном, так и в другом направлениях. Но и этот метод не превосходит в быстродействии метод простых вставок, который, как мы уже знаем, в свою очередь не пригоден для использования при большом количестве сортируемых элементов N.

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

Еще один весьма привлекательных метод обменной сортировки был предложен в 1964 году К.Э. Бэтчером. Его метод далеко не очевиден. В сравнение с методом пузырька он направлен на то, чтобы избежать, казалось бы, неизбежного, а именно того, чтобы число сравнений в алгоритме было равно числу инверсий в исходном файле. Для этого Бетчером был предложен алгоритм поиска возможных сравнений. По сути, этот алгоритм производит сортировку отдельных подпоследовательностей и дальнейшее их слияние. Поэтому такой метод получил название обменной сортировкой со слиянием. С одной стороны эффективность этого алгоритма не велика, но все недостатки компенсируются одним аспектом – этот алгоритм позволяет извлекать большую выгоду на машинах, позволяющих проводить параллельные вычисления. То есть можно параллельно отсортировать несколько подфайлов, а затем выполнить слияние. Поэтому этот метод также известен как алгоритм параллельной сортировки Бутчера.
1.5 Сортировка посредством выбора
Наконец рассмотрим еще один важный класс методов внутренней сортировки. Идея методов этого класса основана на многократном выборе одного элемента. Простейший алгоритм метода сортировки посредством выбора очевидно представить таким образом:

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

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

D_1. [цикл по j] Выполнить шаги D_2, D_3 при j = 1 .. N

D_2. Найти наименьший из ключей , пусть это будет

D_3. Взаимозаменить и

Скорость работы этого алгоритма можно представить формулой.
(1.5)
Как видно, она лишь немного меньше скорости выполнения алгоритма простых вставок. Этот алгоритм отличает его простота и очевидность, а также то, что способы его усовершенствовать весьма ограничены. Конечно, существует весьма простой способ улучшения алгоритма простого выбора: разбить сортируемый массив на несколько частей. Мы еще поговорим об этом в главе 2.

6. 1.6 Шаблоны функций С++

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

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

В данном случае мы ввели тип-параметр Type. Компилятор, в зависимости от того, параметры какого типа будут подставлены в функцию, интерпретирует ее так или иначе. Шаблон может быть конкретизирован или, как иногда говорят инстанцирован, для любого встроенного или определенного пользователем типа. Имя типа-параметра, использованное программистом в объявлении шаблона, может быть использовано как имя обычного типа, например для объявления переменных.

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

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

7. 1.7 Итоги главы

Еще раз отметим, что разделение методов сортировки на классы весьма условно. Зачастую видно, что методы различных классов представляют собой практически зеркальную копию друг друга, или используют по-разному реализованную одну и туже идею. Также взаимосвязи прослеживаются и в зависимости скорости выполнения алгоритмов от числа сравнений и числа элементов. Среди рассмотренных методов трудно выделить какие-то лучшие и худшие методы, хотя для тех или и иных задач все же существуют приоритетные алгоритмы сортировки. Насколько видно из рассмотренной главы в общем случае наиболее выгодным методом является метод вставок, преимущественно метод Шелла, быстрая сортировка или метод бинарных вставок. Более сложные методы, как правило, оказываются и более эффективны. И, как правило, несут под собой сложное теоретическое обоснование. На фоне этого выделяется рассмотренный нами метод выбора. Очень простой и в тоже время он почти не уступает в скорости выполнения методам вставок и превосходит обменные методы сортировки. В связи с этим мы выбираем его в качестве субъекта исследования в нашей дальнейшей работе. Мы постараемся более детально рассмотреть его теоретическое обоснование, в теории проанализировать возможности усовершенствования метода. Написать программу, реализующую алгоритм сортировки посредством простого выбора и протестировать ее на описанной платформе для анализа реальных зависимостей этого метода от типа и размера сортируемого массива.

4. 2. Анализ выбранного метода

   2. 2.1 Теоретическое обоснование метода

Вновь возвращаемся к алгоритму D, рассмотренному в разделе 1.5:

D_1. [цикл по j] Выполнить шаги D_2, D_3 при j = 1 .. N

D_2. Найти наименьший из ключей , пусть это будет

D_3. Взаимозаменить и

Очевидно, время выполнения этого алгоритма зависит от числа элементов N, числа сравнений C, и числа «правосторонних минимумов» M¹. Число сравнений в данном алгоритме не зависит от значений ключей и равно:
(2.1)
Число М будет переменной величиной:
(2.2)
Исходя из этого среднее время выполнения такого алгоритма:
(2.3)
Иначе можно ссылаться на порядок числа пересылок². В худшем случае оно равно , в то время как средний порядок числа пересылок равен , что соответствует формуле (1.1). Это показывает, что метод простого выбора выгоден, несмотря на свою неизысканность, что выделяет его из ряда прочих методов внутренней сортировки.

Далее рассмотрим способы усовершенствования метода простого выбора. Обратимся снова к алгоритму D. Рассмотрим для начала его второй шаг. Можно ли каким-либо образом усовершенствовать способ поиска минимума? В общем – нет. В любом алгоритме поиска минимума, основанном на сравнении пар, необходимо выполнить как минимум n-1 сравнений. Значит ли это, что скорость выполнения алгоритма, основанного на сравнении пар, будет пропорциональна ? В общем – нет. По крайней мере, в нашем алгоритме имеется еще и вторая часть. И даже простое ее усовершенствование приведет к ощутимому результату. Рассмотрим, например последовательность из 16 чисел, которую необходимо отсортировать (рис. 1).


Рисунок 1 Пример сортировки улучшенным методом выбора

алгоритм сортировка шаблон функция

Проведем довольно простое усовершенствование: разобьем 16 чисел на четыре группы, по четыре числа в каждой. Теперь поиск минимума будет производиться для каждой группы. После этого поиск минимума происходит среди минимальных элементов каждой из групп. На следующем шаге цикла требуется повторить поиск минимума уже только в одной группе и сравнить его с уже имеющимися элементами из других групп; и так далее до того, пока не останется элементов для сравнения. Конечно, этот способ требует более сложного алгоритма и дополнительной памяти для области вывода. Но, если N – точный квадрат, то массив разбивается на √N групп, по √N элементов в каждой. Таким образом, каждый выбор (кроме первого) требует √N-1 сравнений, плюс √N-1 сравнений среди наименьших элементов групп. Тогда скорость работы алгоритма получается порядка O(N√N), что в сравнении с гораздо предпочтительней.

Такой метод был назван метод квадратичного выбора и впервые был опубликован в 1956 году Э.Х. Френдом. Автор обобщил эту идею и описал возможность создания метода кубического выбора (массив делится на групп, по подгрупп с элементами), выбора четвертой степени и т. д. Итак, Френд пришел к выбору n-ой степени, который отражается в методе выбора из бинарного дерева.

Этот весьма любопытный метод напоминает систему турнира на выбывание. Для определения минимального элемента при представлении сортировки в виде дерева происходит за сравнений. А для определений минимума из оставшихся с каждым шагом требуется не более сравнений. Итого суммарная скорость выполнения алгоритма будет равна приблизительно . Но с другой стороны для реализации такого метода потребуется дополнительный массив с индексами вышедших вверх элементов после каждого круга сравнений, так как та запись, в которой он располагался до этого, будет заменена на бесконечность; к тому же потребуется и дополнительная область вывода. Таким образом, встает вопрос: можно ли обойтись без замены элементов на бесконечности и тем самым избежать довольно больших затрат памяти? Решением этого вопроса является метод, представленный ниже.

Пирамидальная сортировка основана на последовательной перестройке исходного массива в пирамиду таким образом, что на вершине находится наибольший элемент. Сам метод был придуман Дж. У. Дж. Уильямсом в 1964 году. Эффективную его реализацию предложил Р. У. Флойд в том же году. Предложенный им алгоритм преобразует исходный файл в пирамиду, а затем многократно исключает вершину, расставляя элементы в соответствующем порядке. Этот алгоритм очень громоздок и в то же время довольно изыскан. Скорость его работы оценивается в среднем формулой (2.3):
, (2.4)
что не лучше скорости алгоритмов Шелла и быстрой сортировки. Но в отличие от прочих быстрых алгоритмов, в которых худшее значенье скорости достигает , скорость алгоритма пирамидальной сортировки всегда будет не больше , что делает этот алгоритм очень выгодным для сортировки массивов с большим числом инверсий. На этом перейдем к реализации выбранного нами алгоритма сортировки.

3. 2.2 Реализация алгоритма

Для реализации алгоритма сортировки посредством простого выбора (алгоритм D) мы будем использовать язык программирования C++. Для этого составим блок-схему нашего алгоритма с использованием цикла с заданным числом повторений (рис 2). Данный алгоритм будет сортировать массив array, размера size в порядке неубывания. Для реализации алгоритма потребуется использовать один вложенный цикл, реализующий поиск минимума. Как видно на схеме этот цикл (блок 5) производит поиск минимума только среди элементов, которые еще не были выбраны – это позволяет избежать замены выбранных элементов на бесконечность. Блок 7 реализует перестановку выбранного минимума с первым элементом рассматриваемого подмассива. На следующем шаге главного цикла происходит установка счетчика count на элемент вперед и инициализация переменной min значением из подмассива, огражденного слева элементом массива с индексом, соответствующим значению счетчика.


Рисунок 1 - Блок-схема алгоритма сортировки посредством простого выбора
Теперь перейдем непосредственно к кодированию этого алгоритма на языке C++ с помощью компилятора C++Builder 6. Для реализации тестирования нашего алгоритма необходимо использовать шаблон функции С++. Реализация такого шаблона представлена в программе 1.
Программа 1.

#include // подключение модулей

#include // ……………..

#include // ……………..

template < class Type, int size > // объявлениешаблона

int sort( Type (&array)[size] ) // объявлениефункции

{

struct time t; // объявление переменной типа time

int t1, t2, ti; // объявление переменных для расчета времени

работы цикла 1

gettime( &t ); // возвращение системного времени

t1 = t.ti_hund; // запись сотых долей секунды системного времени в

переменную t1

int k = 0, j = 0; // объявление счетчика

Type min = array[0], buf; // объявление переменных для поиска

минимума и перестановки элементов

for( int x = 0; x < size; ++x ){ // цикл 1

k = x; // установка счетчика

min = array[x]; // установка нового значения минимума

for( int i = x+1; i < size; ++i ) // цикл 2 для поиска минимума в

массиве

if( min >= array[i] ){

min = array[i];

j = i; // запоминание позиции минимума в массиве

}

buf = array[k]; // перестановка минимума на позицию k

array[k] = array[j]; //

array[j] = buf; //

}

gettime( &t ); // получение системного времени

t2 = t.ti_hund; // запись сотых долей секунды

системного времени в переменную t2

ti = abs( t2 -t1 ); // вычисление времени выполнения цикла 1

return ti;

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

Наша функция sort будет не только сортировать массив, но и возвращать время сортировки в формате сотых долей секунды. Поэтому для проведения тестирования нашего алгоритма далее в программе 2 с помощью функции main мы будем конкретизировать наш шаблон.
Программа 2.

#include

#include

#include
int main()

{

// задание переменных для вычисления среднего времени

int inttime[15];

float avtime = 0;

// задание размера сортируемого массива

const int size = 100;

// заполнение массива целых чисел

int ia[size];

for(int x = 0; x < size; ++x ){

randomize();

ia[x] = random( 100 );

}

// конкретизация шаблона для массива типа int

cout << "sort time for ia[" << size << "] { ";

for(int x = 0; x < 15; ++x ){

inttime[x] = sort( ia );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

float fa[size];

for(int x = 0; x < size; ++x ){

randomize();

fa[x] = log( random( 100 ) + 1 );

}

// конкретизация шаблона для массива типа float

avtime = 0;

cout << "sort time for fa[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( fa );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

char ca[size];

for (int x = 0; x < size; ++x ){

randomize();

ca[x] = random( 64 ) + 62;

}

// конкретизация шаблона для массива типа char

avtime = 0;

cout << "sort time for ca[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( ca );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

string sa[size];

string samp = "deathisjustanotherpathonethatweallhavetotake";

int bag, fag;

string dag = "int";

for ( int x = 0; x < size; ++x ) {

bag = random( 44 );

fag = random( 44 );

sa[x] = dag + samp[bag] + samp[fag];

}

// конкретизация шаблона для массива типа string

avtime = 0;

cout << "sort time for sa[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( sa );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

cin.get();

return 0;

}

//---------------------------------------------------------------------------

4. 2.3 Тестирование алгоритма

В данном разделе мы приступим к тому, для чего непосредственно создавалась наша программа - мы будем тестировать наш алгоритм. Для этого вновь обратимся к уже полученным формулам скорости выполнения алгоритма и попытаемся сопоставить полученные путем эксперимента данные с теоретическим обоснованием нашего алгоритма.

Будем уверены, что наша программа соответствует оптимизированному варианту алгоритма сортировки посредством простого выбора. Как мы отмечали, среднее время выполнения такого алгоритма составляет порядка . Также мы ссылались на число пересылок и отмечали, что его максимальное значение может быть порядка . И будем опираться на то, что зависимость скорости выполнения практически всех простых алгоритмов внутренней сортировки, которые можно считать рациональными, при большом количестве сортируемых элементов стремиться к порядку . Теперь вернемся к нашей программе. Путем варьирования константы size мы будем получать различные значения функции sort. Определив константу size значение 100, мы получим выведенное на консоль среднее из пятнадцати значений время сортировки для массивов различного типа (рис 4).


Рисунок 1 – Консоль вывода времени сортировки
Как видно 100 это слишком малое количество записей в массиве, поэтому в дальнейшем мы будем увеличивать это значение, начиная с 0 с шагом в 500. Запуская программу для каждого размера массива и выбирая среднее из полученных значений времени, мы получили следующую таблицу данных.
Таблица 1 – Время сортировки массива

	количество элементов в сортируемом массиве
тип данных	0	100	500	1000	1500	2000	2500	3000	3500	4000	4500	5000
int	0	0	0.06	0.4	0.86	1.53	2.4	3.46	4.6	6.2	7.1	7.5
float	0	0	0.13	1.1	3	5.1	7.4	9.4	11.7	12.9	13.9	14.7
char	0	0	0.06	0.4	0.9	2	3	4.1	5.6	7.3	8.4	9
string	0	4.4	9.2	12.8	17	20.1	23.5	26.7	28.7	30	31.2	32

На основании данной таблицы можно вывести закономерности и составить график зависимость времени сортировки массива от размера этого массива для четырех типов данных (рис 4).



Рисунок 1 – График зависимости времени сортировки от числа элементов

6. 3. Итоги анализа алгоритма

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

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

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

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

8. Заключение

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

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

1. 
   Среднее время выполнения алгоритма
   
2. 
   Наибольшее значение времени выполнения алгоритма
   
3. 
   Объем занимаемой оперативной памяти
   
4. 
   Скорость оперирования сортируемыми данными
   
5. 
   Специфичность области и среды применения алгоритма
   

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

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

10. Список используемых источников

1. 
   Д. Кнут. Искусство программирования. М.: перевод на русский язык «Мир» 1978. 202 с.
   
2. 
   С.Д. Кузнецов. Методы сортировки и поиска. М.: Наука 1987.
   
3. 
   Стенли Б. Липман. Язык программирования С++. СПб.: «Невский диалект» 2003 перевод на русский язык А. Слинкин.
   

1^Исследование алгоритма простого выбора «Сортировка и выбор» Д. Кнут [1].

2^Метод выбора «Методы сортировки и поиска» С.Д. Кузнецов [2].