к этому доказательству. Задание предусловия
Приведу некоторые пояснения к этому доказательству. Задание предусловия и постусловия процедуры QSort достаточно очевидно - сортируемый массив должен быть не пустым, а после работы метода должен быть отсортированным. Важной частью обоснования является четкое введение трех множеств - S1, S2, S3 - и условий, накладываемых на их элементы. Эти условия и становятся частью инварианта, сохраняющегося при работе различных циклов нашего метода. Вначале множества S1 и S3 пусты, в ходе вычислений пустым становится множество S2. Так происходит формирование подзадач, к которым рекурсивно применяется алгоритм. Особым представляется случай, когда множество S1 тоже пусто. Нетрудно показать, что эта ситуация возможна только в том случае, если случайно выбранный элемент множества, служащий критерием разбиения исходного множества на два подмножества, является минимальным элементом.
Почему обоснование полезно практически? Дело в том, что в данном алгоритме приходится следить за границами множеств (чтобы они не пересекались), за пустотой множеств (служащих условием окончания циклов), за выполнением условий, накладываемых на элементы множеств. Если явно не ввести эти понятия, то вероятность ошибки существенно возрастает. В заключение следует все-таки привести результат сортировки хотя бы одного массива.
Рис. 10.3. Результаты быстрой сортировки массива
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий