Page 71 - Программирование. Python. Для школьников. bizdin.kg

ТИЗМЕЛЕРДИ СОРТТОО 71

Тандоо методу

Дагы бир популярдуу сорттоо методу – бул тандоо методу. Алгач бардык
массив каралып чыгат, минималдык элемент табылганда ал массивдин эң
башына коюлат. Экинчи жүрүштө калган бардык, б.а. экинчиден баштап
акыркы элементке чейин каралат, кайрадан эң кичине элемент табылат
жана ал 2-орунга жылдырылат. Андан ары 3-элементтен баштап дагы эң
кичине элементи табылат жана 3-орунга жылдырылат, ж.б.у.с. (n-1)-эле-
ментке чейин.

Тизмени тандоо методу боюнча сорттоонун алгоритмин жазалы. Мында i
өзгөрмөсү минималдык элемент жазылган уячанын индексин сактайт, ал
эми j өзгөрмөсү каралып жаткан элементти сактайт.

for i in range(n-1):
n_min = i
for j in range(i+1,n):
if a[j] < a[n_min]:
n_min = j
if i != n_min:
a[i], a[n_min] = a[n_min], a[i]
Бул жерде табылган минималдык элемент өзүнүн ордунда турбаса гана
орун алмашуу жүрөт, б.а. i! = nmin болгондо. Минималдык элементтин но-
мерин издөө циклде аткарылгандыктан, бул сорттоо алгоритми да камтыл-
ган циклди түзөт.
«Тез сорттоо» же quicksort

Көбүкчөлүү сорттоо менен тандоо методу чоң берилиштеги массивдер
үчүн (10000дей элементтер) жай иштейт. Ошондуктан чоң массивдерди
сорттоо үчүн атайын «тез сорттоонун» рекурсивдүү алгоритми колдонулат
(англ. quicksort).

Мында сорттоонун идеясы мындай: алгач массив болжол менен ортосунан
тең экиге бөлүнөт, андан соң сол жак бөлүгүндөгү элементтерден «ортодо
турган» элементтен чоң же ага барабар элементтер тандалып алынат жана
оң бөлүгүнө орун алмаштырылат. Андан ары оң жагы жана сол жагы өзүн-
чө массивдер катары каралат да кайрадан экиге бөлүнүшөт.

www.trk.kg