Табиғи біріктіру арқылы сұрыптау: алгоритм және күрделілігі

Табиғи бірігу арқылы сұрыптау

Алгоритм

Сандық алгоритмдер. Сандармен математикалық есептеулер жүргізуге арналған.

Сандық емес алгоритмдер. Әртүрлі құрылымдан-ған мәліметтер-мен жұмыс істейді.

Объектілердің берілген тізбегін қандай да бір анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды.

Сұрыптаудың мақсаты - сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді.

Сұрыптау әдістері

Ішкі сұрыптау алгоритмде-рі (массивтерді сұрыптау)

Сыртқы сұрыптау алгоритмде-рі (файлдарды сұрыптау)

Файлдар түрінде ұйымдастырылған мәліметтерді сұрыптау сыртқы сұрыптау деп аталады. Егер файл оперативті жадыда сыймайтындай үлкен болса, онда сұрыптау - өте үлкен проблема. Тура біріктіру арқылы сұрыптау екі реттелген тізімді біріктіретін жай біріктіру әдісін қолданады. Басты идеясы біртіндеп үлкейетін элементтер түрінде файл ұйымдастырылатынында, яғни жазулар тізбегі r1<=r2<=…<=rn жазулар тізбегі.

Сұрыптау бір элементі ішкі тізімдердің жүрістер сериясынан тұрады, әрбір жүрісте ішкі тізімнің ұзындығы екі еселенеді. Ол үшін log2n жүріс қажет болады. Түзу бірігу арқылы сұрыптау 2n log2n мәліметтерді қарауды талап етеді, сондықтан оның күрделілік реті

O (n log 2n) .

Түзу бірігу арқылы сұрыптауда алғашқы ұзындығы бірге тең болатын реттелген сериялар пайдаланылады да, олар әрбір жүріс сайын екі еселеніп отырады. Ең аяғында сериялар файлдардың барлығын қамтиды да сұрыпталу аяқталады. Мұның бір кемшілігі қысқа сериялар мен жұмыста көп уақыт кетеді. Мұндай сұрыптауды салыстырмалы түрде ұзын сериялардан бастасақ, алгоритмнің тиімділігі неғұрлым артады. Әрбір ретте неғұрлым екі серия бірігетін сұрыпталу әдісі табиғи бірігу деп аталады.