Программалау тілдері туралы
жүктеу/скачать 0,64 Mb.
|
ишпей куатындар ушин. Таратпандар-1
- Бұл бет үшін навигация:
- Шелл алгоритмі
- 1962 ж . Чарльз Э. Р. Хоар ойлап тапқан
- 1964 ж . К. Э. Бэтчер о
| Кемшілігі : әрбір қою кезінде массивті жылжыту жүргізіледі , демек , салыстырмалы түрде салыстыру саны аз болған кезде де алмастырулар саны өте ауқымды болуы мүмкін . Бұл алгоритмнің нұсқалары бар : бинарлық қою , екiжолдық қоюлар . қою арқылы сұрыптау байланған тізімдер үшін қолайлы , өйткені бұл жағдайда массивтен айырмашылығы әр түрлі элементтер арасында деректерді тасымалдау қажет емес .
Шелл алгоритмі . Бұл алгоритм кемімелі қадаммен қою арқылы сұрыптау ретінде жіктеледі . Кемитін қадамдар принципі әртүрлі базалық сұрыптау үшін де , оның ішінде көпіршікті сұрыптау үшін де қолданылуы мүмкін . Мұндай модификацияның нәтижесінде тарақпен сұрыптау алынады . Алгоритмнің тиімділігі аралық қадамдардың әрқайсысында элементтердің не азғантай саны немесе элементтердің жеткілікті түрде жақсы реттелген жиынтықтары сұрыпталады . Массивтің реттілігі әр қадамнан кейін өседі . Шелл алгоритмі бойынша сұрыптау кезіндегі массивтің өзгеруі келесі суретте көрсетілген түрге ие ( массивтің бастапқы жағдайы , сыртқы циклдың әрбір өту нәтижесі және соңғы жағдайы келтірілген ) . j = ( 0 ) шарттарын тексеру массивтің шегінен тыс шығып кетуді болдырмайды . Мұндай қосымша тексерулер алгоритмнің өнімділігін сәл төмендетеді деп саналады . Тез сұрыптау алгоритмі . Бұл алгоритмнің жіктемелік атауы – бөле отырып алмастыру арқылы сұрыптау : 1962 ж . Чарльз Э. Р. Хоар ойлап тапқан . Қазіргі уақытта әзірленген ең жақсы әмбебап алгоритмдердің бірі ( өте күрделі емес ) . Алмастыру арқылы сұрыптау алгоритмдері тобына жатады ( көпіршікті сұрыптау сияқты ) . Сұрыпталатын массив екі ішкі массивке бөлінеді , ол үшін алдымен шекаралық немесе тірек мәні – компаранд ( яғни массивтің басқа элементтері салыстырылатын мән ) тандалады . Компарандадан үлкен барлық элементтер бір массивке , ал кішілері екіншісіне ауыстырылады . Барлық процесс барлық массив ретке келтірілгенге дейін әрбір ішкі массив үшін қайталанады . Сұрыптау процесі рекурсивті сипатқа ие . Компаранда таңдау туралы қы рады . Нұсқалары бар : кездейсоқ таңдау – кейде ең жақсысы болып табылады ; ішкі массивтен саны шағын элементтерді таңдау және осы үлгінің медианасын компаранд ретінде пайдалану . Кең таралған және тиімді әдіс – үш элементті таңдау және олардың орташасын алу әдісі ; экстремумнің бірі – ең нашар нұсқа , бірақ бұл жағдайда да алгоритм жұмыс істейді ; – әрбір ішкі массивтің ортасында орналасқан элемент . Әрбір ағымдағы ішкі массивтің ортасындағы компарандпен C / C ++ тілінде жылдам сұрыптау процедурасы ( Хоар әдісі ) . Хоар алгоритмі бойынша сұрыптау кезіндегі массивтің өзгеруі төмендегі суретте көрсетілген түрде ( компарандалардың асты сызылған , өңделетін ішкі массивтер қоршалған ) болады . b b a b с Жылдам сұрыптау кезіндегі массивті өңдеy Алмастыру арқылы біріктіре отырып сұрыптау . 1964 ж . К. Э. Бэтчер ойлап тапқан . Алгоритм Шелл алгоритмін еске салады – мұнда да көрші емес кілттердің жұптары салыстырылады , бірақ жұптар басқаша іріктеледі . 8 , 4 , 2 , 1 қадамдарының тізбегі пайдаланылады , бірақ салыстырмалы жұптар жабылмайды ( яғни екі салыстырмалы көрші жұптарда Шелл алгоритміндегі сияқты ортақ элемент жоқ – 1 - ші және 9 шы , 9 - шы және 17 - ші , 17 - ші және 26 - шы және т.б. ) . Бұдан әрі сұрыпталған ішкі массивтерді жұптарын біріктіру жүреді . жүктеу/скачать 0,64 Mb. Достарыңызбен бөлісу:
|