Көпіршікті және шейкерлік сұрыптауды талдау. Алмастыру алгоритміндегі сұрыптаулар саны
С=(n2-n)/2 Ал, элементтер орын ауыстыруының ең кіші, орта және ең үлкен саны сәйкес:
Mmіn=0 Mave=3*(n2-n)/2 Mmax=3*( n2-n)/4 тең болады.
Жетілдірілген әдістерді, оның ішінде шейкерлік сұрыптауды талдау өте күрделі. Ең кіші салыстырулар саны Cmіn=n-1.Кнут жетілдірілген көпіршікті сұрыптаудағы електен өткізудің орта мәні n-k1n1/2, ал орташа салыстыру саны - ½(n2-n(k2+ln n))-ге пропорционал дейді. Бұл айтылғандардан жоғарыда келтірілген жетілдірулер алмастырулар санына әсер етпейтінін байқауға болады. Олар тек артық 2 рет тексерулер санын қысқартады. Мұнда екі элементтің орындарын алмастыру - кілттерді салыстыруға қарағанда маңызды операция болып есептеледі. Сондықтан бұл әдіс айтарлықтай ұтыс бермейді.
Жасалынған талдау алмастыру сұрыптауы мен оның жетілдірілуі жалғау мен таңдау көмегімен жасалынған сұрыптаудың ортасындағы операция тәрізді екенін көрсетеді. Оның алгоритмі төмендегідей:
Шындығында көпіршікті сұрыптауда айтарлықтай құнды нәрсе жоқ, ал шейкерлік сұрыптау практикада барлық элементтер реттелген жағдайда пайдаланылады. Ал, мұндай жағдай өте сирек кездеседі.
Енді сұрыптаудың жетілдірілген әдістерін қарастырайық.
Әдебиеттер Негізгі әдебиеттер: 1 [30-34], 3 [86-96]
Қосымша әдебиеттер: 1[111-119] – б, 6 [32-36] – б.
Бақылау сұрақтары Массив дегеніміз не? Индекс деп нені айтамыз?
Массивтің өлшемі, мөлшері ұғымдары қалай түсінесіз?
Массив элементтері ЭЕМ еске сақтау құрылғысында қалай орналасады? Массив элементтерін пайдалануды қалай жүзеге асыруға болады?
Массивтің екі элементтерінің орындарын қалай ауыстыруға болады?
Функция мәндерін есептеу алгоритмдерінің айырмашылығы неде?
Екі массив және бір массив элементтерінің қосындыларын есептеудің алгоритмдері қандай?
Бірдей мөлшерлі екі массив элементтерін кезектестіріп бір массивке біріктірудің алгоритмі қандай? Берілген массив пен құрастырылған массивтердің индекстерінің арасында қандай байланыс бар?
Массив элементін өшірудің, жаңадан элемент қосудың алгоритмдері қандай? Массив элементтерін жылжыту неге соңынан басталу керек?
Массив элементтерін кері бағытта орналастырудың алгоритмін сипаттаңыз.
