Saralash usullarini ko'rib chiqish va sinovdan o'tkazish. I qism

Boshqa kuni "VKontakte" dagi sharhlarda men loyihaning boshqa talabalaridan biri bilan bahslashdim. Bahsning mohiyati "kim g'alaba qozonadi" edi - sort()sinfdan olingan usul java.util.Arraysyoki oddiy algoritmlarning o'z-o'zidan yozilgan ilovalari: qabariq , qo'shish , tanlash , qobiq (Shell algoritmi). Ba'zilar uchun bu savolning javobi aniq bo'lishi mumkin, ammo nizo kelib chiqqanligi sababli, har bir tomon o'z nuqtai nazarini qo'llab-quvvatlagan "hurmatli manbalarga" ega bo'lishiga qaramay, kulrang materiyani cho'zgan holda tadqiqot o'tkazishga qaror qilindi. jarayon, turli xil algoritmlarni amalga oshirish. TL; DR: java.util.Arrays.sort() u 100 000 yoki undan ortiq elementli massivlar bo'yicha so'zsiz etakchi hisoblanadi; kichikroq o'lcham bilan Shell usuli ba'zan u bilan raqobatlasha oladi. Ko'rib chiqilgan algoritmlarning qolgan qismi butunlay bo'sh va faqat ba'zi ekzotik sharoitlarda foydali bo'lishi mumkin. Endi silikon uber-qurilmalarimizda massivlar qanday tartiblanganligini ko'rib chiqamiz.

Tanlash tartibi. Tanlov bo'yicha saralash

Keling, eng oddiy va eng aniq usuldan boshlaylik. Buning mohiyatini bizga Robert Sedgvik o'zining kursra haqidagi videoma'ruzasida juda yaxshi ko'rsatib berdi (men u yerdan gifga yomon siqilgan animatsiyani keltiraman): Ko'rish Birinchi elementdan massiv bo'ylab yugurish, har bir qadamda biz o'ng tomonda minimal elementni qidiring, u bilan biz joriy elementni almashtiramiz. Natijada, biz massivimizning yakuniy versiyasini tartiblangan shaklda saqlab qo'yamiz. Mana Java-da ushbu algoritmni amalga oshiradigan 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;
    }

Algoritm tahlili shuni ko'rsatadiki, har bir o'tishda massivning qolgan qismini tarash kerak, ya'ni bizga aniq N + (N-1) + (N-2) + ... + 1 = N ^ kerak bo'ladi. 2/2 taqqoslash. Shunday qilib, algoritmning murakkabligi O(N^2). Bu qanday ma'nono bildiradi? Demak, massivdagi elementlar sonini (N) 2 marta oshirsak, algoritmning ishlash vaqtini 2 ga emas, balki 2^2 = 4 martaga oshiramiz. N ni 10 marta oshirib, biz ish vaqtini 100 barobarga oshiramiz va hokazo. Ubuntu 14.4 bilan ishlaydigan Core i3 protsessorli 2012 yilgi noutbukimda men quyidagi ish vaqtini oldim:

Kiritish tartibi. Kiritish tartibi

Bu erda fikr biroz boshqacha. Yana Doktor Sedgvikning animatsiyasiga murojaat qilaylik: Oldinda nima borligini biz hali ko'rmaganmiz va biz ortda qoldirgan hamma narsa doimo tartibda bo'ladi. Gap shundaki, biz asl massivning har bir yangi elementini kichikroq elementga “dam olguncha” boshiga “qaytaramiz”. Shunday qilib, bizda yana N ta o'tish bor (asl massivning har bir elementi uchun), lekin har bir o'tishda, ko'p hollarda, biz butun qoldiqni emas, balki faqat bir qismini ko'rib chiqamiz. Ya'ni, biz 1 + (N-1) + (N-2) + … + N = N ^ 2/2 variantini olamiz, agar biz har bir keyingi elementni eng boshiga qaytarishimiz kerak bo'lsa, ya'ni vaziyatda "teskari" massivda tartiblangan kirishning (omadsiz, omadsiz). Allaqachon tartiblangan massivda (bu yerda omad) to'liq bepul bo'ladi - har bir o'tishda faqat bitta taqqoslash va elementni joyida qoldirish mavjud, ya'ni algoritm N ga mutanosib vaqt ichida ishlaydi. Murakkablik Algoritmning eng yomon nazariy holati, ya'ni O( N^2) bilan aniqlanadi. O'rtacha ish vaqti N ^ 2/4 ga mutanosib bo'ladi, ya'ni oldingi algoritmdan ikki baravar tez. Mening amalga oshirishimda, almashtirishdan optimal foydalanilmaganligi sababli, ish vaqti Tanlash vaqtiga qaraganda uzoqroq edi. Tez orada postni tuzatish va yangilashni rejalashtiryapman. Mana kod va uning bir xil mashinada ishlashi natijasi:

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 tartiblash. Shell tartiblash

Donald Shell ismli aqlli yigit 1959 yilda qo'shish algoritmidagi eng qimmat holatlar element massiv boshiga juda uzoqqa qaytganida ekanligini payqadi: ba'zi bir o'tishda biz elementni bir nechta pozitsiyalar bilan boshiga qaytaramiz. , va boshqa o'tish deyarli butun massiv orqali boshiga uzoq va uzoq. Bir vaqtning o'zida bir nechta elementlardan o'tib, buni qilish mumkinmi? Va u shunday yo'l topdi. Bu, odatda, d-sort yoki, Sedgwickga ko'ra, h-sort deb ataladigan maxsus qisman navlarni ketma-ket bajarishdan iborat (men gumon qilamanki, h hop degan ma'noni anglatadi). 3-sort, masalan, ko'rib chiqilayotgan elementni avvalgisi bilan taqqoslamaydi, lekin ikkitasini o'tkazib yuboradi va 3 pozitsiyasi bilan solishtiradi. Agar o'zgartirilsa, u uni yana 3-elementning orqadagi pozitsiyalari bilan taqqoslaydi va hokazo. Xulosa shuki, natijada olingan massiv "3-tartibli" bo'ladi, ya'ni elementlarning noto'g'ri joylashuvi 3 pozitsiyadan kam bo'ladi. Ushbu kiritish algoritmi bilan ishlash oson va yoqimli bo'ladi. Aytgancha, “1-sort” qo‘shish algoritmidan boshqa narsa emas =) h qiymatini kamaytiruvchi massivga h-sortni ketma-ket qo‘llash orqali biz katta massivni tezroq saralashimiz mumkin. Bu shunday ko'rinadi: Ko'rish Bu erda qiyinchilik qisman turlarning to'g'ri ketma-ketligini qanday tanlashdir. Oxir oqibat, algoritmning ishlashi bunga bog'liq. Eng keng tarqalgani Donald Knut tomonidan taklif qilingan ketma-ketlikdir: h = h*3 + 1, ya'ni 1, 4, 13, 40, ... va hokazo massiv hajmining 1/3 qismigacha. Ushbu ketma-ketlik munosib ishlashni ta'minlaydi va amalga oshirish ham oson. Algoritmni tahlil qilish juda ko'p tilni talab qiladi va mening qobiliyatimdan tashqarida. Tahlilning kengligi h ketma-ketlikning ko'p variantlari bilan ham belgilanadi. Empirik tarzda aytishimiz mumkinki, algoritm tezligi juda yaxshi - o'zingiz ko'ring: Bir soniyadan kamroq vaqt ichida million element! Va bu erda Knut ketma-ketligi bilan Java kodi.

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

Pufakcha tartiblash. Pufak usuli

Bu klassika! Deyarli har bir yangi boshlovchi dasturchi ushbu algoritmni amalga oshiradi. Bu shunday klassikki, doktor Sedgvikda buning uchun animatsiya ham yo'q edi, shuning uchun men ishni o'zim qilishim kerak edi. Bu yerda ko'ring , har bir o'tishda biz massivni boshidan oxirigacha kesib o'tamiz, tartibsiz qo'shni elementlarni almashtiramiz. Natijada, eng katta elementlar massivning oxirigacha "suzadi" (shuning uchun nomi). Biz har bir yangi o'tishni massiv allaqachon tartiblangan ( sorted = true) deb umid qilib, optimistik tarzda boshlaymiz. Parcha oxirida xato qilganimizni ko'rsak, yangi parcha boshlaymiz. Bu erda qiyinchilik shundaki, biz har bir o'tishda yana (deyarli) butun massivni bosib o'tamiz. Taqqoslash har bir qadamda sodir bo'ladi, almashish deyarli har bir qadamda sodir bo'ladi, bu esa ushbu algoritmni eng sekinlardan biriga aylantiradi (agar biz "silkituvchi tartib" va boshqalarni emas, balki oqilona amalga oshirilganlarini hisobga olsak). Qizig'i shundaki, rasmiy ravishda bu erda murakkablik O (N ^ 2) ga teng bo'ladi, ammo koeffitsient qo'shish va tanlashga qaraganda ancha yuqori. Algoritm kodi:

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

Ishlash vaqti: Farqni his eting: million elementda yarim soatdan ko'proq! Xulosa: Hech qachon bu algoritmdan foydalanmang!!!

Birinchi qismning qisqacha mazmuni

Natijada, men ushbu algoritmlar uchun umumiy jadvalga qarashni taklif qilaman. Shuningdek, siz o'rnatilgan usul natijalari bilan solishtirishingiz mumkin java.util.Arrays.sort(). Bu qandaydir sehrga o'xshaydi - Shelldan tezroq nima bo'lishi mumkin? Bu haqda keyingi qismda yozaman. U erda biz keng qo'llaniladigan tezkor tartiblash algoritmlarini ko'rib chiqamiz, shuningdek, birlashtirish tartibini ko'rib chiqamiz, massivlarni primitivlar va mos yozuvlar turlaridan saralash usullarining farqi haqida bilib olamiz, shuningdek, bu masalada juda muhim interfeys bilan tanishamiz Comparable;) Quyida siz o'rganishingiz mumkin. ma'lumotlar jadvallari yordamida logarifmik shkalada qurilgan grafik. Chiziq qanchalik tekis bo'lsa, algoritm shunchalik yaxshi bo'ladi =) Butun loyihani yuklab olib, mustaqil ravishda testlarni o'tkazmoqchi bo'lganlar uchun havolani saqlang: Java Keyingi qismda ko'rishguncha! =)