Сұрыптау әдістері жайында

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 8 бет
Таңдаулыға:

Жоспар
І. Кіріспе
ІІ. Негізгі бөлім
1. Алгоритмді сұрыптау.
2. Сұрыптау әдістері
3. Шелла әдісі
4. Хоорда әдісі
5. Берілгендер қоры
6. Сұрыптауға есептер.
ІІІ. Қорытынды

Алгоритм іріктеу
Берілгендерді реттеудің тәжірибелік көзқарас бойынша проблемалары.
Сұрыптаудың әртүрлі бес әдісінің жетістіктері мен кемшіліктері.
Сұрыптау программалаудың барлық облыстарында берілгендер базасында
болсын немесе математикалық программалауда болсын шектеусіз қолданылады.
Сұрыптау алгоритімінің әрқайсысын 3 бөлікке бөлуге болады:
1. Қос элементтің реттілігін анықтау үшін салыстыру,
2. Қос элементтің орындарын ауыстыру арқылы реттеу,
3. Жиынның барлық элементтері реттелгенше салыстыру және өзгерту арқылы
жеке сұрыптау алгоритмі.
Төменде қарастырылатын сұрыптаудың бес алгоритмі де осы қасиеттерге ие
болады. Көптеген алгоритмдерден бұлардың сұрыптап алынған себебі:
біріншіден жиі қолданылады, екіншіден басқа алгоритмдердің көпшілігі осы
көрсетілгендердің әртүрлі модификациялары болып табылады.
1. Көбік әдісі немесе пузирька әдісі.
Бұл әдістің идеясы атынан – ақ көрініп тұр. Ең жеңіл элементтері
жоғары қалқып шығады да, ең ауырлары түбіне шөгеді, яғни батады. Алгоритм
бойынша келесі түрде түсінуге болады.
Біз барлық массивті төменнен жоғарыға деп қарастырамыз және төменгі
элемент жоғарғы элементтен аз болатындай етіп ауыстырамыз. Енді қалған
сұрыпталмаған № - 1 элементтер үшін осыны қайталаймыз, яғни біріншіден
төмен жатқандардан бастаймыз. Көріп отырғанымыздай алгоритм өте қарапайым
және аса тиімді де емес.
Бұл әдіске қарағанда тиімді және көрнекі әдіс – екінші әдіс.
2. Таңдап сұрыптау әдісі
Бұл әдіс бойынша массивті қарастырғанда ең кіші элементті алдыңғы
элементпен салыстыра отырып іздейміз. Егер ондай элемент табылса оның орнын
біріншімен ауыстырамыз. Сосын осы операцияны қайталаймыз, бірақ бұл жолы
бірінші элементтен емес екіншісінен бастаймыз. Осылайша бүкіл массивті
сұрыптап болғанша салыстырамыз.
3. Шелла әдісі
Бұл әдіс 1959 жылы Donald Lewis Shall автрорларының ұсынуымен енгізілді.
Бұл алгоритмнің негізгі идеясы мынада: бір – бірінен ұзақ орналасқан
элементтерді салыстыра отырып массивте тұтас ретсіздік жасау керек.
Салыстырылатын элементтер арасындағы ара қашықтықтың бірте – бірте бірлікке
дейін қысқарады, яғни азаяды. Бұл сұрыптаудың соңғы сатысында көрші
элементтердің реттелуіне әкеледі.
4. Хоора әдісі
Бұл әдістің авторы Charles Antony Richard Hoare. Бұл әдіс 1962 жылы
талданып тез сұрыптау әдісі деген атқа ие болды. Бұл әдістің негізі мынада:
сұрыптауға жататын жиынның ішінен осы жиынды екі жиынға бөліп жіберетін
элементті табу керек. Бұл идеяны түрлі әдістермен көрсетуге болады.
Сұрыптау – элементтердің тұрақтылығын кемімейтін (не өспейтін)
тұрақтылыққа түрлендіру. Элементтердің тұрақтылығы {Аі} кемімейтін деп
аталады, егер кез келген i және j үшін, ij болғанда Аі = Aj теңсіздігі
орындалса.
Қатаң өспелі тізбектер үшін теңсіздік Аі Aj түрге келеді.
Олимпиадалық есептерді шешуде берілгендерді сұрыптау өте қажет. Негізінен
берілгендер N элементтен тұратын массив түрінде беріледі. Мұнда элементтер
сандар мен қатарлардан тұрады. Берілген массивті элементтерді ауыстырып
алгоритмнің бірнеше түрін қолдану керек екенін білу керек.
Есептің күрделілігі логарифмдік сызықтың, квадраттың, экспонициальный
т.б. болуы мүмкін, оларды шешу үшін қажетті O (ln(N))’, O(N), O (N2) және
O (eN) операцияларын тиісінше орындау керек.
Ең жақсы қолдануға тиімді универсальды сұрыптау алгоритмі – O (n* ln
(n)), бұл алгоритм олимпиада есептерінде N = 300 000 массивті сұрыптауға
мүмкіндік береді. Осындай алгоритмдердің қатарына мынадай сұрыптауларды
жатқызуға болады: тез, пирамидалық, бинарлық ағаш. Сұрыптаудың қарапайым
алгоритмі – O (N2), бұл N = 5000 сұрыптау үшін есептер шешуге мүмкіндік
береді.
Кейбір жағдайларда сызықтың тәртіптің күрделілігімен сұрыптауға болады,
егер берілгендерде кейбір шектеулер бар болса (мысалы массив ішінара
сортталған немесе элементтің диапозоны шектелген болса). Осындай тәртіппен
107 элементтен тұратын массивті сұрыптауға болады. Мысалы: келесі
алгоритмдер мынадай шешім береді: цифрлық және разрядтық.
Көпшілік кез келген олимпиадалық есепті шешу үшін екі сұрыптау әдісін
білсек жеткілікті деп ойлайды. Бірақ шындығында олай емес.
Енді біз программистердің жиі қолданатын сұрыптау алгоритмдерін
қарастырамыз.
a [i] – сандық массив, n элементтен тұратын, 1 -ден n – ге дейінгі
индекспен белгіленген массивті сұрыптау алгоритімінің барлық мысалдарда
қарастырамыз.
Талдау сұрыптау. Алдымен барлық элементтер арасындағы ең кішісін анықтап,
1 мен алмастырамыз, ары қарай қалғандарының ішінен тағы да ең кішісін
тауып, екіншімен алмастырамыз Осылайша (n - 1) – ші элементке дейін
алмастырамыз.
Шешу алгоритмі төмендегіше болады:
for I = 1...n – 1{
for j = I + 1... n{
if (a [i] a [j]) a [i] ------ a [j];
}
}
Көбік сұрыптау. Бұл сұрыптау алгоритмін де алдыңғыға ұқсас, мұнда да
керекті элементті біріншіден бастап соңғысына дейін позицировать етеміз.
Керекті элементті өз позициясына қою көбікті еске түсіреді. Бірінші (ең
кіші) элемент өз орнына тұру үшін массивпен оңға және солға жылжуы керек,
қос – қостан көрші элементтерді солдан оңға қарай орын ауыстыратындай етіп
салыстырамыз. Екінші элементті өз орнына қою үшін тағы да массив бойынша
жүру керек, бірақ ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.