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

Тақырыбы:Сұрыптау есебін шешу. Ішкі және сыртқы сұрыптаулар.

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

Қарапайым таңдау әдісімен сұрыптау келесі қадамдарға келтіріледі:

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

2. Массивтың ең үлкен және соңғы элементтерінің орындарын ауыстыру.

3. Соңғы элементті жайына қалдырып, 1 мен 2 пунктты массивтың қалғандарына (соңғы элементсіз) қайта орындау.

4. 3 пунктты массивтың қалдығы бір элементке дейін қысқарғанша қайталау.

Мысалы: сұрыптау процедурасын программаларды жобалаудың тілінде (псевдокодта) сипаттаймыз.

For i := n downto 2 do

Begin

Максимальды элементті табу а[1], ..., a[i];

Оның индексын k айнымалысында сақтау;

егер 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. Кему реті бойынша сұрыптаудың өспелі рет бойынша сұрыптаудан айырмашылығы неде?

3. Қарапайым таңдау әдісімен сұрыптау арқылы массив элементтерін сұрыптау идеясын сипатта.

4. Бір қадамды орындау уақыты массивтың реттелмеген бөлігінің өлшеміне неліктен тура пропорционал?

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

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

1. Сұрыптау процедурасын сұрыптау элементтердің кему реті бойынша жүргізілетіндей етіп өзгерт.

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

3. Массивты сұрыпта, массивтегі қайталанбайтын сандардың санын есепте.

4. Сұрыптау процедурасын I параметры мәні әрбір қадамда өсетіндей етіп өзгерт.

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

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

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

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

9. n*m матрицасында бағандарды өсу реті бойынша сұрыпта.

10. Футбол командаларының тізімі және чемпионатта әрбір команда алған ұпайлар саны берілген. Ұпайлар саны бірдей командалар жоқ екендігі белгілі. Жүлдегерлерді басып шығар.

11. Реттелмеген массивте қайталанатын элементтер болуы мүмкін. Бірдей элементтер тобының ішінен біреуін ғана қалдыру керек.

12. Жарсытың турнирлік кестесі А квадрат матрицасы арқылы берілген. Aij әрбір элементі i командасының j командасының қақпасына соққан голдар саны. Диагональ бойымен әрбір команданың орынын орналастыру керек (жеңілістерінің санын алып тастағандағы жеңістер саны бойынша, тең түскен жағдайда соғылған гол мен жіберілген голдардың айырмасы бойынша).