Saýlamak usullaryny gözden geçirmek we synagdan geçirmek. I bölüm

Beýleki gün, VKontakte baradaky teswirlerde taslamanyň beýleki talyplaryndan biri bilen jedel etdim. Jedeliň düýp manysy “kim ýeňer” - ýönekeý algoritmleri sort()synpdan java.util.Arraysýa-da özbaşdak ýazmagyň usuly: köpürjik , goýmak , saýlamak , gabyk (Shell algoritmi). Käbir adamlar üçin bu soraga jogap aç-açan bolup biler, ýöne jedel ýüze çykansoň, her tarapyň öz nukdaýnazaryndan "hormatlanýan çeşmelere" eýe bolandygyna garamazdan, çal meseläni uzadyp, barlag geçirmek kararyna gelindi. dürli algoritmleri durmuşa geçirmek. TL; DR: java.util.Arrays.sort() 100,000 element ýa-da ondanam köp massiwde şertsiz öňdebaryjydyr; kiçi göwrümli bolsa, “Shell” usuly käwagt onuň bilen bäsleşip biler. Göz öňünde tutulan algoritmleriň galan bölegi düýbünden boş we diňe käbir ekzotik şertlerde peýdaly bolup biler. Indi, kremniýli enjamlarymyzda massiwleriň nähili tertipleşdirilendigine seredeliň.

Saýlaw görnüşi. Saýlama boýunça tertiplemek

Iň ýönekeý we düşnükli usuldan başlalyň. Munuň düýp manysy, Robert Sedgwik tarapyndan kursdaky wideo leksiýasynda bize gaty gowy görkezildi (Gif-e erbet gysylan animasiýamy şol ýerden sitata bererin): Birinji elementden massiwiň üstünden ylgamak , her ädimimizde sag tarapdaky iň pes elementi gözläň, onuň bilen häzirki elementini çalyşýarys. Netijede, massiwimiziň soňky wersiýasyny tertipli görnüşde saklaýarys. Ine, bu algoritmi Java-da durmuşa geçirýän kod:

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;
    }

Algoritmiň seljermesi, her geçelgede massiwiň galan böleginden daralmagyň zerurdygyny görkezýär, ýagny bize takyk N + (N-1) + (N-2) + ... + 1 = N ^ 2/2 deňeşdirme. Şeýlelik bilen, algoritmiň çylşyrymlylygy O (N ^ 2). Bu näme many berýär? Diýmek, massiwdäki (N) elementleriň sanyny 2 esse köpeltmek bilen, algoritmiň işleýiş wagtyny 2 däl-de, 2 ^ 2 = 4 esse artdyrarys. N-ni 10 esse köpeltmek bilen, iş wagtyny 100 esse artdyrarys we ş.m. Ubuntu 14.4 işleýän Core i3 prosessorly 2012 noutbukymda aşakdaky iş wagtyny aldym:

Goýmagyň görnüşi. Goýmagyň görnüşi

Bu ýerde pikir birneme başga. Againene-de, Lukman Sedgwikiň animasiýasyna ýüzleneliň: Öňdäki zatlary henizem görmedik we yzda galdyrýan zatlarymyz hemişe tertipde galýar. Esasy zat, asyl massiwiň her täze elementini has kiçi elemente “bagly” bolýança başyna “gaýdyp” berýäris. Şeýlelik bilen, ýene-de N geçişlerimiz bar (asyl massiwiň her elementi üçin), ýöne her geçişde, köplenç galan bölegine däl-de, diňe bir bölegine seredýäris. .Agny, 1 + (N-1) + (N-2) +… + N = N ^ 2/2 wariantyny alarys, diňe her indiki elementi başyna, ýagny ýagdaýynda yzyna gaýtarmaly bolarys. girizişiň “tersine” massiwine (bagtsyz, bagtsyz) tertiplenen. Eýýäm tertipleşdirilen massiwde (ine, şowlulyk) doly erkinlik bolar - her geçişde diňe bir deňeşdirme bar we elementi ýerinde goýmak, ýagny algoritm N. bilen proporsional bir wagtda işlär. algoritmiň iň erbet teoretiki ýagdaýy, ýagny O (N ^ 2) bilen kesgitlener. Ortaça, iş wagty N ^ 2/4 bilen proporsional bolar, ýagny öňki algoritmden iki esse çalt. Durmuşa geçirişimde, permutasiýany optimal ulanmaýandygy sebäpli, iş wagty Saýlawdan has uzyn boldy. Soonakynda ýazgyny düzetmegi we täzelemegi meýilleşdirýärin. Ine, kod we şol bir enjamda işlemegiň netijesi:

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;
            }
        }
    }

Gabyk görnüşi. Gabyk görnüşi

Akylly ýigit Donald Şell 1959-njy ýylda goýmak üçin algoritmdäki iň gymmat ýagdaýlaryň elementiň massiwiň başyna gaty yza gaýdyp gelendigini görüpdir: käbir geçişlerde elementi iki pozisiýa bilen yzyna gaýtaryp berýäris. we başga bir geçelgede tutuş massiwden başyna çenli uzak we uzyn. Birnäçe elementden böküp, birbada edip bolarmy? Şeýle ýol tapdy. Adatça d-sort diýlip atlandyrylýan ýa-da Sedgwikiň pikiriçe, h-sort (h-hop diýmekdir öýdýän) yzygiderli ýerine ýetirilýän bölekleýin görnüşlerden ybarat. Mysal üçin, 3 görnüşli sorag elementi öňküsi bilen däl-de, ikisini geçer we bir 3 pozisiýa bilen deňeşdirer. Üýtgedilse, ony ýene 3 pozisiýa elementi bilen deňeşdirer we ş.m. Iň esasy, emele gelen massiw “3 görnüşli” bolar, ýagny elementleriň nädogry ýagdaýy 3 pozisiýadan az bolar. Bu goýmak algoritmi bilen işlemek aňsat we ýakymly bolar. Theeri gelende aýtsak, “1-sort” diňe bir goýmak algoritminden başga zat däl) Ine, görnüşi: Görmek Bu ýerdäki kynçylyk, bölekleýin görnüşleriň dogry yzygiderliligini nädip saýlamaly. Netijede, algoritmiň öndürijiligi şoňa baglydyr. Iň ýaýran zat, Donald Knut tarapyndan teklip edilen yzygiderlilik: h = h * 3 + 1, ýagny 1, 4, 13, 40, ... we ş.m. massiw ululygynyň 1/3 bölegine çenli. Bu yzygiderlilik oňat öndürijiligi üpjün edýär we durmuşa geçirmek hem aňsat. Algoritmiň derňewi tonna dil talap edýär we meniň mümkinçiligimden has ýokary. Derňewiň giňligi h yzygiderliliginiň köp görnüşi bilen hem kesgitlenýär. Empirik taýdan, algoritmiň tizliginiň gaty gowydygyny aýdyp bileris - özüňiz görüň: Bir sekuntdan az wagtyň içinde million element! Ine, Knut yzygiderliligi bilen Java kody.

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;
            }
        }
    }

Köpürjik görnüşi. Köpürjik usuly

Bu nusgawy! Her täze gelen programmist diýen ýaly bu algoritmi durmuşa geçirýär. Doktor Sedgwikiň hatda animasiýasy-da ýokdy, şonuň üçin eseri özüm etmeli boldum. Bu ýere serediň , her geçişde, tertibi ýok goňşy elementleri çalşyp, başyndan ahyryna çenli massiwden geçýäris. Netijede, iň uly elementler massiwiň ahyryna çenli “ýüzýär” (şonuň üçin ady). Her täze passany massiwiň eýýäm tertiplenendigine umyt edip umyt bilen başlaýarys sorted = true. Parçanyň soňunda ýalňyşlyk goýberendigimizi görsek, täze bir bölüme başlarys. Bu ýerdäki kynçylyk, ýene-de her geçişdäki ähli massiwden geçýäris. Deňeşdirme her ädimde bolup geçýär, alyş-çalyş her ädimde diýen ýaly bolup geçýär, bu bolsa bu algoritmi iň haýallaryň birine öwürýär (rasional durmuşa geçirilýänleri göz öňünde tutsak we “sarsmaz” we beýlekiler). Resmi taýdan bu ýerdäki çylşyrymlylygyň O (N ^ 2) bilen deň boljakdygy gyzykly, ýöne koeffisiýent goýulmalardan we saýlamalardan has ýokary. Algoritm kody:

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;
        }
    }

Iş wagty: Tapawudyny duýuň: million elementde ýarym sagatdan gowrak wagt! Netije: Hiç haçan bu algoritmi ulanmaň !!!

Birinji bölümiň gysgaça mazmuny

Netijede, bu algoritmler üçin umumy tablisa seretmegi maslahat berýärin. Gurlan usulyň netijeleri bilen deňeşdirip bilersiňiz java.util.Arrays.sort(). Bir hili jady ýaly görünýär - “Shell” -den has çalt näme bolup biler? Bu hakda indiki bölümde ýazaryn. Şol ýerde giňden ulanylýan çalt sort algoritmlerine serederis, şeýle hem sortlary birleşdireris, massiwleri başlangyç we salgy görnüşlerinden tertipleşdirmegiň usullarynyň tapawudyny öwreneris, şeýle hem bu meselede örän möhüm interfeýs bilen tanyşarys; Comparable) Aşakda öwrenip bilersiňiz maglumat tablisalaryny ulanyp logarifmiki şkalada gurlan grafik. Çyzyk tekizlese, algoritm şonça gowy =) Taslamany göçürip almak we özbaşdak synag geçirmek isleýänler üçin baglanyşygy saklaň: Java Indiki bölümde görüşeris! =)