Көпіршікті сұрыптау және таңдау сұрыптау
Көпіршікті сұрыптау – көрші элементтер жұптарын салыстыру кезінде қайта-қайта сұрыпталатын тізім арқылы жұмыс істейтін сұрыптау алгоритмі. Егер элементтер жұбы дұрыс емес тәртіпте болса, олар дұрыс ретпен орналастыру үшін ауыстырылады. Бұл өту басқа своптар қажет болмайынша қайталанады. Таңдау сұрыптауы да сұрыптау алгоритмі болып табылады, ол тізімдегі ең аз элементті табудан және оны бірінші элементпен ауыстырудан басталады. Бұл процесс ауыстырылған элементтерді ретімен орналастыру арқылы тізімнің қалған бөлігінде қайталанады.
Көпіршікті сұрыптау дегеніміз не?
Көпіршікті сұрыптау – көрші элементтер жұптарын салыстыру кезінде қайта-қайта сұрыпталатын тізім арқылы жұмыс істейтін сұрыптау алгоритмі. Егер элементтер жұбы дұрыс емес тәртіпте болса, олар дұрыс ретпен орналастыру үшін ауыстырылады. Бұл өту бұдан әрі своптар қажет болмайынша қайталанады (бұл тізім сұрыпталғанын білдіреді). Тізімдегі кішірек элементтер көпіршік бетіне шыққан сайын жоғары шығатындықтан, оған көпіршікті сұрыптау атауы беріледі. Көпіршікті сұрыптау - өте қарапайым сұрыптау алгоритмі, бірақ n элементі бар тізімді сұрыптау кезінде оның орташа іс уақыты күрделілігі O(n2) болады. Осыған байланысты көпіршікті сұрыптау элементтер саны көп тізімдерді сұрыптау үшін жарамайды. Бірақ оның қарапайымдылығына байланысты көпіршікті сұрыптау алгоритмдермен танысу кезінде үйретіледі.
Таңдау сұрыптау дегеніміз не?
Таңдау сұрыптауы - бұл тізімдегі ең аз элементті табу және оны бірінші элементпен ауыстыру арқылы басталатын басқа сұрыптау алгоритмі. Содан кейін ең төменгі элемент тізімнің қалған бөлігінен (екінші элементтен тізімдегі соңғы элементке дейін) табылады және екінші элементпен ауыстырылады. Бұл процесс ауыстырылған элементтерді ретімен орналастыру арқылы тізімнің қалған бөлігінде қайталанады. Сонымен таңдау сұрыптауында, алгоритмнің кез келген қадамында тізім екі бөлікке бөлінеді, оның бір бөлігінде сұрыпталған элементтер, ал екінші бөлігінде сұрыпталмаған элементтер бар. Алгоритм жүріп жатқанда сұрыпталған тізім солдан оңға қарай өседі. Таңдау сұрыптауы да O(n2) орташа іс уақытының күрделілігіне ие. Сондықтан ол үлкен тізімдерді сұрыптау үшін де жарамайды.
Көпіршікті сұрыптау мен таңдау сұрыптауының айырмашылығы неде?
Көпіршікті сұрыптау және іріктеу сұрыптау алгоритмдерінің екеуінің де O(n2) орташа іс уақытының күрделілігі болса да, көпіршікті сұрыптау барлық уақытта дерлік таңдау сұрыптауынан асып түседі. Бұл екі алгоритмге қажет своптардың санына байланысты (көпіршікті сұрыптаулар көбірек своптарды қажет етеді). Бірақ көпіршікті сұрыптаудың қарапайымдылығына байланысты оның код өлшемі өте аз. Тұрақтылық - бұл екі алгоритмнің тағы бір айырмашылығы. Тұрақты сұрыптау алгоритмі, егер тізімде мәні тең элементтер болса, жазбалар ретін сақтайтын сұрыптау алгоритмі. Бұл мағынада таңдау сұрыптауы тұрақты алгоритм емес, ал көпіршікті сұрыптау тұрақты алгоритм болып табылады.
