Массивті сұрыптау мәселесін шешудің бірнеше негізгі алгоритмдері бар. Олардың ішіндегі ең танымалдарының бірі - кірістіру сұрыптауы. Айқындығы мен қарапайымдылығымен, бірақ тиімділігі төмен болғандықтан бұл әдіс негізінен бағдарламалауды оқытуда қолданылады. Ол негізгі сұрыптау механизмдерін түсінуге мүмкіндік береді.
Алгоритмнің сипаттамасы
Кірістіру сұрыптау алгоритмінің мәні бастапқы массив ішінде дұрыс реттелген сегменттің құрылуы болып табылады. Әрбір элемент белгіленген бөлікпен бір-бірден салыстырылып, қажетті жерге енгізіледі. Осылайша, барлық элементтерді қайталаудан кейін олар дұрыс ретпен қатарға тұрады.
Элементтерді таңдау тәртібі кез келген болуы мүмкін, оларды ерікті түрде немесе қандай да бір алгоритм бойынша таңдауға болады. Көбінесе дәйекті санау реттелген сегмент құрылатын массивтің басынан пайдаланылады.
Сұрыптаудың басталуы келесідей болуы мүмкін:
- Массивтің бірінші элементін алыңыз.
- Салыстыратын ештеңе болмағандықтан, элементтің өзін реттелгендей қабылдаңызреттілік.
- Екінші элементке өтіңіз.
- Сұрыптау ережесі негізінде оны біріншісімен салыстырыңыз.
- Қажет болса элементтерді орындарына ауыстырыңыз.
- Алғашқы екі элементті реттелген реттілік ретінде алыңыз.
- Үшінші элементке өтіңіз.
- Екіншімен салыстырыңыз, қажет болса ауыстырыңыз.
- Егер ауыстыру жасалса, оны біріншісімен салыстырыңыз.
- Үш элементті реттелген реттілік ретінде алыңыз.
Түпнұсқа массивтің соңына дейін солай жалғасады.
Нақты өмірдегі кірістіру сұрыптауы
Түсінікті болу үшін бұл сұрыптау механизмінің күнделікті өмірде қалай қолданылатынына мысал келтірген жөн.
Мысалы, әмиянды алайық. Жүз, бес жүз және мың долларлық купюралар банкнот бөлімінде тәртіпсіз жатыр. Бұл бейберекеттік, мұндай қожалықта дұрыс қағазды бірден табу қиын. Банкноттардың массивін сұрыптау керек.
Бірінші – 1000 рубльдік банкнот, одан кейін бірден – 100. Жүзді алып, алдына қоямыз. Үшіншісі - 500 рубль, оған лайықты орын - жүз бен мыңның арасында.
Сондай-ақ біз "Ақымақ" ойынын ойнаған кезде алынған карталарды сұрыптаймыз, осылайша оларды шарлау оңайырақ болады.
Операторлар және көмекші функциялар
Кірістіру сұрыптау әдісі кіріс ретінде сұрыпталатын бастапқы массивті, салыстыру функциясын және қажет болса, элементтерді санау ережесін анықтайтын функцияны алады. Оның орнына жиі қолданыладытұрақты цикл мәлімдемесі.
Бірінші элементтің өзі реттелген жиын, сондықтан салыстыру екіншісінен басталады.
Алгоритм екі мәнмен алмасу (алмасу) үшін жиі көмекші функцияны пайдаланады. Ол жадты тұтынатын және кодты сәл баяулайтын қосымша уақытша айнымалыны пайдаланады.
Балама - элементтер тобын жаппай жылжыту, содан кейін ағымдағыны бос кеңістікке енгізу. Бұл жағдайда келесі элементке көшу салыстыру оң нәтиже бергенде орын алады, бұл дұрыс ретті көрсетеді.
Іске асыру мысалдары
Нақты іске асыру негізінен қолданылатын бағдарламалау тіліне, оның синтаксисі мен құрылымдарына байланысты.
Мәндермен алмасу үшін уақытша айнымалыны қолданатын классикалық C енгізуі:
int i, j, temp; үшін (i=1; i =0; j--) { if (массив[j] < темп) үзіліс; массив[j + 1]=массив[j]; массив[j]=temp; } }
PHP енгізу:
insertion_sort(&$a) { үшін ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Мұнда алдымен сұрыптау шартына сәйкес келмейтін барлық элементтер оңға жылжытылады, содан кейін ағымдағы элемент бос орынға енгізіледі.
while циклін пайдаланатын Java коды:
қоғамдық статикалық жарамсыз кірістіруСұрыптау(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Кодтың жалпы мағынасы өзгеріссіз қалады: массивтің әрбір элементі алдыңғыларымен дәйекті түрде салыстырылады және қажет болған жағдайда олармен ауыстырылады.
Болжалды жұмыс уақыты
Әрине, ең жақсы жағдайда алгоритмді енгізу дұрыс реттелген массив болады. Бұл жағдайда алгоритм әр элементті алмасусыз оның дұрыс жерде екеніне көз жеткізу үшін жай ғана тексеруі керек. Осылайша, жұмыс уақыты бастапқы O(n) массивінің ұзындығына тікелей байланысты болады.
Ең нашар енгізу - кері ретпен сұрыпталған массив. Бұл ауыстырулардың көп санын қажет етеді, орындалу уақыты функциясы элементтердің квадраты санына байланысты болады.
Толық ретсіз массив үшін ауыстырулардың нақты санын мына формула арқылы есептеуге болады:
n(n-1)/2
мұндағы n – бастапқы массивтің ұзындығы. Осылайша, 100 элементті дұрыс ретпен орналастыру үшін 4950 ауыстыру қажет болады.
Кірістіру әдісі шағын немесе жартылай сұрыпталған массивтерді сұрыптау үшін өте тиімді. Дегенмен, есептеулердің күрделілігіне байланысты оны барлық жерде қолдану ұсынылмайды.
Алгоритм басқа көптеген күрделі сұрыптау әдістерінде көмекші құрал ретінде пайдаланылады.
Тең мәндерді сұрыптау
Кірістіру алгоритмі тұрақты деп аталатын түрлерге жатады. Бұл білдіреді,ол бірдей элементтерді ауыстырмайды, бірақ олардың бастапқы тәртібін сақтайды. Тұрақтылық индексі көп жағдайда дұрыс тапсырыс беру үшін маңызды.
Жоғарыда - бидегі кірістіру сұрыптаудың тамаша көрнекі мысалы.
