Введение

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

Цель исследования

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

Материал и методы исследования

В работе, при описании задачи сортировки массива из 1, 2 … п элементов, принимаем известную формулировку [1]: пусть требуется упорядочить массив элементов: R1,R2,…,Rn, в котором каждый элемент представляет собой запись Rj, содержащую некоторую информацию и ключ Kj, управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей a,b,c выполнялись следующие условия:

· закон трихотомии: либоa<b, либоa>b, либоa=b;

· закон транзитивности: еслиa<bиb<c, тоa<c.

В этом приближении задача сортировки сводится к нахождению такой перестановки записей p(1)p(2)…p(n), после которой ключи a,b,c расположились бы в порядке не убывания: Kp(1)⩽Kp(2)⩽⋯⩽Kp(n).

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

Оценка достоверности полученных результатов затрат машинного времени на выполнение сортировки множества оценивалась путем сравнения с известными теоретическими зависимостями, а именно асимптотической нотацией O(n), O(n2) или O(n×log(n)) представляющей собой зависимость скорости выполнения программы от размера входного массива. Следует отметить, что асимптотическая нотация как математическая форма записи зависимости времени сортировки хоть и даёт более широкое представление о временных затратах на упорядочивание данных, но не даёт вещественных значений, в работе выполнена попытка получить среднестатистический результат затрат времени на различные типы сортировок, путём замера результатов запуска различных случаев начального массива и различных сортировок. Для измерения скорости работы алгоритмов сортировок выбран язык программирования Python, база готовых решений в области сортировки которого позволяет выполнить сортировку массивов данных всеми рассмотренными выше способами. Оценка затрат машинного времени на выполнения операции сортировки выполнялась с встроенным модулем [5] time языка программирования Python, позволяющим выполнить фиксацию значений времени до и после выполнения кода. Оценка погрешности затрат времени на реализацию алгоритмов сортировки массивов выполнялась посредством сортировки для каждого случая не менее чем 100 одинаковых массивов с последующим определением среднего значения времени выполнения операции сортировки и определения диапазон максимальных отклонений от него.

Результаты исследования и их обсуждение

Результаты оценки затрат машинного времени приведены в табл. 1. и на рис. 1-5. Из приведенных результатов видно, что результаты вычислительного эксперимента качественно

Таблица 1 – Затраты машинного времени на сортировку, с

а

б

в

Рисунок 1 –Сортировка пузырьком:

а – в I массиве; б – в II массиве; в - в III массиве.

а

б

в

Рисунок 2 –Сортировка перемешиванием: а – в I массиве; б – в II массиве; в - в III массиве.

а

б

в

Рисунок 3 –Сортировка вставками: а – в I массиве; б – в II массиве; в - в III массиве.

а

б

в

Рисунок 4 –Сортировка слиянием: а – в I массиве; б – в II массиве; в - в III массиве.

а

б

в

Рисунок 5 –Сортировка двоичным деревом: а – в I массиве; б – в II массиве; в - в III массиве.

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

Вывод

В работе, на ноутбуке с высокопроизводительным мобильным процессором AMD Ryzen 7 линейки Hawk Point c тактовой частотой 3.8 ГГц., выполнен сравнительный анализ затрат машинного времени на реализацию, на языке программирования Python, наиболее распространенных алгоритмов сортировки массивов. Показано, что для массивов с худшим сценарием расположения элементов затраты машинного времени возрастают от 4,47×10-4 с. до 4,05 с., и для лучшего сценария возрастают от 5,19×10-6 с. … 7,07×10-4 с. Затраты машинного времени для сортировки перемешиванием составляют 3,89×10-4 с. … до 3,68 с. и 5,01×10-6 с. … 6,69×10-4 с., для сортировки вставками 2,11×10-4 с. … до 1,90 с. и 1,01×10-5 с. … 1,28×10-3 с., для сортировки слиянием от 1,66×10-4 с. … 2,44×10-2 с. и 1,42×10-4 с. … 2,18×10-2 с. , для сортировки с помощью двоичного кода 5,59×10-4 с. … 6,86 с. и 1,12×10-4 с. … 1,62×10-2 с. соответственно. Оценка эффективности работы алгоритмов по реализации методов сортировок показала, что в случайном массиве быстрее всего является сортировка двоичным деревом, а самой медленной оказалась сортировка пузырьком.