Зертханалық жұмыс №9

Тақырыбы:Сұрыптау есебін шешу. Сұрыптау алгоритмдері.

Жалпы мәлімет

Алдыңғы алгоритм сияқты бұл алгоритм де жекелеген қадамдардан тұрады. Әрбір қадамда массивты басынан аяғына дейін көршілес элементтер жұптарын салыстыра отырып, жүріп өтеді. Егер кезекті жұп талап етілетін тәртіпті бұзатын болса, онда оның элементтерінің орындарын ауыстырады. Қадамдарды кезекті жүріс ешқандай ауыстыру шақырмайтындай болғанша қайталай береді.

Мысалы: 5 1 8 4 9 элементтерінен тұратын массивты қарапайым ауыстыру әдісімен өспелі түрде реттейміз. Массивтың ағымдағы бөлігінің ұзындығы n-k+i, k – қарап шығу номері, i – ізделетін жұптың номері, п – k соңғы жұптың номері.

.

Бірінші қарауда барлық массив қарастырылады.

i = l5 4 8 2 9

> ауыстырамыз

i = 24 5 8 2 9

< ауыстырмаймыз

i = 34 5 8 2 9

> ауыстырамыз

i = 44 5 2 8 9

<

9 өзінің орнында тұр.

Екінші қарау: массивты бірінші элементтен төртінші элементке дейін қарастырамыз.

i = 14 5 2 8 9

< ауыстырмаймыз

i = 24 5 2 8 9

> ауыстырамыз

i = 34 2 5 8 9

< ауыстырмаймыз

8 өзінің орнында тұр.

Үшінші қарау: массивтың қарастырылып отырған бөлігі алғашқы үш элементті қамтиды.

i = 14 2 5 8 9

> ауыстырамыз

i = 22 4 5 8 9

< ауыстырмаймыз

5 өзінің орнында тұр.

Төртінші қарау: соңғы жұпты қарастырамыз.

i = 12 4 5 8 9

< ауыстырмаймыз

4 өзінің орнында тұр.

Ең кіші элемент (2) үшін тек бірінші орын ғана қалады.

Сөйтіп, массив қарапайым ауыстыру әдісімен өсу ретімен орналастырылды. Бұл әдіс сондай-ақ, «көпіршік әдісі» деп аталады. Бұл атау неғұрлым «жеңіл» элементтер аз-аздап бетіне, жоғары жүзіп шығатын процестің бейнелік интерпретациясынан келіп шығады.

Бақылау сұрақтары:

1. Массивтың екі элементінің орынын қалай ауыстырады?

2. Кірістірілген циклдар деген не?

3. Қарапайым таңдау әдісі мен қарапайым ауыстыру әдісінің айырмашылығы қандай?

Тапсырмалар варианттары:

Енгізілетін мәліметтер (алғашқы массив) пен шығатын мәліметтерді (сұрыпталған массив) бүтін сандардан тұратын текстік файл ретінде қалыптастыру керек.

Барлық варианттарға «көпіршік» сұрыптау процедурасын қолдану керек.

1. Ең жақсы және ең жаман жағдайлардағы орындалған ауыстырулар мен салыстырулар санын есепте.

2. Берілген қатардың n алғашқы элементтерін өсу реті бойынша орналастыр. Осы элементтерді кему реті бойынша басып шығар.

3. Біздің мысалымызда соңғы екі элемент сұрыпталған болғандықтан элемнеттер ретіне ешқандай әсер етпейді. Сондықтан, біздің алгоритмді қандай бір жүрісте элементтер ауыстырылды ма, соны есте сақтау арқылы жақсартуға болады. Егер болмаса, сұрыптауды аяқтауға болады.