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