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

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

16-тема:

Тизмелерди сорттоо

Көпчүлүк учурда керектүү маалыматты издөөнү жеңилдетүү үчүн биз
сорттоону колдонобуз. Мисалы, сөздүктө алфавит боюнча сөздөрдү сорт-
тоо издөөнү жеңилдетет.

Программалоодо сорттоо – бул массивдин элементтерин берилген иретте
жайгаштыруу болуп саналат.

Сорттоо ирети ар кандай болушу мүмкүн: сандар үчүн адатта мааниле-
ринин өсүү (кемүү) тартибинде сорттоо каралат. Мисалы, [3 1 0 5 2 7]
бир өлчөмдүү массивин өсүү тартибинде сорттоодо [0 1 2 3 5 7] массиви
алынат. Символдук берилиштер адатта алфавиттик тартипте сорттолушат.

Негизи сорттоонун көптөгөн ыкмалары ойлоп табылган. Жалпысынан алар-
ды эки топко бөлүп караса болот: 1) жөнөкөй, бирок өтө жай иштөөчү (чоң
массивдер үчүн), 2) татаал, бирок тез иштөөчү.

Сорттоонун эң эле көрсөтмөлүү методдорунун бири болгон – «көбүкчө
методун» карайлы.
Көбүкчө методу (алмаштыруу менен сорттоо)

Бул методдун аты белгилүү физикалык кубулуштан алынган: суудагы аба
көбүкчөсү өйдө көтөрүлөт. Массивди бул ыкма менен сорттоо үчүн, мас-
сивден солдон оңду көздөй коңшу элементтерди экиден салыштырып
өтүү керек. Качан сол жактагы элемент оң жактагысынан чоң болуп калса,
анда алардын ордун алмаштыруу керек. Ошентип 1-өтүштөн кийин эң
чоң элемент тизменин акырына келип калат. Эми тизмени кайрадан иргеп
чыгуу керек. 2-өтүштө эң чоң элемент тизменин аягында тургандыктан аны
салыштырбайбыз. Б.а. салыштыруулардын саны 1ге азаят. Демек, циклдеги
өтүштөрүнүн саны тизменин элементтеринин санынан 1ге аз болот.

4 4 4 4 1
5 5 5 1 4

2 2 1 5 5
1 1 2 2 2
3 3 3 3 3

www.trk.kg