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

Маргинальные свойства простых сортировок целочисленных массивов
7
Таким образом, маргинальные свойства сортировки методом пар-
ных сравнений оцениваются суммированием числа операций на всех
этапах:
2
min 1 2 min 1 2 3 ; SortPair SortPair SortPair
W W W n n      
2
max 1 2 max
5 15
1 .
2 2
SortPair SortPair SortPair
W W W n n      
Сравнивая минимальные результаты сортировки методов пере-
становки и парных сравнений (пузырька) для уже упорядоченного
исходного массива, получаем, что быстродействие сортировки мето-
дом парных сравнений выше, чем быстродействие сортировки мето-
дом перестановки:
2 2
min min 1 2 3 2 3 3 . SortPair SortExchange W n n W n n         
В случае когда элементы исходного массива расположены в об-
ратном порядке, быстродействие сортировки методом выбора выше,
чем быстродействие сортировки методом парных сравнений (n > 2):
2 2
max max
5 15 21 7
1 10 .
2 2 2 2
SortPair SortChoice W n n W n n         
Сортировка модифицированным методом парных сравнений.
Ниже представлена функция SortPairMod( ), в которой используется
алгоритм предыдущей функции SortPair( ) с добавлением флага:
void SortPairMod(int a[], const int n)
{ int n1 = n – 1;
for (int i = 0; i < n1; i++)
{ bool flag = true;
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;
flag = false;
}
if (flag) break;
}
}
Флаг указывает, была ли перестановка парных значений на оче-
редной итерации главного цикла. Если перестановки не наблюдались,
то массив упорядочен и дальнейшие итерации главного цикла не
нужны, сортировка закончена. Это выгодно для частично упорядо-
ченных массивов, которые редко изменяются. Интерфейс функции
указывает адрес исходного неупорядоченного массива a, содержаще-
го n элементов. После выполнения функции массив a упорядочен по
возрастанию.