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

Маргинальные свойства простых сортировок целочисленных массивов
5
    1 1 1 1 1
2,3,4 max
0 1 0
7
7 7 1 1 .
2
n n n
SortExchage
i j i i
W n i n n   
   
        
Таким образом, маргинальные свойства сортировки методом
перестановки оцениваются суммированием числа операций на всех
этапах:
1 min 2 min
SortExchange SortExchange SortExchange W W W   
2
2 3 3 ;n n    
max 1 2 max
SortExchange SortExchange SortExchange
W W W   
2 1 13
2 ,
2 2
n n    
где 2 min
SortExchange W и 2 max
SortExchange W объединяют соответствующие опера-
ции на втором этапе.
Сравнивая минимальные результаты сортировки методов выбора
и перестановки для уже упорядоченного исходного массива, получа-
ем, что по быстродействию сортировки метод выбора уступает мето-
ду перестановки:
2 2
min min 10 11 3 2 3 3 . SortChoice SortExchange
W n n W n n         
В максимальном случае быстродействие сортировки методом выбо-
ра выше, чем быстродействие сортировки методом перестановки (n > 2):
2 2
max max
21 7 1 13
10 2 .
2 2 2 2
SortChoice SortExchange
W n n W n n         
Сортировка методом парных сравнений. Ниже представлена
функция SortPair( ), в которой в неупорядоченной части массива
сравниваются соседние элементы для выбора меньшего значения:
void SortPair(int a[], const int n)
{ int n1 = n – 1;
for (int i = 0; i < n1; i++)
for (int j = n1; j > i; j--)
if (a[j] < a[j - 1])
{ int r = a[j];
a[j] = a[j - 1];
a[j - 1] = r;
}
}
Полученное в итоге минимальное значение подсоединяется к
упорядоченной части массива. Интерфейс функции указывает адрес
исходного неупорядоченного массива a, содержащего n элементов.
После выполнения функции массив a упорядочен по возрастанию.