Маргинальные свойства простых сортировок целочисленных массивов УДК 681.3.06(075) Маргинальные свойства простых сортировок целочисленных массивов © А.Ф. Деон, Ю.И. Терентьев МГТУ им. <...> Н.Э. Баумана, Москва, 105005, Россия Выполнен сравнительный анализ маргинальных скоростных свойств простых сортировок массивов с учетом операций сравнения, сложения, перестановки и запоминания сортируемых элементов в массивах целых чисел. <...> К простым сортировкам массивов обычно относят сортировки методами выбора, перестановки, парных сравнений, сдвига и вставки [1]. <...> Традиционно их быстродействие оценивают лишь по количеству операций сравнения во время упорядочивания массива. <...> При этом основное внимание уделено двум предельным по количеству операций случаям: минимальному, когда исходный массив уже упорядочен, и максимальному, когда элементы массива расположены в обратном порядке. <...> Метод реализован в рамках функции SortChoice( ), в которой позиция текущего упорядоченного элемента заполняется минимальным текущим значением из неупорядоченной части массива: void SortChoice(int a[ ], const int n) { int n1 = n – 1; for (int i = 0; i < n1; i++) { int k = i; for (int j = i + 1; j < n; j++) if (a[j] < a[k]) k = j; int r = a[i]; a[i] = a[k]; a[k] = r; } } Интерфейс функции указывает адрес исходного неупорядоченного массива a, содержащего n элементов. <...> 1 А.Ф. Деон, Ю.И. Терентьев Скоростные свойства функции SortChoice( ) определяются количеством выполненных операций в теле функции [2]. <...> Сначала выполняется инструкция int n1 = n – 1 для определения количества WSortChoice итераций главного цикла сортировки. <...> В заголовке главного цикла for (int i = 0; i < n1; i++) до начала итераций настраиваются две операции: 1) установка начального значения int i = 0; 2) начальная проверка условия i < n1. <...> Обозначим это количество операций как WSortChoice 2,1 2. <...> Кроме того, на каждой итерации в заголовке цикла выполняются одна операция на очередную <...>