Сыртқы сұрыптау алгоритмдері

1. a тізбегі b және c екі жартыға бөлінеді;

2. b және c тізбектері жеке элементтерді реттелген жұптарға біріктіру арқылы тоғыстырылады;

3. Алынған тізбек a деп аталады, содан кейін 1 және 2 қадамдар қайталанады; бұл жолы реттелген жұптар реттелген төрттіктерге тоғыстырылады;

4. Алдыңғы қадамдар қайталады; төрттіктер сегіздіктерге тоғыстырылады, барлық үрдіс бүкіл тізбек реттелгенше жалғасады; тоғыстырылатын жарты тізбектер ұзындықтары екі еселеніп отырады.

Табиғи тоғыстыру – бұл әр тоғыстыруда мүмкін ең ұзын ішкі тізбектер біріктірілетін тоғыстыру.

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

Сурет 1. Сұрыптау алгоритмдерінің классификациясы

Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив.

Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі).

Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау). Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.

Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең жақсысы, алмасумен сұрыптау – ең жаманы, ал жылдам сұрыптау ең тезі және ең жақсысы болып табылады.

Орын ауыстырып сұрыптаудың негізгі идеясы сұрыпталған тізімге жаңа элементті қосар кезде оны кез келген орынға емес бірден қажетті орынға қою керек, сосын барлық тізімді қайтадан сұрыптау керек. Орын ауыстырып сұрыптау l өлшемді кез келген сұрыпталған тізімнің бірінші элементін оқиды. Екіэлементті сұрыпталған тізім бірэлементті тізімнің қажетті орнына алдыңғы берілген тізімнен екінші элементті қосқаннан құрылады. Енді алдыңғы берілген тізімнен сұрыпталған екіэлементті тізімге үшінші элемент қоюға болады. Бұл процесс алдыңғы берілген тізімнің барлық элементтері тізімнің кеңейтілген сұрыпталған бөлігіне қойылғанға дейін қайталана береді.

Іздеу деп берілген жиында берілетін эталон априорының (немесе шаблонның) қасиеттеріне иә объектіні табуды атайды. Көп жағдайда жиын массив түрінде анықталады.