Сұрыптау әдістерін қарастыру және сынау. I бөлім

Күні кеше «ВКонтакте» әлеуметтік желісіндегі пікірлерде жобаның басқа студенттерінің бірімен ұрысып қалдым. Даудың мәні «кім жеңеді» болды - қарапайым алгоритмдердің sort()сыныптағы әдісі java.util.Arraysнемесе өздігінен жазылған іске асыру: көпіршік , кірістіру , таңдау , қабық (Shell алгоритмі). Кейбіреулер үшін бұл сұрақтың жауабы анық болуы мүмкін, бірақ дау туындағандықтан, әр тарап өз көзқарасын жақтайтын «құрмет көздеріне» қарамастан, сұр материяны кеңейте отырып, зерттеу жүргізу туралы шешім қабылданды. процесс, әр түрлі алгоритмдерді жүзеге асыру. TL;DR: java.util.Arrays.sort() ол 100 000 немесе одан да көп элементтерден тұратын массивтер бойынша сөзсіз көшбасшы; кішірек өлшемде Shell әдісі кейде онымен бәсекелесе алады. Қарастырылған алгоритмдердің қалған бөлігі толығымен бос және кейбір экзотикалық жағдайларда ғана пайдалы болуы мүмкін. Енді кремний uber-құрылғыларымызда массивтер қалай сұрыпталатынын қарастырайық.

Таңдау сұрыптауы. Таңдау бойынша сұрыптау

Ең қарапайым және ең айқын әдіспен бастайық. Оның мәнін бізге Роберт Седгвик курсра туралы бейне лекциясында тамаша көрсетті (Мен GIF-ке нашар сығымдалған анимациядан үзінді келтіремін): Көрініс Бірінші элементтен массив арқылы жүгіру, әрбір қадамда біз оң жақтағы минималды элементті іздеңіз, онымен ағымдағы элементті ауыстырамыз. Нәтижесінде массивіміздің соңғы нұсқасын сұрыпталған түрде сақтаймыз. Міне, Java-да осы алгоритмді жүзеге асыратын code:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

Алгоритмді талдау көрсеткендей, әрбір өту кезінде массивтің қалған бөлігін тарау қажет, яғни бізге дәл N + (N-1) + (N-2) + ... + 1 = N^ қажет болады. 2/2 салыстыру. Осылайша, алгоритмнің күрделілігі O(N^2) болады. Бұл нені білдіреді? Бұл массивтегі элементтер санын (N) 2 есе көбейту арқылы алгоритмнің жұмыс істеу уақытын 2 емес, 2^2 = 4 есе көбейтеміз дегенді білдіреді. N 10 есе ұлғайту арқылы біз жұмыс уақытын 100 есе арттырамыз және т.б. Ubuntu 14.4 нұсқасымен жұмыс істейтін Core i3 процессоры бар 2012 жылғы ноутбугымда мен келесі жұмыс уақытын алдым:

Кірістіру сұрыптауы. Кірістіру сұрыптауы

Мұнда идея сәл басқаша. Тағы да, Доктор Седгвиктің анимациясына жүгінейік: Көрініс Алда не күтіп тұрғанын біз әлі көрген жоқпыз және артта қалдырғанның бәрі әрқашан өз орнында қалады. Мәселе мынада, біз бастапқы массивтің әрбір жаңа элементін кішірек элементке «тұрғанша» басына «қайтарамыз». Осылайша, бізде тағы да N өту бар (бастапқы массивтің әрбір элементі үшін), бірақ әр өтуде көп жағдайда біз барлық қалдықты емес, тек бір бөлігін ғана қарастырамыз. Яғни, біз әрбір келесі элементті ең басына қайтару керек болған жағдайда ғана 1 + (N-1) + (N-2) + … + N = N^2/2 опциясын аламыз, яғни жағдайда «кері» массив бойынша сұрыпталған кірістің (сәтсіз, сәтсіз). Қазірдің өзінде сұрыпталған массив жағдайында (бұл жерде сәттілік) толық тегін болады - әр өтуде бір ғана салыстыру және элементті орнында қалдыру бар, яғни алгоритм N пропорционалды уақытта жұмыс істейді. Күрделілігі Алгоритмнің ең нашар теориялық жағдайы, яғни O( N^2) арқылы анықталады. Орташа алғанда, жұмыс уақыты N^2/4 пропорционалды болады, яғни алдыңғы алгоритмге қарағанда екі есе жылдам. Менің іске асыруымда ауыстыруды оңтайлы пайдаланбағандықтан, жұмыс уақыты Таңдау уақытынан ұзағырақ болды. Жақында постты түзетіп, жаңартуды жоспарлап отырмын. Міне, code және оның бір машинада жұмыс істеу нәтижесі:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Қабық сұрыптау. Қабық сұрыптау

Ақылды жігіт Дональд Шелл 1959 жылы кірістіру алгоритміндегі ең қымбат жағдайлар элемент массивтің басына өте алыс оралғанда болатынын байқады: кейбір өтуде элементті бірнеше позициялар арқылы басына қайтарамыз. , ал басқа бір өтуде бүкіл массив арқылы басына дейін алыс және ұзақ. Мұны бірден бірнеше элементтер арқылы секіру мүмкін бе? Және ол мұндай жолды тапты. Ол дәйекті түрде орындалатын арнайы ішінара сұрыптаулардан тұрады, әдетте d-сұрыптау немесе, Седгвик бойынша h-сұрыптау деп аталады (менің ойымша, h - hop дегенді білдіреді). Мысалы, 3-сұрыптау қарастырылып отырған элементті алдыңғысымен емес, екеуін өткізіп жіберіп, бір 3 позициямен салыстырады. Өзгертілген болса, ол оны 3-элементтің кері позициясымен және т.б. салыстырады. Қорытындылайтын болсақ, алынған массив «3-сұрыпталған» болады, яғни элементтердің дұрыс емес орналасуы 3 позициядан аз болады. Бұл кірістіру алгоритмімен жұмыс істеу оңай және жағымды болады. Айтпақшы, «1-сұрыптау» жай ғана кірістіру алгоритмінен басқа ештеңе емес =) h мәнін азайтатын массивке h-сұрыптауды дәйекті қолдану арқылы біз үлкен массивті жылдамырақ сұрыптай аламыз. Мынадай көрінеді: Көрініс Мұндағы мәселе ішінара сұрыптаулардың дұрыс реттілігін таңдау болып табылады. Сайып келгенде, алгоритмнің өнімділігі осыған байланысты. Ең көп таралғаны Дональд Кнут ұсынған реттілік: h = h*3 + 1, яғни 1, 4, 13, 40, ... және т.б. массив өлшемінің 1/3 бөлігіне дейін. Бұл реттілік лайықты өнімділікті қамтамасыз етеді және оны орындау оңай. Алгоритмді талдау мыңдаған тілді қажет етеді және менің мүмкіндігімнен тыс. Талдаудың кеңдігі h реттілігінің көптеген нұсқаларымен де анықталады. Эмпирикалық түрде алгоритмнің жылдамдығы өте жақсы деп айта аламыз - өзіңіз қараңыз: Бір секундтан аз уақыт ішінде миллион элемент! Міне, Knut тізбегі бар Java codeы.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Көпіршікті сұрыптау. Көпіршік әдісі

Бұл классика! Әрбір жаңа бастаған бағдарламашы дерлік бұл алгоритмді жүзеге асырады. Бұл классика болғаны сонша, доктор Седгвиктің оған анимациясы да болмаған, сондықтан мен жұмысты өзім орындауға тура келді. Көру Мұнда, әр өтуде, біз тәртіпсіз көрші элементтерді ауыстыра отырып, массивті басынан аяғына дейін айналдырамыз. Нәтижесінде ең үлкен элементтер массивтің соңына дейін «жүзеді» (осыдан атауы). Жиым сұрыпталған ( sorted = true) деген үмітпен әрбір жаңа өтуді оптимистік түрде бастаймыз. Үзіндінің соңында қателескенімізді көрсек, жаңа жолды бастаймыз. Мұндағы қиындық мынада, біз тағы да әрбір өтуде бүкіл массивті (дерлік) айналып өтеміз. Салыстыру әр қадамда болады, алмасу әр қадамда дерлік жүреді, бұл бұл алгоритмді ең баяулардың біріне айналдырады (егер ұтымды жүзеге асырылғандарын қарастырсақ, «сұрыптауды» және басқаларды). Бір қызығы, мұнда формальды түрде күрделілік O(N^2) тең болады, бірақ коэффициент кірістіру мен таңдаудан әлдеқайда жоғары. Алгоритм codeы:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Жұмыс уақыты: Айырмашылықты сезініңіз: миллион элементтерде жарты сағаттан астам уақыт! Қорытынды: Бұл алгоритмді ешқашан қолданбаңыз!!!

Бірінші бөлімнің қысқаша мазмұны

Нәтижесінде мен осы алгоритмдер үшін жалпы кестені қарауды ұсынамын. Сондай-ақ кірістірілген әдіс нәтижелерімен салыстыруға болады java.util.Arrays.sort(). Бұл қандай да бір сиқырға ұқсайды - Shell-ден жылдамырақ не болуы мүмкін? Бұл туралы келесі бөлімде жазамын. Онда біз кеңінен қолданылатын жылдам сұрыптау алгоритмдерін, сондай-ақ біріктіру сұрыптауын қарастырамыз, массивтерді қарабайыр және анықтамалық типтерден сұрыптау әдістерінің айырмашылығы туралы білеміз, сонымен қатар осы мәселеде өте маңызды интерфейспен танысамыз Comparable;) Төменде сіз зерттей аласыз. деректер кестелерінің көмегімен логарифмдік масштабта құрастырылған график. Сызық неғұрлым тегіс болса, алгоритм соғұрлым жақсы болады =) Толық жобаны жүктеп алып, сынақтарды өз бетінше орындағысы келетіндер үшін сілтемені сақтаңыз: Java Келесі бөлімде кездескенше! =)