Semakan dan ujian kaedah pengisihan. Bahagian I

Pada hari yang lain, dalam komen VKontakte, saya bertengkar dengan salah seorang pelajar lain projek itu. Intipati pertikaian ialah "siapa yang akan menang" - kaedah sort()daripada kelas java.util.Arraysatau pelaksanaan algoritma mudah yang ditulis sendiri: gelembung , sisipan , pemilihan , shell (algoritma Shell). Bagi sesetengah orang, jawapan kepada soalan ini mungkin jelas, tetapi sejak pertikaian itu timbul, walaupun pada hakikatnya setiap pihak mempunyai "sumber yang dihormati" yang memihak kepada sudut pandangannya, ia telah memutuskan untuk menjalankan kajian, meregangkan perkara kelabu dalam proses, melaksanakan pelbagai algoritma. TL;DR: java.util.Arrays.sort() ia adalah peneraju tanpa syarat pada tatasusunan 100,000 elemen atau lebih; ​​dengan saiz yang lebih kecil, kaedah Shell kadangkala boleh bersaing dengannya. Selebihnya algoritma yang dipertimbangkan adalah kosong sepenuhnya dan boleh berguna hanya dalam beberapa keadaan eksotik. Sekarang mari kita lihat bagaimana tatasusunan diisih dalam peranti uber silikon kami.

Isih pemilihan. Isih mengikut pilihan

Mari kita mulakan dengan kaedah yang paling mudah dan paling jelas. Intipatinya ditunjukkan dengan sempurna kepada kita oleh Robert Sedgwick dalam kuliah videonya tentang coursera (saya akan memetik animasi dari sana yang saya mampatkan dengan teruk menjadi gif): Lihat Menjalankan tatasusunan dari elemen pertama, pada setiap langkah kita cari elemen minimum di sebelah kanan, yang dengannya kita menukar elemen semasa. Akibatnya, kami menempah versi akhir tatasusunan kami dalam bentuk yang diisih. Berikut ialah kod yang melaksanakan algoritma ini dalam Java:

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

Analisis algoritma menunjukkan bahawa adalah perlu untuk menyisir baki tatasusunan pada setiap laluan, iaitu, kita memerlukan tepat N + (N-1) + (N-2) + ... + 1 = N^ 2/2 perbandingan. Oleh itu, kerumitan algoritma ialah O(N^2). Apakah maksud ini? Ini bermakna dengan menambah bilangan elemen dalam tatasusunan (N) sebanyak 2 kali, kita akan meningkatkan masa berjalan algoritma bukan sebanyak 2, tetapi sebanyak 2^2 = 4 kali. Dengan meningkatkan N sebanyak 10 kali, kami akan meningkatkan masa operasi sebanyak 100 kali, dan seterusnya. Pada komputer riba 2012 saya dengan pemproses Core i3 yang menjalankan Ubuntu 14.4, saya mendapat masa operasi berikut:

Isihan sisipan. Isihan sisipan

Di sini ideanya sedikit berbeza. Sekali lagi, mari kita beralih kepada animasi daripada Doctor Sedgwick: Lihat Apa yang di hadapan masih belum dilihat oleh kita lagi, dan semua yang kita tinggalkan sentiasa kekal teratur. Intinya ialah kita "mengembalikan" setiap elemen baharu tatasusunan asal ke permulaan sehingga ia "bersandar" pada elemen yang lebih kecil. Oleh itu, kita sekali lagi mempunyai N pas (untuk setiap elemen tatasusunan asal), tetapi dalam setiap pas, dalam kebanyakan kes, kita tidak melihat keseluruhan baki, tetapi hanya sebahagian. Iaitu, kita akan mendapat pilihan 1 + (N-1) + (N-2) + … + N = N^2/2 hanya jika kita perlu mengembalikan setiap elemen seterusnya ke permulaan, iaitu, dalam kes daripada input yang diisih tatasusunan "dalam songsang" (malang, malang). Dalam kes tatasusunan yang telah diisih (inilah nasib) akan ada freebie yang lengkap - pada setiap pas hanya terdapat satu perbandingan dan membiarkan elemen di tempatnya, iaitu, algoritma akan berfungsi dalam masa yang berkadar dengan N. Kerumitan algoritma akan ditentukan oleh kes teori yang paling teruk, iaitu, O(N^2). Secara purata, masa operasi akan berkadar dengan N^2/4, iaitu, dua kali lebih pantas daripada algoritma sebelumnya. Dalam pelaksanaan saya, disebabkan penggunaan pilihatur yang tidak optimum, masa berjalan lebih lama daripada Pemilihan. Saya bercadang untuk membetulkan dan mengemas kini siaran itu tidak lama lagi. Berikut ialah kod dan hasil operasinya pada mesin yang sama:

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

Isih cangkerang. Isih cangkerang

Seorang lelaki pintar, Donald Schell, menyedari pada tahun 1959 bahawa kes yang paling mahal dalam algoritma untuk sisipan adalah apabila elemen kembali sangat jauh ke permulaan tatasusunan: pada beberapa laluan kita mengembalikan elemen ke permulaan dengan beberapa kedudukan , dan pada satu lagi laluan hampir melalui keseluruhan tatasusunan ke permulaan adalah jauh dan panjang. Adakah mungkin untuk melakukan ini sekaligus, melompat melalui beberapa elemen? Dan dia menemui cara sedemikian. Ia terdiri daripada melakukan jenis separa khas secara berurutan, biasanya dipanggil jenis-d atau, menurut Sedgwick, jenis-h (saya mengesyaki h bermaksud lompat). 3-sort, sebagai contoh, akan membandingkan elemen yang dimaksudkan bukan dengan yang sebelumnya, tetapi akan melangkau dua dan membandingkan dengan satu 3 kedudukan kembali. Jika diubah, ia akan membandingkannya semula dengan kedudukan elemen 3 kembali dan seterusnya. Intinya ialah tatasusunan yang terhasil akan menjadi "3-isih", iaitu, kedudukan elemen yang salah akan kurang daripada 3 kedudukan. Bekerja dengan algoritma sisipan ini akan menjadi mudah dan menyenangkan. By the way, "1-sort" tidak lebih daripada sekadar algoritma sisipan =) Dengan menggunakan h-sort secara berurutan pada tatasusunan dengan penurunan nilai h, kita boleh mengisih tatasusunan yang besar dengan lebih cepat. Begini rupanya: Lihat Cabaran di sini ialah cara memilih urutan jenis separa yang betul. Akhirnya, prestasi algoritma bergantung pada ini. Yang paling biasa ialah jujukan yang dicadangkan oleh Donald Knuth: h = h*3 + 1, iaitu, 1, 4, 13, 40, ... dan seterusnya sehingga 1/3 daripada saiz tatasusunan. Urutan ini memberikan prestasi yang baik dan juga mudah untuk dilaksanakan. Analisis algoritma memerlukan banyak bahasa dan di luar kemampuan saya. Keluasan analisis juga ditentukan oleh banyak variasi jujukan h. Secara empirik, kita boleh mengatakan bahawa kelajuan algoritma adalah sangat baik - lihat sendiri: Sejuta elemen dalam masa kurang dari satu saat! Dan inilah kod Java dengan urutan Knut.

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

Isih gelembung. Kaedah gelembung

Ini adalah klasik! Hampir setiap pengaturcara pemula melaksanakan algoritma ini. Ia sangat klasik sehingga Dr. Sedgwick tidak mempunyai animasi untuknya, jadi saya terpaksa melakukan kerja itu sendiri. Lihat Di sini, pada setiap laluan, kami melintasi tatasusunan dari awal hingga akhir, menukar elemen jiran yang tidak teratur. Akibatnya, elemen terbesar "terapung" (oleh itu namanya) ke penghujung tatasusunan. Kami memulakan setiap pas baharu dengan optimis berharap tatasusunan sudah diisih ( sorted = true). Di penghujung petikan, jika kita melihat bahawa kita telah melakukan kesilapan, kita mulakan laluan baru. Kesukaran di sini ialah, sekali lagi, kita sedang melintasi (hampir) keseluruhan tatasusunan pada setiap laluan. Perbandingan berlaku pada setiap langkah, pertukaran berlaku pada hampir setiap langkah, yang menjadikan algoritma ini salah satu yang paling perlahan (jika kita menganggap yang dilaksanakan secara rasional, dan bukan "goncang jenis" dan lain-lain seperti itu). Adalah menarik bahawa secara rasmi kerumitan di sini juga akan sama dengan O(N^2), tetapi pekalinya jauh lebih tinggi daripada sisipan dan pemilihan. Kod algoritma:

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

Masa operasi: Rasai perbezaannya: lebih daripada setengah jam pada sejuta elemen! Kesimpulan: Jangan gunakan algoritma ini!!!

Ringkasan bahagian pertama

Akibatnya, saya cadangkan melihat jadual umum untuk algoritma ini. Anda juga boleh membandingkan dengan keputusan untuk kaedah terbina dalam java.util.Arrays.sort(). Ia kelihatan seperti sejenis sihir - apakah yang lebih pantas daripada Shell? Saya akan menulis tentang ini di bahagian seterusnya. Di sana kita akan melihat algoritma pengisihan pantas yang digunakan secara meluas, serta pengisihan gabungan, belajar tentang perbezaan kaedah untuk menyusun tatasusunan daripada jenis primitif dan rujukan, dan juga berkenalan dengan antara muka yang sangat penting dalam perkara ini Comparable;) Di bawah ini anda boleh belajar graf yang dibina pada skala logaritma menggunakan jadual data. Lebih rata garis, lebih baik algoritma =) Bagi mereka yang ingin memuat turun keseluruhan projek dan menjalankan ujian sendiri, simpan pautan: Java Jumpa anda di bahagian seterusnya! =)