Анализ SelectSort

В противоположность семейству IFSort и MinSort, размеры которых существенно растут с ростом размеров сортируемых строк, SelectSort может сортировать строки любого размера. Будучи по размеру не более, чем IFSort4 или MinSort6, SelectSort может сортировать строки в сотни и тысячи символов. Однако, время выполнения для SelectSort будет зависеть от длины входной строки. Количество шагов в данном случае может быть точно определено. Первое, сосредоточимся на выражениях WHILE, которые появляются в DP 3.1, 3.2, 3.2.1, 3.2.2. Исключая другие детали программы, выражения WHILE в SelectSort могут быть пронумерованы.

Предположим, что имеется N входных символов. Выражение WHILE номер 1 требует N итераций. Второе выражение WHILE также потребует N итераций, потому что F1 укорачивается на 1 символ при каждой итерации. Количество итерации для третьего и четвертого выражений WHILE зависит от номера итерации для выражения WHILE номер 2.

На первой итерации WHILE номер 2, WHILE номер 3 требует N итераций, а WHILE номер 4 – N-1 итераций. На второй итерации для WHILE номер 2, WHILE номер 3 требует N-1 итераций, а WHILE номер 4 – N-2 итераций и т.д. Таким образом, количество итераций будет следующим:

Далее, посчитаем выражения READ и WRITE для каждого блока WHILE

Следовательно, количество выражений READ/WRITE выполняемых SelectSort, будет следующим:

Nrw = 2N + N + 2(N + (N-1) + … + 1) + 2((N-1) + (N-2) + … + 0)

= 5N + 4((N-1) + …+ 1)

= 5N + 4N(N-1)/2

= 5N + 2N² – 2N

= 2N²+3N

Количество выражений READ/WRITE для входных последовательностей различной длины

Очевидно, что количество итераций Nrw в основном определяется составляющей 2N². Мы можем сказать, что количество операций ввода-вывода для данной программы порядка 2N². Т.е. 1000-строка будет сортироваться примерно в 100 раз дольше, чем 100-строка, и т.д. Время работы программы может быть довольно большим для еще более длинных строк.