Ќазаќ мемлекеттік ќыздар педагогика институты
жүктеу/скачать 1,32 Mb.
|
- Бұл бет үшін навигация:
- Дәріс №23. Сұрыптаудың альтернативті әдістері. (Сұрыптаудың жетілдірілген әдістері)
| Әдебиеттер
Негізгі әдебиеттер: 8 [189-214], 3 [60-75] Қосымша әдебиеттер: 5[86-89] – б, 9[63-67] – б. Бақылау сұрақтары Жиын элементтерінің саны нешеден артпауы керек? Жиын элементі деген не? Жиынның базалық типі деген не? Паскаль типінде жиын элементтерінің мәндері қандай белгімен көрсетіледі? Жиындарға қолданылатын амалдарды ата? Жиындардың бірігуі, қиылысуы, айырымы деген не? Дәріс №23. Сұрыптаудың альтернативті әдістері. (Сұрыптаудың жетілдірілген әдістері) Кемімелі қашықтықпен қосу көмегімен сұрыптау. Тармақ көмегімен сұрыптау НeapSort программасын талдау. Бөлудің көмегімен сұрыптау. Жылдам сұрыптау әдісін талдау. Массив элементттерін сұрыптау әдістерін салыстыру Кемімелі қашықтықпен қосу көмегімен сұрыптау 1959 жылы Д.Шелл тікелей қосу көмегімен сұрыптауды ұсынды. Алдымен бір-бірінен 4 элементке қашық тұрған элементтер топталып, сұрыпталады. Мұндай процесс төрттік сұрыптау деп аталады. Біздің мысалда 8 элемент қарастырылады, әрбір топ екі элементтен тұрады. Бірінші електен өткізуден кейін элементтер қайта топтастырылады. Енді әрбір элементтер тобы бір-бірінен екі орын қашықтықта орналасады да, қайта сұрыпталады. Бұл екілік сұрыптау деп аталады. Ал, үшінші електен өткізуде әдеттегі бірлік сұрыптау жүзеге асады. Бір қарағанда бұл алгоритмде егер бірнеше сұрыптау процесі қажет болса, әрқайсысында барлық элементтер қамтылса, үнемдеудің орнына жұмыс көбейген тәрізді болып көрінеді. Дегенмен, әрбір кезеңде не салыстырмалы түрде аз элементтер сұрыпталады, немесе барлық элементтер барынша реттелген және салыстырмалы түрде аздаған орын ауыстырулар талап етіледі. Бұдан мұндай әдіс нәтижесінде реттелген сұрыптаулар реттелген массив береді және әрбір електен өткізу алдыңғысынан тек ұтады (өйткені әрбір і-сұрыптау 2і-ші сұрыптаумен сұрыпталған 2 топқа біріктіреді). Сондай-ақ, топтағы қашықтықты бірнеше жолмен азайтуға болады, әйтеуір соңғысы жалғыз болуы тиіс. Кем дегенде соңғы електен өткізу барлық жұмысты орындайды. Барлық t қашықтықтар сәйкес h1,h2,…,ht арқылы белгіленіп, олар үшін мына шар орындалады: Ht=1, hi+1 Мұнда әрбір h сұрыптау тікелей қосу көмегімен орындалатын сұрыптау тәрізді программалаланады. Қосу үшін орынды іздеуді аяқтау шартының қарапайымдылығы барьер әдісімен қамтамасыз етіледі. Сұрыптаудың әрқайсысы өзіне тән барьерін қоюды талап етеді, оның орнын анықтау үшін сұрыптаудың әрқайсысы өзіне тән барьерін қоюды талап етеді, оның орнын анықтау үшін программаны барынша қарапайым жасау қажет. Сондықтан массивті тек бір а0 компонентіне ғана емес, h1 компонентке кеңейтуге тура келеді. Оның жазылу түрі төмендегідей: A: array[-h1..n] of integer. Бұл алгоритмді талдайтын болсақ, қандай қашықтық жақсы нәтиже береді. Мұнда әрбір електен өткізуде екі тізбек бұғанға дейін ешқашан қиылысқан емес. Бұл жағдайда мына теореманы қолдануға болады: егер К сұрыпталған тізбекті і рет сұрыптасақ та, ол К сұрыпталған болып қалады. Мұны Кнеут өз еңбектерінде былай дәлелдеп көрсетеді: 1, 4,13, 40, 121, ... , мұндағы hk-1=3hk+1, ht=1 және t=[log3n]-1 Тізбегін пайдаланудың мағынасы бар. Ол тағы да басқа тізбекті ұсынады: 1 3, 7, 15, 31, ... , мұндағы hk-1=2hk+1, ht=1, ал t=[log2n]-1. Шелл әдісімен n элементті сұрыптау жағдайында шығын n1.2-не пропорционал екенін математикалық талдау дәлелдеп көрсетеді. Сонымен бұл алгоритм тағы да жетілдіруді талап етеді. Тармақ көмегімен сұрыптау Тікелей таңдаудың көмегімен сұрыптау n элементтер мен қалған n-1 және т.б. элементтердің ішінен қайталанатын ең кіші элементті іздеуге негізделеді. N элементтің ішінен ең кішісін табу n-1 салыстыру; ал, n-1 үшін n-2 салыстыру және т.б. талап етіледі. Алғашқы n-1 сандардың қосындысы ½( n2- n)-ге тең. Мұны қалай орындауға болады. Мысалы, n/2 салыстыруды орындап, әрбір жұп кілттегі кішісін анықтауға болады. n/4 салыстырудың көмегімен таңдалған кіші жұптардың ішіндегі кішісін т.с.с. табуға болады. n-1 салыстыру жасап, таңдау тармағын схема түрінде тұрғызуға болады. Мұнда түбірді бізге қажетті ең кіші кілт ретінде белгілеуіміз қажет. Сұрыптаудың екінші кезеңі – ең кіші элемент ретінде белгіленген жолдың бойымен төмен түсіп, ең төменгі деңгейге дейін оны бос элементпен алмастыру жолымен осы тармақтан шығару немесе аралық төбедегі көрші тармақтың элементімен алмастыру. Сонымен, тармақтың түбіріне келген элемент тағы да ең кіші кілт болып есептеліп, ол да шығарылады. Осындай n қадамнан кейін тармақ бос болып қалады да, сұрыпта упроцесі аяқталады. Мұнда мына мәселеге көңіл аудару қажет: әрбір n қадамдағы таңдауда тек log n салыстыру талап етіледі. Сондықтан барлық процесс үшін n*log n қарапайым операциялар ретімен қатар, тармақ құруға тағы да n қадам қажет. Бұл тек n2-ты талап ететін тікелей әдісті жетілдіру ғана емес, n1.2 қадамды талап ететін Шелл әдісін жетілдіру болып табылады. Қосымша ақпаратты сақтау есепті кеңейтік жібереді, сондықтан тармақ бойынша сұрыптауда әрбір жеке қадам күрделене түседі. Сонымен, шамадан тыс ақпаратты сақтау үшін қандай да бір тармақ түріндегі құрылым құрылады. Біздің келесі міндет – осы ақпаратты тиімді ұйымдастыру болып табылады. Дербес жағдайда, бос ақпараттардан құтылу қажет, қажет емес көптеген салыстыруларды шығаратын тармақтар толтырылады. Сонымен қатар, n бірлік жадыны қажет ететін n элементтен тұратын тармақты ұсыну қажет. Бұл әдіс Д. Уилльямс ұсынған HeapSort әдісінде жүзеге асырылды. Тармақтардың көмегімен дәстүрлі сұрыптау айтарлықтай жаңартылды. Мұнда пирамида hL,hL+1, … ,hR кілттер тізбегі түрінде анықталады, ол мына шарттарды қанағаттандырады: hi<=hLi және hi<=hLi+1, мұндағы і=L,…,R/2. Кез келген екілік тармақты төмендегідей массив ретінде қарастыруға болады: Онда 7 элементтен тұратын пирамиданы былай қарастыруға болады: Мұндағы h1 ең кіші элемент, h1=min(h1, h2, … , hn). Енді hL+1, … ,hR элементтерімен берілген қандай да бір пирамида болсын. Мұндағы L және R мәндері үшін hL, … ,hR пирамидасын кеңейтетеін жаңа х элементін қосайық. Мына кккк-суретке сол жағынан h1=44 элементін қосайық. Жаңа пирамида төмендегідей ретпен құрылады: алдымен х тармақ құрылымның басына барып орналасады, әр жолы өзіне жақын тұрған екі элементтің кішісінің бағыты бойынша біртіндеп төмен түседі, ал элементтің өзі жоғары қарай жылжиды. Келтірілген мысалда алдымен 06 мен 12, онан кейін 44 орындарымен алмасады. Нәтижесінде төмендегідей тармақ алынады: Бұл жылжу алгоритмін былай тұжырымдауға болады: әрбір қадам сайын алмасатын тіркелген элементтер индексін I,j деп белгілейік. Бұдан жоғарыда келтірілген шарттың өзгермейтінін байқауға болады. Р. Флойд ұсынған пирамиданың «сол жерінде» деп аталатын тәсілінде: h1, h2, … , hn деп аталатын қандай да бір массив беріледі. Ал, hm, … , hn , мұндағы m=(n div 2)+1; I,j индекстері j=2i (немесе j=2i+1) шартын қанағаттандыратындықтан пирамида құрайды. Бұл элементтер сәйкес екілік тармақтың төменгі қабатын құрайды. Олар үшін ешқандай реттілік талап етілмейді. Енді пирамида солға қарай кеңейеді. Әр жолы элемент қосылған сайын ығысу барысында бір элемент қосылып, сол орынға қойылып отырады. Сонымен, n элементтен тұратын пирамиданың қалыптасу процесі төмендегідей сипатталады: L: =(n div 2)+1; While L>1 do L:=L-1; Sift(L,n); End; Тек дербес емес элементтердің ішінен толық реттелген тізбек алу үшін n рет жылжымалы қадам жасау қажет, әрбір қадамнан кейін тармақтың басына ең кіші кезекті элемент шығарылады. Тағы да мынадай сұрақ пайда болады: жоғары қалықтап шыққан элементті қайда сақтауға болады және сол орынға қайта баруға бола ма? Әрине, мұны былай шешуге болады: әр жолы пирамиданың соңғы компонентін алып, (мысалы, бұл х болсын ), пирамиданың жоғарғы элементін босаған орынға орналастырып отыруға болады. Бұл процесті мына процедураның көмегімен сипаттауға болады: Sift Ал, негізгі программа heapSort программасымен алынады. жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу:
|