Білім беру бағдарламасы білім алушыларына арналған. Лекциялар жинағы «Техника және ақпараттандыру»
жүктеу/скачать 316.11 Kb.
|
- Бұл бет үшін навигация:
- Қыстыру арқылы сұрыптау
| Көпіршіктік іріктеу
Бұл əдістің ойы келесіге негізделген. Əр бір қадамда тізімдегі көршілес элементтер салыстырылады. Егер олар дұрыс емес тұрса, яғни алдынғы элемент келесіден кіші болса, онда олар орындарымен ауысады. Бұл процесті көршілес, дұрыс емес тізімде орналасқан элементтердің пары балғанға дейін созылады. Ол тізімнің іріктелгенін көрсетеді. Көпіршікпен аналогия болған себебі, өйткені əр бір минималды элемент тізім басына шығады. Көпіршіктік іріктеуді екі предикат арқылы жүзеге асырамыз. Олардың біріеуін permutation деп атайық, тізімнің бірінші екі элементтерін салыстырады, егер біріншісі екінші элементтен үлкен болса, онда олардың орындарын ауыстырамыз. Ал егер бірінші жұп дұрыс тізімде орналасса, ол предикат соңын қарастыруға көшеді. Көмекші предикатты permutation пайдалана отырып, негізгі предикат bubble сізімдегі көпіршіктік іріктеуді жүзеге асырады. permutation([X,YT],[Y,XT]:Х>У,!. /* Егер бірінші екіншіден үлкен болса, бірінші екі элементтердің орнын ауыстырамыз */ permutation ([X ,T],[XTl ]):- permutation (Т, Т 1 ). /*соңындағы орын ауыстыруларға көшейік*/ bubble(L,Ll):- permutation (L,LL), /* орын ауыстыруды жүзеге асыратын предикатты шақырайық * / bubble(LL,L!). /* алынған тізімді қайта іріктеуге тырысайық */ bubble(L,L). /* егер орын ауыстырулар болмаса, тізім сортталмағанын көрсетеді. * / Бірақ біздің көпіршіктік əдіс тек дұрыс емес тізбекте орналасқан, ең болмағанда тізімнің бір жұбы болғанша жұмыс істейді. Ондай элементтер біткеннен кейін permutation предикаты сəтсіздікке ұшырайды, ал bubble ережеден фактке өтеді жəне сұрыптаумен тізімді екінші аргументтің сапалы түріне қайтарады. Қыстыру арқылы сұрыптау Енді қыстыру сұрыптауын қарастырайық. Ол, егер тізім соңы сұрыпталған болса, онда тізімдегі бірінші элементті оның соңыдағы орнына қою жеткілікті жəне барлық тізім сұрыпталған болып шығады. Бұл ойды жүзеге асыру үшін екі предикат құрайық. Iinsert предикатының мəні – сұрыпталған тізімге ол реттелген күйде қалатындай мəнін қою. Оның бірінші аргументі қоспалы мəн болады, екіншісі - сұрыпталған тізім, үшіншісі-тізім, бірінші аргументтің қойылымы керек жерде екінші аргументтің реті өзгермейтіндей алынған. ins_sort([ ],[ ]). /* сұрыпталған бос тізім - бос тізім болып қалады. * / ins _sort([HIT],L):- ins _ sort(T, Т _ Sort), /* Т – алғашқы тізімнің соңы, Т _ Sort – сұрыпталған алғашқы тізімнің соңы * / inse~l·1-T.T _ Sort,L). Н қоямыз (алғашқы тізімнің бірінші элементі) T_Sort, L аламыз (тізім , алғашқы тізімнің элементтерінен тұратын жəне кему бойынша емес тұрғандар.) */ insert(X,[],[X]). /* бос тізімге кез-келген мəнді қойсақ, бір элементті тізім аламыз. */ insert(X, [HT], [HTl ]):- Х>Н,!, /* егер қойылатын мəн тізімнің басынан үлкен болса, онда оны соңына қою керек. * / insert(X,T,Tl). /*Х-ті Т-нің соңына қойамыз, нəтижесі Т1 тізімін аламыз */ insert(X,T,[XI 1) ./*бұл ұсыныс егер қойылатын мəн Т тізімінің басынан үлкен болмаса, онда оны Т тізіміне бірінші элемент деп қояғанда ғана қоямыз. */ жүктеу/скачать 316.11 Kb. Достарыңызбен бөлісу:
|