Телефон: 8-800-350-22-65
Напишите нам:
MAX:
WhatsApp:
Telegram:
Прием заявок круглосуточно
График работы офиса: с 9:00 до 23:00 Нск (с 5:00 до 19:00 Мск)

Статья опубликована в рамках: CLXVII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 05 ноября 2026 г.)

Наука: Информационные технологии

Скачать книгу(-и): Скачать книгу

Библиографическое описание:
Яо Ш. ВЛИЯНИЕ ИСХОДНОЙ УПОРЯДОЧЕННОСТИ МАССИВА НА ЧИСЛО СРАВНЕНИЙ ПРИ СОРТИРОВКЕ ВСТАВКАМИ И СЛИЯНИЕМ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. CLXVII междунар. студ. науч.-практ. конф. № 11(165). URL: https://sibac.info/archive/studconf/tech/v2/ce57467711a356f61351de6d25e1f54a/11(165).pdf (дата обращения: 19.11.2026)
Проголосовать за статью
Идет голосование
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

ВЛИЯНИЕ ИСХОДНОЙ УПОРЯДОЧЕННОСТИ МАССИВА НА ЧИСЛО СРАВНЕНИЙ ПРИ СОРТИРОВКЕ ВСТАВКАМИ И СЛИЯНИЕМ

Яо Шуайпэн

студент 4-го курса, направление Прикладная математика и информатика, Политехнический институт, Новгородский государственный университет имени Ярослава Мудрого, РФ, г. Великий Новгород

Введение

Сортировка применяется при обработке списков, поиске записей и подготовке данных к анализу. При выборе алгоритма важно учитывать не только размер массива, но и расположение элементов до сортировки. В работе сравниваются сортировка вставками и сортировка слиянием. Первый алгоритм последовательно помещает очередное значение в отсортированную часть массива. Второй делит массив на части, сортирует их и объединяет в общий упорядоченный список [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. Полученные значения согласуются с теоретическими оценками трудоемкости. При практическом выборе алгоритма следует учитывать характер входных данных, а не только их объем.

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

  1. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 4th ed. Cambridge, MA: MIT Press. – 2022. – 1312 P.
  2. Sedgewick R., Wayne K. Algorithms. 4th ed. – Boston: Addison-Wesley Professional, 2011. – 976 P.
Проголосовать за статью
Идет голосование
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов