Page 72 - Программирование. Python. Для школьников. bizdin.kg
P. 72
72 PYTHON ПРОГРАММАЛОО ТИЛИ ТИЗМЕЛЕРДИ СОРТТОО
Бул методдун маңызын түшүнүш үчүн мисал карайлы. Бизге төмөндөгүдөй
массив берилсин:
78 6 82 67 55 44 34
X
Х деп массивдин ортоңку элементин карайлы, б.а. 67. Массивдин сол жа-
гындагы Хтен чоң же ага барабар элементти табабыз. Бул элемент 78 саны.
Бул элементтин индексин L менен белгилейли. Эми Хтен оң жакта турган
эң кичине элементти табалы. Бул 34 саны. Анын индексин R тамгасы менен
белгилейбиз.
78 6 82 67 55 44 34
L R
Эми ушул эки элементтин ордун алмаштырабыз. L өзгөрмөсүн оңго, ал эми
R өзгөрмөсүн солго жылдыруу менен биз ордун алмаштыра турган кийин-
ки түгөйдү табабыз. Булар 82 жана 44 сандары.
34 6 82 67 55 44 78
L R
Орундары алмаша турган кийинки түгөйлөр – 67 жана 55 сандары.
34 6 44 67 55 82 78
L R
Бул орун алмашуудан кийин, андан аркы издөө L өзгөрмөсү R өзгөр-
мөсүнөн чоң болуп калгандыгына алып келет, б.а. массив экиге бөлүнүп
калды. Жыйынтыгында A[L] дин сол жагында жайгашкан массивдин бар-
дык элементтери Х тен кичине же барабар, ал эми A[R]дин оң жагында
жайгашкан бардык элементтер Х тен чоң же барабар.
L R
34 6 44 55 67 82 78
R L
Ошентип, баштапкы массивди сорттоо, массивдин эки бөлүгүн сорттоого,
б.а. ошол эле типтеги эки маселени (бирок кичинекей өлчөмдөгү) чечүүгө
алып келди. Эми ушул алгоритмди массивдин алынган эки бөлүгүнө колдо-
нуу керек: биринчи бөлүгү – 1ден Rге чейинки элементтер, экинчи бөлүгү
- Lден акыркы элементке чейин.
www.trk.kg
