Білім беру бағдарламасы білім алушыларына арналған. Лекциялар жинағы «Техника және ақпараттандыру»
жүктеу/скачать 316.11 Kb.
|
- Бұл бет үшін навигация:
- Тез сұрыптау
| Таңдау арқылы сұрыптаймыз.
Алгоритм ойы таңдау арқылы сұрыптау өте қарапайым. Тізімде минималды элементті табамыз (осы лекция басында ойлап тапқан предикатты min_list пайдалана отырып). Оны тізімнен жоямыз (алдынғы лекцияда қарастырылған, delete _ one предикат көмегімен). Қалған тізімді сұрыптаймыз. Сұрыпталған тізімге басы ретінде минималды элементті қосамыз. Себебі бұл элемент алғашқы тізімдегі барлық элементтерден кіші болды, жəне ол сұрыталған тізімнің барлық элементтерінен кіші болады.Жəне соған байланысты, егер оны тізімді сорттау басына қойсақ, онда тізбек өзгермейді: Жазып алайық: choice([ ],[ ]). /* сұрыпталған бос тізім - бос тізім болып қалады. * / choice(L,[XIT]):- /* Х-ті сұрыпталған тізімге Т жазамыз. (L-тізімінің минималды элементі) */ min _list(L,X), /* Х - L-тізімінің минималды элементі */ delete _ one(X,L,L 1), /* L 1 - L тізімінен Х элементінің бірінші кірісінің нəтижесін өшіру * / choi r(L 1, Т). /* L 1 тізімін сұрыптайық, нəтижесін Т – деп белгілейік* / Тез сұрыптау “Тез сорттаудың” авторы Хоар болып табылады. Ол оны тез деп атады, өйткені жалпыжағдайда бұл алгоритмнің эффектілігі айтарлықтай жоғары. Əдіс ойы келесідей. Алғашқы тізімді екі жазылымға бөлеміз, ол кейбір кедергілі элемент қолданылады. Біріншісінде__________кедергі элементінен кіші элементті орналастырамыз, екіншісінде – үлкен не тең. Бұл тізімдердің əр қайсысын сол əдіспен сұрыптаймыз, одан кейін тізімге кедергіден кіші элементтерді қосамыз, ең бірінші кедергі элементтің өзін, одан кейін кедергіден кіші элементтердің тізімін. Нəтижесінде дұрыс тізімде тұрған элементтерден тұратын тізімді аламыз. Бұл ойды программалық кодқа іске асыру үшін, бізге қарапайым предикат керек болады. Рartition қосымша предикаты екі қосымша тізімшеге бөлінуіне жауапшы болады. Онда төрт аргумент болады. Бірінші екі элемент -енетін: біріншісі – алғашқы тізім, екіншісі –кедергілік элемент. Үшінші жəне төртінші элементтер –шығатын, соған байланысты кедергіден кіші алғашқы тізімнің элементтер тізімі, жəне кедергі элементтерінен кіші емес элементтерден тұратын тізім. Quick_sort предикаты Хоардың тез сұрыптау алгоритмымен жүзеге асырылады. Ол екі сөйлемнен құралатын болады. Мынаны жазып алайық: quick_sort([],[]). /* Сортталған бос тізім бос болып қалады. */ quick_sort([HT],C):- жүктеу/скачать 316.11 Kb. Достарыңызбен бөлісу:
|