Кіріспе

Сорталау алгоритмі

Компьютерлік ғылымда, шыдамдылық бойынша сұрыптау – карточкалық ойын «шыдамдылықтан» шабыттанған және оның атымен аталған сұрыптау алгоритмі. Алгоритмнің бір түрі берілген массивтегі ең ұзын өсу тізбегінің ұзындығын тиімді есептейді.

Шолу

Алгоритмнің атауы "сабырлық" карта ойынының қарапайым түрінен шыққан. Ойын, араластырылған карта текшесімен басталады. Карталар төмендегі ережелер бойынша үстелге бірінен соң бірі үюлерге таратылады. Бастапқыда, үюлер жоқ. Алғашқы карта бір картадан тұратын жаңа үю құрайды. Әрбір келесі карта, жаңа картаның мәнінен үлкен немесе тең мәні бар ең сол жаққа орналасқан үюдің үстіне қойылады, немесе барлық қолданыстағы үюлердің оң жағына қойылып, жаңа үю құрайды. Таратуға карталар қалмағанда ойын аяқталады. Бұл карта ойыны екі кезеңді сұрыптау алгоритміне айналады. Толық реттелген доменнен n элементтен тұратын массив берілген болса, бұл масситті карталар жинағы ретінде қарастырып, сабырлық сұрыптау ойынын модельдеңіз. Ойын аяқталғаннан кейін, реттелген тізбекті ең кішкентай көрінетін картаны қайталап алып шығу арқылы қалпына келтіріңіз; яғни, әрқайсысы ішкі сұрыпталған p үюдің k жолды біріктірілуін жүзеге асырыңыз.

Талдау

Сабырлылық сұрыптаудың бірінші кезеңі, карта ойындарының симуляциясы, ең нашар жағдайда n элементтік кіріс массиві үшін O(n log n) салыстырулар алу үшін іске асырылуы мүмкін: ең көп дегенде n үйме болады, ал құрылымы бойынша үймелердің жоғарғы карталары солдан оңға қарай өсу тізбегін құрайды, сондықтан қалаған үйме бинарлық іздеу арқылы табылуы мүмкін. Екінші кезең – үймелерді біріктіру, басымдық кезегін пайдаланып, сондай-ақ уақытында орындалуы мүмкін. Егер кіріс деректерде табиғи "жұмыстар" болса, яғни төмендемейтін кіші массивтер болса, онда өнімділік айқын түрде жақсаруы мүмкін. Шын мәнінде, кіріс массиві реттелген болса, барлық мәндер бір үйме құрайды және екі кезең де O(n) уақытында орындалады. Орташа жағдайдың күрделілігі әлі де O(n log n) құрайды: кез келген біркелкі кездейсоқ мәндер тізбегі күтілетін үйме санын тудырады, оларды құруға және біріктіруге уақыт кетеді. Шыдамдылық сұрыптаудың практикалық тиімділігін Чандрамули мен Голдштейн бағалап, олардың сынақ мәселесінде қарапайым нұсқасы қазіргі заманғы жылдам сұрыптаудан оннан жиырма есеге дейін баяу екенін көрсетеді. Олар мұны шыдамдылық сұрыптауға жұмсалған салыстырмалы түрде аз зерттеулерге байланысты айтады және оның өнімділігін жылдам сұрыптау деңгейіне дейін жақындататын бірнеше оңтайландыруларды әзірлейді. Егер карталардың мәндері 1-ден n-ге дейін болса, онда карталарды үймелерге қою үшін ең нашар жағдайда жұмыс істейтін тиімді іске асыру бар, ол Ван Эмде Боас ағашына сүйенеді.

Басқа проблемалармен байланысы

Сабырды сұрыптау Флойд ойыны деп аталатын карта ойынымен тығыз байланысты. Бұл ойын бұрын сипатталған ойынға өте ұқсас: бірінші карта бір картадан тұратын жаңа қатар құрайды. Әрбір келесі карта жаңа картаның мәнінен кем емес мәні бар қолданыстағы қатардың үстіне немесе барлық қолданыстағы қатарлардың оң жағына қойылады, осылайша жаңа қатар пайда болады. Қолда бар карталар біткен кезде ойын аяқталады. Ойынның мақсаты – мүмкіндігінше аз қатармен аяқтау. Сабырды сұрыптау алгоритмінен айырмашылығы, жаңа картаны сол жақтағы қатарға қоюдың міндетті шарты жоқ. Сабырды сұрыптау – бұл ойынды ойнаудың ашкөз стратегиясы болып табылады. Алдос және Диаконис 9 немесе одан аз қатарды жеңіске жету нәтижесі деп анықтауды ұсынады, бұл шамамен 5% ықтималдықпен орын алады.

Ең ұзын өсетін кіші тізбекті табу алгоритмі

Алдымен жоғарыда сипатталғандай сұрыптау алгоритмін орындаңыз. Қалыптардың саны ең ұзын кіші тізбектің ұзындығымен анықталады. Кез келген картаны қалыпқа қойғанда, алдыңғы қалыптағы жоғарғы картаға (жаңа картадан кішірек мәні бар екендігі болжамдалады) кері сілтеме қойыңыз. Соңында, ең ұзын ұзындығы бар төмендеу тізбегін қалпына келтіру үшін соңғы қалыптағы жоғарғы картадан кері сілтемелерді орындаңыз; оның кері тізбегі ең ұзын өсу тізбегін табу алгоритмінің жауабы болып табылады. С. Беспамятник және М. Сегал, А. С. Росс және тәуелсіз түрде Роберт В. Флойд оны сұрыптау алгоритмі ретінде таныды. Алғашқы талдауды Маллоуз жасады. Флойдтың ойынын Флойд Дональд Кнутпен хат алмасып әзірледі.

Қолдану

Шыдамдылықты сұрыптау алгоритмі процестерді басқаруда қолданылуы мүмкін. Өлшемдер тізбегінде ұзақ өсу тізбегінің болуы трендтің көрсеткіші ретінде пайдаланылуы мүмкін. 2002 жылғы SQL Server журналындағы мақалада ең ұзын өсу тізбегінің ұзындығын анықтау үшін шыдамдылықты сұрыптау алгоритмінің SQL нұсқасы келтірілген.