Хоар сұрыптамасы (лездік сұрыптау). ( 2 сағат)

Хоар сұрыптамасы (лездік сұрыптау). ( 2 сағат)

Бұл сұрыптауды жылдам сұрыптау деп атаймыз. Бұл әдісті 1962 жылы Оксфорд университетінің профессоры К.Хоар жасап шығарған. Бұл рекурсияны пайдалану туралы тамаша мысал. N элементтен тұратын А массивін өсу реті бойынша сұрыптау туралы алгоритмін қарастырайық.

Қандайда да бір элемент мәні, көбінесе ортаңғысын Х айнымалысына жазады. Массив элементтері қарастырылады. Солдан-оңға қарай қозғалыста Х элементіне тең немесе одан үлкен элементті іздейміз. Ал, оңнан-солға қарай қозғалыста Х-қа тең немсес одан үлкен элементті іздейміз. Табылған элементтер орындары ауыстырылады және қарсы іздеу жалғасытырылады.

Содан соң ол массив екі бөлікке дәл бөлінеді. Бастапқыда Х-ке тең немесе кіші элементтер табылады, ал оң жағынан – Х-ке тең немесе үлкендері табылады. А массивін сұрыптау туралы берілген есепті сұрыптау нәтижесінде алынған массив бөліктеріне байланысты екі ішкі есептерге бөлуімізге болады.

Берілген рекурсивті алгоритмді бір рет шақыруды есептеу сұрыптайтын массив элементтері сандарына теңбе-тең. Ең жақсысы бөлікті дәл екіге бөлу, сондықтан барлық алгоритмнің есептеу қиындығы N*LogN реттегі жылдам сұрыптау өлшемдерінен тұрады (2 негіздегі логарифм). Есептелуі орта есепппен алдыңғы тәртіп бойынша.

Сурет. 7. Жылдам сұрыптаудың блок-сұлбасы.

Сурет 8. Разряд бойынша сұрыптау әдісінің блок-сұлбасы.

А массивінің әр элементі B_i көмекші массивінің ішіне салынады, мұнда i - элементтің n-ші разрядының мәні.

Кесте 6. Жылдам сұрыптаудың мысалысы