Көпіршікті сұрыптау: алгоритм, күрделілік және оңтайландыру әдістері

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

Орындаған: Асқар Ш. Т-341

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

Ең танымал алгоритм - көпіршікті сұрыптау (көпіршікті сұрыптау әдісі немесе көпіршікті сұрыптау ) . Оның танымалдығы қызықты атына және де алгоритмнің қарапайымдылығына байланысты. Алайда, тұтастай алғанда, сұрыптау алгоритмдерінің ең нашарларының бірі болып табылады .

Көпіршікті сұрыптау алмастыру сұрыптауының класына жатады. Оның алгоритмі қажет болған жағдайда, қайталанатын салыстыру элементі мен көрші элементтерін алмастырады. Элементтері суда ауа көпіршіктері ретінде әрекет етеді, олардың әрқайсысы өздерінің деңгейінде көтерілген кезде.

Көпіршікті сұрыптаудың қалай жұмыс жасайтынын көрсету үшін, бізде бастапқы алаптың элементтері dcab бар делік. Әрбір сұрыптаудан өткеннен кейінгі массивтің өзгерген түрі көрсетілген:

Басы d c a b

Өту 1 a d c bе

Өту 2 a b d c

Өту 3 a b c d

Кез келген сұрыптау алгоритмін талдау кезінде салыстырмалы мен айырбастау операцияларының жақсы, орташа және де жаман жағдайда қалай орындалатынын білген маңызды. Орындалатын кодтың ерекшелігі компилятор арқылы оңтайландыру, процессорлар арасындағы айырмашылық және іске асыру ерекшелігі факторларға тәуелді болғандықтан, біз бұл параметрлердің нақты мәндерін табуға тырыспаймыз. Оның орнына зейінімізді әрбір алгоритмнің жалпы тиімділігіне аударамыз.

Көпіршікті сұрыптауда салыстыру саны бірдей болады, себебі екі for циклінде көрсетілген сан тізбектің бастапқыда реттелген немесе реттелмегенине тәуелсіз түрде қайталанып отырады. Бұл дегеніміз көпіршікті сұрыптау алгоритмі әрдайым (n2-n) /2 орындап отырады деген сөз. Мұндағы n - сұрыпталатын элементтер саны. Формула сыртқы циклдің n - 1 рет, ал ішкі цикл n/2 рет орындалуына байланысты шығарылған. Бұл екеуінің көбейтіндісі берілген формулаға сәйкес келеді.

Көпіршікті алгоритм сұрыптауында жақсы жағдайда ауыстыру саны 0-ге тең, егер массив ол кезге дейін сұрыпталған болса. Алайда, орташа немесе жаман жағдайларда ауыстыру саны реттік n2 санының көлемі де болады. Көпіршікті алгоритм сұрыптауын жақсартуға болады, егер жұмыс қарқынын жылдамдатуға тырыссақ. Мысалы, көпіршікті сұрыптаудың келесі ерекшелігі: таңбаланған элемент массивтағы үлкені бірінші сұрыпталудан кейін дұрыс орынды табады.

Негізінде көпіршікті сұрыптаудың екі алгоритмі бар. Және оның екеуінің де эффектісі де бірдей.