Сорттоо ыкмаларын карап чыгуу жана сыноо. I бөлүк

Өткөн күнү ВКонтактедеги комментарийлерде долбоордун башка студенттеринин бири менен урушуп кеттим. Талаш-тартыштын маңызы "ким жеңет" болгон - sort()класстын ыкмасы java.util.Arraysже жөнөкөй алгоритмдердин өз алдынча жазылган ишке ашырылышы: көбүк , киргизүү , тандоо , кабык (Shell алгоритми). Кээ бирөөлөр үчүн бул суроонун жообу ачык болушу мүмкүн, бирок талаш-тартыштар жаралгандыктан, ар бир тарап өз көз карашын жактаган “урматтуу булактарга” карабастан, боз затты сунуп, изилдөө жүргүзүү чечими кабыл алынган. процесс, ар кандай алгоритмдерди ишке ашыруу. TL; DR: java.util.Arrays.sort() ал 100 000 же андан көп элементтерден турган массивдерде шартсыз лидер болуп саналат; кичине өлчөмү менен Shell ыкмасы кээде аны менен атаандаша алат. Калган каралып жаткан алгоритмдер толугу менен бош жана кээ бир экзотикалык шарттарда гана пайдалуу болушу мүмкүн. Эми кремний убер-түзмөктөрүбүздө массивдер кандай иреттелгенин карап көрөлү.

Тандоо сорту. Тандоо боюнча сорттоо

Эң жөнөкөй жана эң айкын ыкмадан баштайлы. Анын маңызын бизге Роберт Седгвик өзүнүн курсра боюнча видеолекциясында эң сонун көрсөтүп турат (мен анимацияны gifге жаман кысып алганымдан цитата кылам): Көрүү Биринчи элементтен массив аркылуу чуркап, ар бир кадамда биз оң тараптан минималдуу элементти издеңиз, анын жардамы менен биз учурдагыны алмаштырабыз. Натыйжада, биз массивибиздин акыркы versionсын иреттелген формада сактайбыз. Бул жерде 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 вариантын алабыз, эгерде биз ар бир кийинки элементти эң башына кайтарышыбыз керек болсо, б.а. Киргизүүнүн “тескери” массивинде иреттелген (бактысыз, ийгorксиз). Буга чейин сорттолгон массивде (бул жерде ийгorк) толук акысыз болот - ар бир өтүүдө бир гана салыштыруу жана элементти өз ордунда калтыруу болот, башкача айтканда, алгоритм 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;
            }
        }
    }

Shell сорттоо. Shell сорттоо

Акылдуу жигит Дональд Шелл 1959-жылы кыстаруу алгоритминдеги эң кымбат учурлар элемент массивдин башына өтө алыс кайтып келгенде экенин байкаган: кээ бир өтүүдө биз элементти бир нече позиция менен башына кайтарабыз. , жана башка өтүү дээрлик бүт массив аркылуу башталышы алыс жана узун. Муну бир эле учурда бир нече элементтерден өтүү мүмкүнбү? Жана ал ушундай жолду тапты. Ал жалпысынан d-сорт же Седгвик боюнча h-сорт деп аталган атайын жарым-жартылай сортторду ырааттуу аткаруудан турат (мен h-хоп дегенди билдирет деп ойлойм). 3-сорт, мисалы, каралып жаткан элементти мурункусу менен эмес, экөөнү өткөрүп жиберип, кайра 3 позиция менен салыштырат. Эгерде өзгөртүлсө, ал аны кайра 3-элементтин орду менен кайра салыштырат жана башкалар. Жыйынтыгында пайда болгон массив “3 сорттуу” болот, башкача айтканда, элементтердин туура эмес жайгашуусу 3 позициядан аз болот. Бул киргизүү алгоритми менен иштөө жеңил жана жагымдуу болот. Айтмакчы, “1-сорт” жөн гана киргизүү алгоритминен башка эч нерсе эмес =) h маанисин азайтуу менен массивге h-сортту ырааттуу колдонуу менен биз чоң массивди тезирээк сорттой алабыз. Бул кандай көрүнөт: Көрүү Бул жердеги маселе жарым-жартылай сорттордун туура ырааттуулугун кантип тандоо керек. Акыр-аягы, алгоритмдин иштеши ушундан көз каранды. Эң кеңири таралганы Дональд Кнут тарабынан сунушталган ырааттуулук: h = h*3 + 1, башкача айтканда, 1, 4, 13, 40, ... жана башкалар массивдин 1/3 бөлүгүнө чейин. Бул ырааттуулук татыктуу аткарууну камсыз кылат жана ишке ашыруу үчүн да жеңил. Алгоритмдин анализи бир нече тонна тилди талап кылат жана менин мүмкүнчүлүгүмдөн тышкары. Анализдин кеңдиги ч тизмектеринин көп варианттары менен да аныкталат. Эмпирикалык түрдө алгоритмдин ылдамдыгы абдан жакшы деп айта алабыз - өзүңүз көрүңүз: Бир секундага жетпеген убакытта миллион элемент! Жана бул жерде 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;
        }
    }

Иштөө убактысы: Айырмачылыкты сезиңиз: миллион элементтерде жарым сааттан ашык убакыт! Жыйынтык: Бул алгоритмди эч качан колдонбоңуз!!!

Биринчи бөлүктүн корутундусу

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