Page 77 - Bkhargava_-_Grokaem_algoritmy

76 Глава 4. Быстрая сортировка

шем арсенале. Столкнувшись с новой задачей, не впадайте в ступор. Вместо
этого спросите себя: «А нельзя ли решить эту задачу, применив стратегию
"разделяй и властвуй"?~
К концу этой главы вы освоите свой первый серьезный алгоритм «разделяй
и властвуй~: быструю сортировку. Этот алгоритм сортировки работает на­
много быстрее сортировки выбором (о которой рассказывалось в главе 2).
Он является хорошим примером элегантного кода.

«Разделяй и властвуй»

Возможно, вы не сразу поймете суть стра­
тегии «разделяй и властвуй~, поэтому
мы рассмотрим три примера. Сначала
я приведу наглядный пример. Потом мы
разберем пример кода, который выгля­
дит не так красиво, но, пожалуй, вос­
принимается проще. В завершение будет
рассмотрена быстрая сортировка - алгоритм
сортировки, использующий стратегию «разделяй
и властвуй~.

Представьте, что вы фермер, владеющий земельным участком.

1&60 м

:·.~;· ',~ ~•'''•'')·"·' 1) , •• ".' ,,1' ''• l'•'i
1
1
1
1 1
11\1, :,,".'''( ~.'1•;.', •••• ,·: ,··f'''. ,\ 1•,
;,,,,,, ~111,, 1,,,,, ., .• 1,, ••••••• 1,•,,
'•(' •1·1/'•· ······'''••''''''
J~J. '''1.• 1'1•'''' .,.,,1··~'·'"···· ·'•
1
11 1,1•'',•i,, ,, ,, '.':' .:~·.' r;., ·,•'1:1 6110 м
,,1,,,J,,,• '1/ i ,., ,, ·' ,", •,,•,, '••','.
,,,,, 1 1'. 1 ,1 1. ''• J •,, •• ·~.~~·~'.•,'•,'
1 / i •); ~ J, 1 ' '. ,, ''t •',, • , '.. 1 ••• , .,
/ ' / '., '/ \ \ , \ '',, ·,· ' • ,, •• • 1,,,' .~ :~:·.· ,< •.
'1 1
1_,•1 " / ,,, '•'•»•' ,.1,,,,,,,,,.,.,•,'
'
'
1
"' "
{
•
'
' /
, • , '
1,, , '.,. \. , ••.• \ ,,'\'•\·,•"',
l••J, 1 ~"' •' •/ ••• •"' ,,' 1 ,'\·,• •• , •• ,,,,, ",,
Вы хотите равномерно разделить землю на одинаковые квадратные участ­
ки. Участки должны быть настолько большими, насколько это возможно,
так что ни одно из следующих решений не подойдет.
www.trk.kg