Маргинальные свойства простых сортировок целочисленных массивов
1
УДК 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
элементов. После выполнения функции
массив
a
упорядочен по возрастанию.
