Маргинальные свойства простых сортировок целочисленных массивов - page 10

А.Ф. Деон, Ю.И. Терентьев
10
мированием соответствующего числа операций на всех этапах. В ми-
нимальном случае число операций
min 1 2 min
SortPairMod SortPairMod SortPairMod W W W   
2 6 ,n  
т. е. для уже упорядоченного массива количество операций при сор-
тировке данным методом пропорционально только длине массива.
Проверке подвергаются соседние элементы только один раз.
Максимальный случай дает следующий результат:
max 1 2 max
SortPairMod SortPairMod SortPairMod W W W   
2
4 2 6 .n n    
Сравнивая минимальные результаты сортировки обычного и мо-
дифицированного методов парных сравнений, получаем, что быстро-
действие сортировки модифицированным методом парных сравнений
превосходит быстродействие сортировки обычным методом парных
сравнений:
2
min min 1 2 3 2 6 . SortPair SortPairMod W n n W n       
В максимальном случае быстродействие сортировки методом вы-
бора выше, чем быстродействие сортировки модифицированным ме-
тодом парных сравнений (n > 2):
2 2
max max
21 7
4 2 6 10 .
2 2
SortPairMod SortChoice W n n W n n         
Сортировка методом сдвига. Ниже представлена функция
SortShift( ), в которой позиция текущего упорядоченного элемента
заполняется очередным минимальным значением из неупорядочен-
ной части массива, при этом происходит сдвиг неупорядоченных
элементов до места очередного минимального элемента:
void SortShift(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[k];
for (int m = k; m > i; m--) a[m] = a[m - 1];
a[i] = r;
}
}
Интерфейс функции указывает адрес исходного неупорядоченно-
го массива a, содержащего n элементов. После выполнения функции
массив a упорядочен по возрастанию.