Статья опубликована в рамках: CLXVII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 05 ноября 2026 г.)
Наука: Информационные технологии
Скачать книгу(-и): Скачать книгу
дипломов
ВЛИЯНИЕ ИСХОДНОЙ УПОРЯДОЧЕННОСТИ МАССИВА НА ЧИСЛО СРАВНЕНИЙ ПРИ СОРТИРОВКЕ ВСТАВКАМИ И СЛИЯНИЕМ
Введение
Сортировка применяется при обработке списков, поиске записей и подготовке данных к анализу. При выборе алгоритма важно учитывать не только размер массива, но и расположение элементов до сортировки. В работе сравниваются сортировка вставками и сортировка слиянием. Первый алгоритм последовательно помещает очередное значение в отсортированную часть массива. Второй делит массив на части, сортирует их и объединяет в общий упорядоченный список [1; 2].
Цель работы — оценить, как исходный порядок целых чисел влияет на количество сравнений элементов. Время выполнения здесь не используется: оно зависит от оборудования, языка программирования и особенностей реализации. Число сравнений позволяет сопоставить алгоритмы при одинаковых входных данных.
Материалы и методы
Для эксперимента сформированы массивы длиной 100, 500 и 1000 элементов. Каждый массив содержит целые числа от 0 до n − 1 без повторений. Для каждого размера рассмотрены три варианта: элементы уже расположены по возрастанию, размещены в случайном порядке или расположены по убыванию. Случайные перестановки генерировались 20 раз с фиксированными начальными значениями генератора, что позволяет воспроизвести результаты.
Для сортировки вставками подсчитывалось каждое сравнение элемента отсортированной части массива с текущим ключом, в том числе последнее сравнение, прекращающее сдвиг. Для сортировки слиянием учитывались сравнения первых оставшихся элементов двух объединяемых частей. Проверка границ массива и присваивания в подсчет не входили. Все реализации проверялись сравнением результата со стандартной сортировкой Python.
Оценка трудоемкости известна из теории алгоритмов: вставки имеют порядок O(n) для уже отсортированного массива и O(n²) в худшем случае; сортировка слиянием сохраняет порядок O(n log n) для всех трех вариантов [1; 2]. Эти оценки относятся к скорости роста числа операций, а не к точному времени в секундах.
Результаты исследования
Результаты приведены в таблице 1. Для случайных массивов показано среднее значение по 20 перестановкам; для упорядоченных вариантов вычисление выполнялось один раз. Средние значения округлены до целых.
Таблица 1.
Количество сравнений элементов при двух способах сортировки
| Размер | Порядок данных | Вставки | Слияние |
|---|---|---|---|
| 100 | Возрастание | 99 | 316 |
| 100 | Случайный порядок | 2 552 | 543 |
| 100 | Убывание | 4 950 | 356 |
| 500 | Возрастание | 499 | 2 216 |
| 500 | Случайный порядок | 63 569 | 3 858 |
| 500 | Убывание | 124 750 | 2 272 |
| 1000 | Возрастание | 999 | 4 932 |
| 1000 | Случайный порядок | 251 928 | 8 714 |
| 1000 | Убывание | 499 500 | 5 044 |
В отсортированном массиве вставки требуют только n − 1 сравнение: каждый очередной элемент сразу остается на своем месте. При обратном порядке каждый элемент последовательно сравнивается со всеми предыдущими, поэтому число сравнений равно n(n − 1)/2. Для n = 1000 получены 999 и 499 500 сравнений соответственно. Это различие вызвано исходным порядком данных, а не изменением размера массива.
Сортировка слиянием заметно меньше зависит от первоначального расположения элементов. При n = 1000 число сравнений изменялось от 4 932 до 8 714. При случайном порядке алгоритм слияния выполнил приблизительно в 29 раз меньше сравнений, чем вставки (8 714 против 251 928). Однако на уже отсортированных данных вставки оказались экономнее: 999 сравнений против 4 932.
Следовательно, при предварительно упорядоченных небольших наборах данных сортировка вставками может быть удобна благодаря простоте и небольшому числу сравнений. Для больших массивов с неизвестным расположением элементов сортировка слиянием обеспечивает более устойчивое поведение. Окончательный выбор в прикладной задаче также зависит от объема дополнительной памяти и затрат на перемещение элементов: в данном эксперименте эти показатели не измерялись.
Заключение
Вычислительный эксперимент подтвердил влияние исходной упорядоченности на число сравнений. Для сортировки вставками при n = 1000 этот показатель менялся от 999 до 499 500, тогда как для сортировки слиянием находился в пределах 4 932–8 714. Полученные значения согласуются с теоретическими оценками трудоемкости. При практическом выборе алгоритма следует учитывать характер входных данных, а не только их объем.
Список литературы
- Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 4th ed. Cambridge, MA: MIT Press. – 2022. – 1312 P.
- Sedgewick R., Wayne K. Algorithms. 4th ed. – Boston: Addison-Wesley Professional, 2011. – 976 P.
дипломов

