«Піл» роботын құрастыру. 5-7 сынып

№1 лабораториялық жұмыс

Тақырыбы: Қарапайым таңдау әдісімен сұраптау

Мақсаты: қарапайым таңдау әәдісімен массивті сұрыптауды зерттеу және осы алгоритмнің тиімділігін бағалау.

Жалпы мағұлмат

Қарапайым таңдау әдісімен сұрыптау келесі қадамдардан жинақталады:
1. Массивтің ең үлкен элементінің нөмірін орнату.
2. Массивтің соңғы элементін ең үлкен элементпен орын ауыстыру.
3. Соңғы элементті қалдырып, массивтің қалдығымен ауыстыру 1 және 2 пункті орындау (яғни соңғы элементсіз массивпен). Массив бір элементке дейін қасқарғанша 3-ші пункті қайталау.

Мысал

Бағдардламаны жобалау тілінде сұрыптау тілін жазайық.

For i := n downto 2 do

Begin

а[1], ..., a[i] – дан максималды мәнін табу керек, ал оның индексін к айнымалысына сақтаймыз, егер i<>k онда a[i] и a[k] орындарын бір бірімен ауыстырамыз;

End;

Міне бес элементті массив мәндері былай өзгереді (30,20,10,50,40)

30 20 10 50 40

30 20 10 40 50

30 20 10 40 50

10 20 30 40 50

10 20 30 40 50

Ең үлкен элементті іздеу өрісінің асты сызылған.

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

1. Массивті сұрыптау астарында қандай түсінік бар?

2.Кему бойынша сұрыптаудан жою бойынша сұрыптаудың қандай айырмашылығы бар?

Тапсырмалар

ЕСКЕРТУ!!! енгізілетін және шығатын мәліметтерді бүтін сандардан тұратын мәтіндік файл түрінде пішіндеу керек.

1. Сұрыптау элементтерді жою арқылы жүретіндей етіп, сұрыптау процедурасын өзгерту.

2. Берілген массивті сұрыптау және массивтегі бірдей сандарды санау.

3. і параметрінің мәні әр қадам сайын өсіп отыру үшін сұрыптау процедурасын өзгерту.

4.Қарапайым таңдау ккөмегімен массивтің жұп элементтерін сссұрыптау.

5. Қарапайым таңдау көмегімен массивтің қолайлы элементтерін сұрыптау.

№2 лабораториялық жұмыс

Тақырыбы: қарапайым айырбастау әдісімен сұраптау

Мақсаты: қарапайым айырбастау әдісімен массивті сұрыптауды зерттеу және осы алгоритмнің тиімділігін бағалау.

Жалпы мағұлмат

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

Мысал

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

бірінші қарау: барлық массив түгелдей қаралады

i = l5 4 8 2 9

ауыстырамыз

i = 24 5 8 2 9

ауыстырамыз <не меняем

i = 44 5 2 8 9

ауыстырамыз <не меняем

i = 34 2 5 8 9

<не меняем

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

i = 22 4 5 8 9

<не меняем

Ең кіші (2) элемент үшін тек бір оорын қалдырылады, яғни бірінші. Міне, біздің массив өсуі бойынша қарапайым айырбастау әдісімен сұрыпталды. Бұл әдіс сонымен бірге көқбіршік деп те аталады («пузырька»).

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

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

2. Қарапайым таңдау мен қарапайым айырбастаудың айырмашылығымен ұқсастығы неде?

Тапсырмалар:

Ескерту!! Енгізілетін және шығарылатын мәліметтерді бүтін сандардан тұратын мәтіндік файл түрінде құру керек!

1. Орындалған салыстырулар мен орын ауыстырулардың жақсы, нашар және орташа мөлшерін санау.

2. Жою юойынша пузірлі сұрыптау процедурасын жазыңыз.

3. n бүтін саны берілген. а және в араларында қанша сан жатыр.

4. ретімен өсуі бойынша қатардағы бірінші n элементін реттеу. Және осы элементтерді ретімен жою арқылы баспаға шығару.

№3 лабораториялық жұмыс

Тақырыбы: тікелей қосу әдісімен сұрыптау

Жұмыстың мақсаты: тікуелей қосу әдісімен массивті сұрыптауды зерттеу және осы алгоритмнің тиімділігін бағалау

Жалпы мағұлмат

Тікелей қосу әдісімен сұрыптау қарапайым таңдау әдісі сияқты қайталанбайтын элементтерден тұратын массив үшін қолданылады.

Осы әдіс бойынша сұрыптау қадамнан кейін қадам яғни бірізді болып жүреді. К-м аралығындағы қадамдар, яғни массивтің бір бөлігінде бірінші элементі k-1 реттелген деп есептеледі, онда . әрі қарай к+й элементерін алу керек және ол үшін реттелген тәртіп бұзылмас үшін массивтің сұрыпталған бөлімінен орын таңдаған жөн, ондай жағдайда мынаны табу керек не . Осыдан кейін табылған орынға a[k] элементін қою керек.

Әр қадам сайын массивтің сұрыпталған бөлігі ұлғайып отырады. Толықтай сұрыпталу орындалу үшін келесі қадамды орындаға болады n-1.

Енді тек сұрақтарға жауап беру ғана қалды, яғни элементтер үшін қолайлы орынды іздеуді қалай сипаттауға болады? Оны келесі үлгімен іске асырамыз::массивтің басына қарай жылжи отырып сол жақтағы орналасқан х элементерін қараймыз. Және а[j] элементтерін қараймыз, j өзгереді k-l дейін.

1. бұндай қарау келесі шарт орындалған жағдайда аяқталады:

• а[j] элементі табылды<х, что говорит о необходимости вставки х между a[j-1] и a[j]; >

• ретпен массивтің сол жақ соңына дейін жету керек те бірізділікпен оң жақ орынға х ті қою керек..

Мысал

For k := 2 to n do

begin

x := a[k]; j := k-1;

{ х ті келесі көрсетілген массивте сәйкес орынға қою керек a[1], …, a[k] }

{ ол үшін циклді ұйымдастырамыз }

{ j 0 және x <= a[j] }

{циклде оң жақта 1 позицияда элементерді араластырамыз}

{циклден шығатын кезд х ті j+1массивіне қоямыз }

end;

Тапсырмалар

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

2. Жою бойынша сұрыптау процедурасын құрыңыз.

3. бүтін сандар қатары берілген. Осы қатардан шығатын ретімен өсуі бойынша барлық әртүрлі сандарды алу керек.