Ауыстыру арқылы сұрыптау

Презентация қосу

Ауыстыру арқылы
сұрыптау

Орындаған: Мұратқанова А.Е.
Т-341 топ
10/12/17
Сұрыптау (Селекция; selection;
Сортировка; sorting) - массив
элементтерін белгілі бір заңдылықпен
орындарын ауыстырып реттеу процессін
айтамыз.
Сұрыптау мақсаты - көптеген
сұрыпталған обьектінің ішінен белгілі бір
элементті іздеуді оңайлату. Ақпараттық
жүйелерде мәліметтерді сұрыптаудың
маңызы өте зор.
Сұрыптаудың түрлері
Бүгінгі таңда сұрыптаудың көптеген
тәсілдері белгілі. Олар:
• Таңдау арқылы сұрыптау
• Ауыстыру арқылы сұрыптау
• Индекстері арқылы сұрыптау
• Енгізу арқылы сұрыптау
• Біріктіру арқылы сұрыптау
10/12/17
Ауыстырып сұрыптау

көпіршікті
шейкерлік
сұрыптау
сұрыптау

жедел
сұрыптау
10/12/17
Көпіршікті сұрыптау
Ең танымал алгоритм - көпіршікті сұрыптау (көпіршікті
сұрыптау әдісі немесе көпіршікті сұрыптау ). Оның
танымалдығы қызықты атына және де алгоритмнің
қарапайымдылығына байланысты. Алайда, тұтастай
алғанда , сұрыптау алгоритмдерінің ең нашарларының
бірі болып табылады .
Көпіршікті сұрыптау алмастыру сұрыптауының класына
жатады. Оның алгоритмі қажет болған жағдайда ,
қайталанатын салыстыру элементі мен көрші
элементтерін алмастырады. Элементтері суда ауа
көпіршіктері ретінде әрекет етеді, олардың әрқайсысы
өздерінің деңгейінде көтерілген кезде.
Көпіршікті сұрыптаудың қалай жұмыс
жасайтынын көрсету үшін , бізде бастапқы
алаптың элементтері dcab бар делік. Әрбір
сұрыптаудан өткеннен кейінгі массивтің өзгерген
түрі көрсетілген:
• Басы d c a b
• Өту 1 a d c bе
• Өту 2 a b d c
• Өту 3 a b c d

10/12/17
Кез келген сұрыптау алгоритмін талдау кезінде салыстырмалы мен айырбастау
операцияларының жақсы, орташа және де жаман жағдайда қалай орындалатынын
білген маңызды. Орындалатын кодтың ерекшелігі компилятор арқылы оңтайландыру,
процессорлар арасындағы айырмашылық және іске асыру ерекшелігі факторларға
тәуелді болғандықтан, біз бұл параметрлердің нақты мәндерін табуға тырыспаймыз.
Оның орнына зейінімізді әрбір алгоритмнің жалпы тиімділігіне аударамыз. Көпіршікті
сұрыптауда салыстыру саны бірдей болады, себебі екі for циклінде көрсетілген сан
тізбектің бастапқыда реттелген немесе реттелмегенине тәуелсіз түрде қайталанып
отырады. Бұл дегеніміз көпіршікті сұрыптау алгоритмі әрдайым (n2-n)/2 орындап
отырады деген сөз. Мұндағы n – сұрыпталатын элементтер саны. Формула сыртқы
циклдің n - 1 рет, ал ішкі цикл n/2 рет орындалуына байланысты шығарылған. Бұл
екеуінің көбейтіндісі берілген формулаға сәйкес келеді.
Көпіршікті алгоритм сұрыптауында жақсы жағдайда ауыстыру саны 0-ге тең, егер
массив ол кезге дейін сұрыпталған болса. Алайда, орташа немесе жаман жағдайларда
ауыстыру саны реттік n2 санының көлемі де болады. Көпіршікті алгоритм сұрыптауын
жақсартуға болады, егер жұмыс қарқынын жылдамдатуға тырыссақ. Мысалы,
көпіршікті сұрыптаудың келесі ерекшелігі: таңбаланған элемент массивтағы үлкені
бірінші сұрыпталудан кейін дұрыс орынды табады.
Негізінде көпіршікті сұрыптаудың екі алгоритмі бар. Және оның екеуінің де эффектісі
де бірдей.
Жедел сұрыптау
Мәліметтерді тез сұрыптауға мүмкіндік
беретін алгоритм, атап айтқанда, сандық
мәліметтерді өсу реті бойынша немесе
мәтіндік мәліметтерді алфавит ретімен
орналастыру. Алгоритм тізіммен берілген
әрекетті орындайды және тізімнің әр
жерінде орналасқан мәліметтерді
салыстырады. Бірнеше жүз элементген
тұратын айтарлыктай үлкен тізімдер үшін
қолданылады.
Жедел сұрыптаудың
артықшылығы
Сұрыпталған тізбектегі қажетті
элементтерді іздестіруді жеңілдетеді.
Ең тезі және ең жақсысы болып
табылады
Бөліктеу арқылы есептеледі.

10/12/17
• 1
Алгоритмі: • 7 13
• 1
Өлшемі n болатын А массивін • 1 13

толтыру i:=1; Индексі i-ден •
•
басталатын массив элементтерінің • 1
• 13
ішінен A[i] және A[j] элементтерінің • 1

орндарын ауыстыру; •
•

i:=i+1 мәні үшін i:=n болғанға дейін •
•

Сұрыпталған A массивін экранға •
•
шығару; • 13
Шейкер әдісімен сұрыптау
Сұрыптаудың шейкерлі әдісі -
ретсіздіктен құтылу арқылы сұрыптау.
Шайқау әдісімен сұрыптау кезінде
массивтегі жүрістер саны минимальды
немесе максимальды элемент қай
жерде орналасқанына байланысты.
Мұнда бірінен кейін бірі келетін
жүрістердің бағытын ауыстыру арқылы
жылдамдатуға болады.
10/12/17
Массив реттелген болған жағдайда бүкіл тізім бойынша 1 ғана
жүріс өтеді. Мұнда тиімділігі О(n)-ға тең. Ал ең тиімсіз
жағдайда i-1 жүріс орындалады және i-ші жүрісте n-i-1
салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n 2) тең.
Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы
сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді
болады. Шейкер сұрыптау алгоритмі элементтердің барлығы
немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді.
• Бұл алгоритмнің негізгі мәні мынада:
• · Массивтегі ретсіздіктен құтыламыз;
• · Бір-бірінен алшақ орналасқан элементтерді салыстырамыз;
• · Салыстырып отырған интервалдар бірте-бірте кемиді;
• · Соңғы қадамдарды элементтер жай ғана орые алмастырумен
шектеледі.

Ұқсас жұмыстар

“Сұрыптаудың” анықтамасы

Бір өлшемді массивтерді сұрыптау

Таңдау арқылы сұрыптау

Көпіршікті сұрыптау

Массивтерді сұраптау әдістері

Мәліметтерді шейкер әдісімен сұрыптау

Массивтерді сұрыптау!

Сандық массивтерді сұрыптау тақырыбы бойынша сабақтарға арналған әдістемеліктер

ЖЫЛДАМ СҰРЫПТАУ АЛГОРИТМІ

Станса жұмысының технологиялық үрдісінің негізі

Пәндер