Основная причина медленной работы алгоритма SIS заключается в том, что все сравнения и обмены между ключами в последовательности а1, а2, . . . , аN происходят для пар из соседних элементов. При таком способе требуется относительно большое время чтобы поставить ключ, находящийся не на месте, в нужную позицию в сортируемой последовательности. Естественно попытаться ускорить этот процесс, сравнивая пары элементов, находящихся далеко друг от друга в последовательности.
Рис. 11. Блок- схема алгоритма SIS.
К. Хоор изобрел и весьма эффективно применил эту идею (алгоритм QUICKSORT), сократив среднее время работы алгоритма SIS от порядка О(N2) до порядка О( N ln N). Поясним этот алгоритм следующим примером.
Предположим, что мы хотим отсортировать последовательность чисел из первой строки на рис. 12.
Строк 38 08 16 06 79 76 57 24 56 02 58 48 04 70 45 47 Действие
1 38 47 уменьшение j
2 38 45
3 38 70
4 38 04 >
5 04 38 обмен
6 08 38 увеличение i
7 16 38
8 06 38
9 79 38 >
10 38 79 обмен
11 38 48
12 38 58
13 38 02 >
14 02 38 обмен
15 76 38 увеличение i,>
16 38 76 обмен
17 38 56 уменьшение j
18 38 24 >
19 24 38 обмен
20 57 38 увеличение i,>
21 38 57 обмен,уменьшение
22 04 08 16 06 02 24 38 57 56 76 58 48 79 70 45 47
( 1 2 3 4 5 6) 7 (8 9 10 11 12 13 14 15 16)
Рис. 12. Начальные шаги алгоритма QUICKSORT при сортировке
последовательности целых чисел.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.