Программалау тілдері туралы


Лекция №9 Статикалық құрылымдар . Іздеу және сұрыптау . Статикалық құрылымдарды қарастыру



бет32/40
Дата15.12.2021
өлшемі0,64 Mb.
#101004
түріПрограмма
1   ...   28   29   30   31   32   33   34   35   ...   40
Байланысты:
ишпей куатындар ушин. Таратпандар-1

Лекция №9

Статикалық құрылымдар . Іздеу және сұрыптау . Статикалық құрылымдарды қарастыру .

Деректердің статикалық құрылымдары —дегеніміз олардың өлшемі программаның бүкіл жұмысы кезінде немесе құрылған сәттен бастап жойылған сәтке дейін өзгеріссіз қалатын құрылымдар . Сұрыптау берілген объектілер жиынын ( сандарды ) ұсынылған реттілікпен қайта теріп орналастыру процесі . Басқаша айтқанда сұрыптау дегеніміз белгілі бір жиынтық элементтерін өсу немесе кему ретімен реттеп орналастыру .

Функционалды жүзеге асыру ерекшеліктері бойынша сұрыптау алгоритмдері топтарға бөлінеді :



- таңдау ( іріктеу ) арқылы сұрыптау ;

- алмастыру арқылы сұрыптау ( айырбастау ) ;



- біріктіру арқылы сұрыптау ;

- тарату арқылы сұрыптау .

Алгоритмді таңдау критерийлері маңызды болып табылады : - орташа сұрыптау жылдамдығы ( орташа уақыт , меншікті жылдамдық ) ; - ең жақсы және нашар жағдайлардағы жылдамдык ( немесе ең аз және ең көп уақыт ) ; - мінез - құлықтың табиғилығы ; - элементтер сәйкес мәндермен ( кілттермен ) ауыса ма ? Сұрыптау жылдамдығы ( немесе уақыты ) салыстыру және алмастыру операцияларының санымен анықталады . Әр түрлі алгоритмдерде жұмыс уақыты деректер құрылымының ( массивтің ) элементтерінің экспоненциалды немесе логарифмдік тәуелділікте болады .

Алмастыру арқылы сұрыптаулар ішіндегі ең қарапайымы көпіршікті сұрыптау . Алгоритмінің сипаттамасы : Екі цикл қолданылады . Сыртқы N - 1 рет өтеді , бұл тіпті ең нашар жағдайда да әрбір элемент өз орнында болады дегенге кепілдік береді . Бұл циклде деректер құрылымының сұрыпталған және сұрыпталмаған бөліктері арасындағы шекара орнатылады ( ығыстырылады ) . Ішкі циклде тікелей салыстыру ауыстыру операциялары орындалады . Элементтерді ауыстыру " үш шелек " әдісімен жүргізіледі : бірінші элементтің мазмұны буферлік айнымалыға орналастырылады , оның орнына екінші элементтің мазмұны және орналастырылады , оның орнына бірінші элементтің буферден " ескі " мазмұны орналастырылады . Сыртқы циклдің әрбір келесі өту жолында ішкі цикл өтетін жолдар саны азаяды ( N - 1 - ден 1 - ге дейін ) . Ішкі циклдың орташа өту саны N / 2 тең деп есептеледі . Сұрыптау процесі " үшбұрышты " сипатта болады ( 1 сурет ) . f , d , a , c , b , е таңбаларынан тұратын символдық массивін қарастырайық . Бағдарлама жұмысы барысында массив келесі түрде өзгереді ( массивтің бастапқы жағдайы және оның сыртқы циклдың әрбір өтуінен кейінгі жағдай ) :





Достарыңызбен бөлісу:
1   ...   28   29   30   31   32   33   34   35   ...   40




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет