Кіріспе

Гибридтік сұрыптау алгоритмі

Интросорт немесе интроспективті сұрыптау – бұл гибридтік сұрыптау алгоритмі, ол жылдам орташа өнімділікті және (асимптотикалық) ең нашар жағдайдағы оңтайлы өнімділікті қамтамасыз етеді. Ол жылдам сұрыптаудан басталады, бірақ рекурсия тереңдігі сұрыпталатын элементтер санының (логарифміне) негізделген белгілі бір деңгейден асып кеткен жағдайда үйінділік сұрыптауға ауысады, ал элементтер саны белгілі бір шектен төмен болғанда ендіру сұрыптауына ауысады. Бұл үш алгоритмнің артықшылықтарын біріктіреді, нәтижесінде типтік деректер жиынтықтарында жылдам сұрыптаумен шамалас өнімділікке қол жеткізіледі және үйінділік сұрыптаудың арқасында ең нашар жағдайда O(n log n) уақытында орындалады. Ол қолданатын үш алгоритм де салыстыруға негіделгендіктен, бұл алгоритм де салыстыру түріне жатады. Интросортты Дэвид Муссер 2004 жылы ойлап тапты, сонымен қатар ол quickselect (жылдам сұрыптаудың бір түрі) негізіндегі гибридтік іріктеу алгоритмі – introselect-ті ұсынды, ол медиандар медианына көшу арқылы ең нашар жағдайдағы сызықтық күрделілікті қамтамасыз етеді, бұл оңтайлы нәтиже. Екі алгоритм де C++ стандартты кітапханасы үшін жалпы алгоритмдерді ұсыну мақсатында жасалды, олардың жылдам орташа өнімділігі және ең нашар жағдайдағы оңтайлы өнімділігі бар, соның арқасында өнімділік талаптарын қатаңдатуға болады. Интросорт орнында орындалады және тұрақты емес алгоритм болып табылады.

Талдау

Тез сұрыптаудағы маңызды операциялардың бірі – тізімді бөлуге арналған півотты таңдау. Ең қарапайым півотты таңдау алгоритмі тізімнің бірінші немесе соңғы элементін півот ретінде алу болып табылады, бұл сұрыпталған немесе дерлік сұрыпталған деректер үшін нашар нәтижелерге әкеледі. Никлаус Вирттің нұсқасы осы жағдайлардың алдын алу үшін ортаңғы элементті пайдаланады, бірақ бұл жасалған тізбектер үшін O(n²) дейін нашарлайды. 3 півотты таңдау алгоритмінің медианасы тізімнің бірінші, ортаңғы және соңғы элементтерінің медианасын алады; алайда, бұл көптеген нақты деректерде жақсы жұмыс істесе де, осы півотты таңдау әдісіне негізделген жылдам сұрыптаудың айтарлықтай баяулауына себеп болатын 3 өлтіруші тізімді жасау әлі де мүмкін. Мюссер 100 000 элементтен тұратын 3 қатерлі тізімнің медианасында интросорттың орындалу уақыты 3 півотты жылдам сұрыптаудың уақытынан 1/200 екенін хабарлады. Мюссер сондай-ақ Седжвиктің кішкентай сұрыптаудың кэштерге тигізетін әсерін қарастырды, онда кішкентай диапазон кірістіру сұрыптаудың бір реттік өтуімен соңында сұрыпталады. Ол бұл кэштен қателердің санын екі есеге арттыруы мүмкін екенін, бірақ екі ұшты кезектермен жұмыс істегенде нәтиже айтарлықтай жақсырақ екенін және шаблондық кітапханалар үшін сақталуы керек екенін мәлімдеді, себебі басқа жағдайларда сұрыптауды бірден жасаудың пайдасы айтарлықтай емес.

Қолданылу

Интросортировка немесе оның кейбір нұсқалары стандартты кітапхананың көптеген сұрыптау функцияларында, соның ішінде кейбір C++ сұрыптауларын іске асыруларда қолданылады. 2000 жылғы маусымдағы SGI C++ Стандартты Үлгілер кітапханасының stl algo. h файлындағы тұрақсыз сұрыптауды іске асыруда Муссердің интросортировка тәсілі қолданылады, рекурсия тереңдігі параметр ретінде беріліп үйірмеге ауысады, 3-тің медианасы півотты таңдау үшін қолданылады және 16-дан кіші бөліктер үшін Кнуттың соңғы енгізу сұрыптау кезеңі қолданылады. GNU Standard C++ кітапханасы да ұқсас: 2×log2 n ең тереңдігі бар интросортировка қолданылады, содан кейін 16-дан кіші бөліктерге енгізу сұрыптау қолданылады. LLVM libc++ да 2×log2 n тереңдігі бар интросортировканы қолданады, бірақ енгізу сұрыптаудың өлшем шектері әртүрлі дерек типтері үшін өзгеше (30, егер алмасулар қарапайым болса, әйтпесе 6). Сондай-ақ, 5-ке дейінгі өлшемдегі массивтер бөлек өңделеді. Kutenin (2022) LLVM жасаған кейбір өзгерістерге шолу жасайды, әсіресе 2022 жылғы квадраттық мәселені шешуге назар аударады. Microsoft .NET Framework Class Library, 4.5 (2012) нұсқасынан бастап, қарапайым жылдам сұрыптаудың орнына интросортировка қолданады. Go интросортировканың модификациясын қолданады: 12 немесе одан аз элементі бар кесінділер үшін енгізу сұрыптау, ал үлкен кесінділер үшін үлгіні жеңіп, жылдам сұрыптау және півотты таңдау үшін үш медиананың кеңейтілген медианасы қолданылады. 1.19 нұсқасына дейін кішкентай кесінділер үшін қабық сұрыптау қолданылды. Java, 14-ші нұсқадан (2020) бастап, гибридтік сұрыптау алгоритмін қолданады, ол жоғары құрылымдалған массивтер үшін (аздаған сұрыпталған кіші массивлерден тұратын массивтер) біріктіру сұрыптауын, ал int, long, float және double массивлерін сұрыптау үшін интросортировканы қолданады.

Жалпы

Никлаус Вирт. Алгоритмдер және деректер құрылымдары. Prentice Hall, Inc., 1985.