Ќазаќ мемлекеттік ќыздар педагогика институты
жүктеу/скачать 1,32 Mb.
|
- Бұл бет үшін навигация:
- Procedure
| НeapSort программасын талдау. Бұл процедураны элементтер саны аз тізбек үшін пайдалану тиімді емес. Неғұрлым n элементтер сан ыкөп болса, программа соғұрлым тиімді жұмыс істейді. НeapSort сұрыптауы үшін тізбектің бастапқы жағдайында элементтері кері ретпен сұрыпталған тізбек үшін жақсы жұмыс істейді. Егер тізбектің элементтері кері ретпен орналасқан болса, пирамиданың пайда болу фазасы ешқандай орын алмастырудың болуын талап етпейді. Алмастырудың орташа саны шамамен n/2* log(n)-ге тең.
Бөлудің көмегімен сұрыптау Ч.Хоар жылдам сұрыптау әдісін ұсынды (QuickSort). Бұл сұрыптауда тиімді нәтижеге қол жеткізу үшін үлкен қашықтыққа орын ауыстыруды орындау қажет. Бізде кері ретпен орналасқан n элемент бар болсын. Оны n/2 алмастырумен сұрыптау қажет: алдымен сол жақтағы элементті оң жақтағы элементпен орындарымен алмастыру қажет, одан кейін біртіндеп оң жаққа жылжу қажет. Бұл тек элементтер кері ретпен орналасқанда ғана орындалады. Жылдам сұрыптау әдісін зерттеу үшін төмендегідей алгоритмді пайдаланайық. Массивтен қандай да бір Х элементін таңдайық. Массивті сол жақтан бастап, Аі >X элемент табылғанша електен өткіземіз. Одан кейін Аj Procedure QuickSort (var item:DataArray; count:integer); Procedure QS (var l,r:integer; var it:DataArray); var I,j: integer;x,y: :Dataitem; Begin I:=l; j:=r; X:=[it(l+r) div 2] Repeat While it[i] Begin Y:=it[i] It[j]:=y; I:=i+1; j:=j-1; End; Until i>j; If l Begin Qs(l,count, item); End; { } Жылдам сұрыптау әдісін талдау Жылдам сұрыптау әдісін зерттеу үшін бөлу процесі қалай жүріп жатқанын қарастыру қажет. Қандай да бір шекаралық х мәнін таңдап, одан кейін массивті тұтасымен қарап шығу керек. Бұдан nсалыстыру орындалады. Алмастырулар санын төмендегідей ықтималдылық түсініктер арқылы ажыратуға болады. Берілген шекаралық х мәнінде күтілетін алмастырулар операциясының саны тізбектің бөлінген сол жақтағы элементтер санына тең болады, яғни ықтималдылыққа көбейтілген n-1 алмастыру барысында әрбір осындай элемент өзінің өзінің орнына барып түседі. Егер осы элемент осының алдында оң жақта болса, алмаастыру орындалады. Оның ықтималдылығы - (n-(x-1))/n. Сондықтан күтілетін алмастырулар саны х-тің барлық мүмкін болатын шекарасы үшін осы күтілетін мәндердің орташасы болып табылады. М =[Sx: 1<=x<=n: (x-1)*(n-(x-1))/n]/n = [Su: 0<=u<=n-1: u*(n-u)]/n2 = N*(n-1)/2n-(2n2-3n+1)/6n=(n-1/n)/6. Бұл жағдайда әрбір бөлу процесі массивті екі жартыға бөледі және сұрыптау үшін бар болғаны log n електен өткізу талап етіледі. Нәтижесінде жалпы салыстырулар саны n*log n, ал жалпы алмастырулар саны - n*log n/6. Мұның ықтималдылығы 1/ n-ді құрайды. Шекараны кездейсоқ таңдағандағы бұл әдістің орташа өнімділігі алдыңғы келтірілген варианттан 2*ln(2) коэффициентпен ғана ажыратылады. Бұл әдістің де өзіне тән кемшіліктері бар. Олардың ішіндегі негізгілерінің бірі n саны аз болған жағдайдайғы өнімділіктің төмендігі. Ал, бұл әдістің артықшылығына келетін болсақ, шағын бөлікті өңдеу үшін тікелей сұрыптаудың қандай да бір әдісін оңай қосуға болады. Бұл программаның рекурсиялық нұсқасында өте қолайлы. Массив элементттерін сұрыптау әдістерін салыстыру Сұрыптау әдістеріне шолуды аяқтай отырып, олардың тиімділіктерін салыстырып көрейік. N – сұрыпталатын элементтер саны, ал С және М – сәйкес қажетті салыстырулар кілті мен алмастырулар саны. Барлық тікелей сұрыптау әдістері үшін дәл аналитикалық формулаларды беруге болады. Мұндағы Mіn, Avg, Max деп аталатын бағандар n элемент мәндерінен жасалған барлық n! орын ауыстырулардың ең кіші, орташа және ең үлкен мәндері. Жетілдірілген әдістер үшін қандай да бір ойластырылған, қарапайым немесе дәл формулаллар жоқ. Дегенмен, Шелл әдісімен сұрыптау жағдайында есептеу шығыны с*n1.2 болса, ал үймек сұрыптау мен жылдам сұрыптау үшін c*n*logn –ге тең. Мұндағы с – сәйкес коэффициенттер.
Бұл формулалар n функциясының өнімділігі үшін қолайсыз өлшемді енгізеді де, сұрыптау алгоритмдерін қарапайым, тікелей әдіске (n2), күрделіленген немесе логарифмдік әдіске (n*log(n))-ге бөлуге әкеледі. Қорыта келгенде, төмендегідей ерекшеліктерді атап көрсетуге болады: Екілік қосуды тікелей жалғаумен салыстырғанда ешқандай тиімділік бермейді, ал реттелген массив жағдайында тіпті қарама –қайшылық пайда болады. Көпіршікті сұрыптау барлық салыстырулардың ішіндегі ең төмені. Оның жетілдірілген нұсқасы шейкерлік сұрыптау тікелей жалғау мен тікелей таңдаумен салыстырғанда тиімсіз, нашар болып қала береді. Жылдам сұрыптау үймек сұрыптаумен салыстырғанда 2-3 есе тиімді. Ол кері ретпен орналасқан массивті реттелген массивті сұрыптағандай жылдамдықпен сұрыптайды. жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу:
|