Программалау тілдері туралы
Лекция №9 Статикалық құрылымдар . Іздеу және сұрыптау . Статикалық құрылымдарды қарастыру
жүктеу/скачать 0,64 Mb.
|
ишпей куатындар ушин. Таратпандар-1
| Лекция №9
Статикалық құрылымдар . Іздеу және сұрыптау . Статикалық құрылымдарды қарастыру . Деректердің статикалық құрылымдары —дегеніміз олардың өлшемі программаның бүкіл жұмысы кезінде немесе құрылған сәттен бастап жойылған сәтке дейін өзгеріссіз қалатын құрылымдар . Сұрыптау берілген объектілер жиынын ( сандарды ) ұсынылған реттілікпен қайта теріп орналастыру процесі . Басқаша айтқанда сұрыптау дегеніміз белгілі бір жиынтық элементтерін өсу немесе кему ретімен реттеп орналастыру . Функционалды жүзеге асыру ерекшеліктері бойынша сұрыптау алгоритмдері топтарға бөлінеді : Бастапқы : - қою арқылы сұрыптау ; - таңдау ( іріктеу ) арқылы сұрыптау ; - алмастыру арқылы сұрыптау ( айырбастау ) ; Қайталама : - есептеу арқылы сұрыптау ; - біріктіру арқылы сұрыптау ; - тарату арқылы сұрыптау . Алгоритмді таңдау критерийлері маңызды болып табылады : - орташа сұрыптау жылдамдығы ( орташа уақыт , меншікті жылдамдық ) ; - ең жақсы және нашар жағдайлардағы жылдамдык ( немесе ең аз және ең көп уақыт ) ; - мінез - құлықтың табиғилығы ; - элементтер сәйкес мәндермен ( кілттермен ) ауыса ма ? Сұрыптау жылдамдығы ( немесе уақыты ) салыстыру және алмастыру операцияларының санымен анықталады . Әр түрлі алгоритмдерде жұмыс уақыты деректер құрылымының ( массивтің ) элементтерінің экспоненциалды немесе логарифмдік тәуелділікте болады . Алмастыру арқылы сұрыптаулар ішіндегі ең қарапайымы көпіршікті сұрыптау . Алгоритмінің сипаттамасы : Екі цикл қолданылады . Сыртқы N - 1 рет өтеді , бұл тіпті ең нашар жағдайда да әрбір элемент өз орнында болады дегенге кепілдік береді . Бұл циклде деректер құрылымының сұрыпталған және сұрыпталмаған бөліктері арасындағы шекара орнатылады ( ығыстырылады ) . Ішкі циклде тікелей салыстыру ауыстыру операциялары орындалады . Элементтерді ауыстыру " үш шелек " әдісімен жүргізіледі : бірінші элементтің мазмұны буферлік айнымалыға орналастырылады , оның орнына екінші элементтің мазмұны және орналастырылады , оның орнына бірінші элементтің буферден " ескі " мазмұны орналастырылады . Сыртқы циклдің әрбір келесі өту жолында ішкі цикл өтетін жолдар саны азаяды ( N - 1 - ден 1 - ге дейін ) . Ішкі циклдың орташа өту саны N / 2 тең деп есептеледі . Сұрыптау процесі " үшбұрышты " сипатта болады ( 1 сурет ) . f , d , a , c , b , е таңбаларынан тұратын символдық массивін қарастырайық . Бағдарлама жұмысы барысында массив келесі түрде өзгереді ( массивтің бастапқы жағдайы және оның сыртқы циклдың әрбір өтуінен кейінгі жағдай ) : жүктеу/скачать 0,64 Mb. Достарыңызбен бөлісу:
|