Review dan pengujian metode penyortiran. Bagian I

Suatu hari, di komentar di VKontakte, saya berdebat dengan salah satu siswa proyek lainnya. Inti dari perselisihan ini adalah "siapa yang akan menang" - sebuah metode sort()dari kelas java.util.Arraysatau implementasi algoritma sederhana yang ditulis sendiri: bubble , penyisipan , seleksi , shell (algoritma Shell). Bagi sebagian orang, jawaban atas pertanyaan ini mungkin sudah jelas, namun karena perselisihan muncul, terlepas dari kenyataan bahwa masing-masing pihak memiliki “sumber yang dihormati” yang mendukung sudut pandangnya, maka diputuskan untuk melakukan penelitian, memperluas masalah abu-abu ke dalam masalah. prosesnya, mengimplementasikan berbagai algoritma. TL;DR: java.util.Arrays.sort() tanpa syarat ia adalah pemimpin dalam array yang terdiri dari 100.000 elemen atau lebih; ​​dengan ukuran yang lebih kecil, metode Shell terkadang dapat bersaing dengannya. Algoritme lainnya yang dipertimbangkan benar-benar kosong dan hanya dapat berguna dalam kondisi eksotik tertentu. Sekarang mari kita lihat bagaimana array diurutkan di perangkat uber silikon kita.

Sortir seleksi. Menyortir berdasarkan pilihan

Mari kita mulai dengan metode yang paling sederhana dan jelas. Esensinya ditunjukkan dengan sempurna kepada kita oleh Robert Sedgwick dalam video ceramahnya tentang coursera (saya akan mengutip animasi dari sana yang saya kompresi dengan buruk menjadi gif): Lihat Menjalankan array dari elemen pertama, di setiap langkah kita cari elemen minimum di sisi kanan, yang dengannya kita menukar elemen saat ini. Hasilnya, kami memesan versi final array kami dalam bentuk yang diurutkan. Berikut adalah kode yang mengimplementasikan algoritma ini di 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 algoritme menunjukkan bahwa perlu menyisir sisa array pada setiap lintasan, yaitu, kita memerlukan N + (N-1) + (N-2) + ... + 1 = N^ 2/2 perbandingan. Jadi, kompleksitas algoritmanya adalah O(N^2). Apa artinya ini? Artinya dengan menambah jumlah elemen dalam array (N) sebanyak 2 kali, kita akan menambah waktu berjalan algoritma bukan sebanyak 2, tetapi sebanyak 2^2 = 4 kali. Dengan menambah N sebanyak 10 kali lipat, kita akan menambah waktu pengoperasian sebanyak 100 kali lipat, dan seterusnya. Pada laptop 2012 saya dengan prosesor Core i3 yang menjalankan Ubuntu 14.4, saya mendapatkan uptime berikut:

Sortir penyisipan. Sortir penyisipan

Di sini idenya sedikit berbeda. Sekali lagi, mari kita beralih ke animasi dari Doctor Sedgwick: Lihat Apa yang ada di depan bahkan belum kita lihat, dan segala sesuatu yang kita tinggalkan selalu tetap teratur. Intinya adalah kita “mengembalikan” setiap elemen baru dari array asli ke awal hingga “bertumpu” pada elemen yang lebih kecil. Jadi, kita kembali memiliki N lintasan (untuk setiap elemen larik asli), tetapi dalam setiap lintasan, dalam banyak kasus, kita tidak melihat keseluruhan sisanya, tetapi hanya sebagian. Artinya, kita akan mendapatkan opsi 1 + (N-1) + (N-2) + … + N = N^2/2 hanya jika kita harus mengembalikan setiap elemen berikutnya ke awal, yaitu dalam kasus dari input yang diurutkan dalam array “terbalik” (sial, sial). Dalam kasus array yang sudah diurutkan (inilah keberuntungan) akan ada freebie lengkap - pada setiap lintasan hanya ada satu perbandingan dan membiarkan elemen di tempatnya, yaitu algoritma akan bekerja dalam waktu yang sebanding dengan N. Kompleksitas algoritma akan ditentukan oleh kasus teoritis terburuk, yaitu O( N^2). Rata-rata, waktu pengoperasian akan sebanding dengan N^2/4, yaitu dua kali lebih cepat dari algoritma sebelumnya. Pada implementasi saya, karena penggunaan permutasi yang tidak optimal, waktu berjalan lebih lama dibandingkan Seleksi. Saya berencana untuk segera memperbaiki dan memperbarui postingan tersebut. Berikut kode dan hasil pengoperasiannya 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;
            }
        }
    }

Jenis cangkang. Jenis cangkang

Seorang yang cerdas, Donald Schell, memperhatikan pada tahun 1959 bahwa kasus yang paling mahal dalam algoritma untuk penyisipan adalah ketika elemen kembali sangat jauh ke awal array: pada beberapa lintasan kita mengembalikan elemen ke awal dengan beberapa posisi , dan di jalur lain melewati hampir seluruh larik ke awal sangatlah jauh dan panjang. Apakah mungkin melakukan ini sekaligus, melewati beberapa elemen? Dan dia menemukan cara seperti itu. Ini terdiri dari pelaksanaan pengurutan parsial khusus secara berurutan, umumnya disebut pengurutan-d atau, menurut Sedgwick, pengurutan-h (saya kira h berarti hop). 3-sort, misalnya, akan membandingkan elemen yang dimaksud bukan dengan elemen sebelumnya, tetapi akan melewati dua elemen dan membandingkannya dengan elemen yang 3 posisi ke belakang. Jika diubah akan dibandingkan lagi dengan elemen 3 posisi ke belakang dan seterusnya. Intinya adalah array yang dihasilkan akan “diurutkan ke-3”, yaitu posisi elemen yang salah akan kurang dari 3 posisi. Bekerja dengan algoritma penyisipan ini akan mudah dan menyenangkan. Omong-omong, “1-sort” tidak lebih dari sekedar algoritma penyisipan =) Dengan menerapkan h-sort secara berurutan ke array dengan nilai h yang menurun, kita dapat mengurutkan array besar dengan lebih cepat. Begini tampilannya: Lihat Tantangannya di sini adalah bagaimana memilih urutan pengurutan parsial yang tepat. Pada akhirnya, kinerja algoritma bergantung pada hal ini. Yang paling umum adalah urutan yang diusulkan oleh Donald Knuth: h = h*3 + 1, yaitu 1, 4, 13, 40, ... dan seterusnya hingga 1/3 dari ukuran array. Urutan ini memberikan kinerja yang layak dan juga mudah diterapkan. Analisis algoritme memerlukan banyak bahasa dan berada di luar kemampuan saya. Luasnya analisis juga ditentukan oleh banyaknya varian barisan h. Secara empiris, kita dapat mengatakan bahwa kecepatan algoritmanya sangat baik - lihat sendiri: Satu juta elemen dalam waktu kurang dari satu detik! Dan berikut adalah kode Java dengan sequence Knutnya.

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

Sortir gelembung. Metode gelembung

Ini klasik! Hampir setiap programmer pemula mengimplementasikan algoritma ini. Ini sangat klasik sehingga Dr. Sedgwick bahkan tidak memiliki animasinya, jadi saya harus mengerjakannya sendiri. Lihat Di sini, pada setiap lintasan, kita menelusuri array dari awal hingga akhir, menukar elemen tetangga yang tidak berurutan. Hasilnya, elemen terbesar “mengambang” (sesuai dengan namanya) ke akhir array. Kami memulai setiap lintasan baru dengan optimis dengan harapan bahwa array sudah diurutkan ( sorted = true). Di akhir bacaan, jika kita melihat bahwa kita telah melakukan kesalahan, kita memulai bacaan baru. Kesulitannya di sini adalah, sekali lagi, kita melintasi (hampir) seluruh array pada setiap lintasan. Perbandingan terjadi di setiap langkah, pertukaran terjadi di hampir setiap langkah, yang menjadikan algoritma ini salah satu yang paling lambat (jika kita mempertimbangkan implementasi yang rasional, dan bukan “shaking sort” dan sejenisnya). Menariknya, secara formal kompleksitas di sini juga akan sama dengan O(N^2), namun koefisiennya jauh lebih tinggi dibandingkan dengan penyisipan dan seleksi. Kode 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;
        }
    }

Waktu pengoperasian: Rasakan perbedaannya: lebih dari setengah jam untuk sejuta elemen! Kesimpulan: Jangan pernah gunakan algoritma ini!!!

Ringkasan bagian pertama

Oleh karena itu, saya sarankan untuk melihat tabel umum untuk algoritma ini. Anda juga dapat membandingkan dengan hasil metode bawaan java.util.Arrays.sort(). Sepertinya semacam keajaiban - apa yang bisa lebih cepat dari Shell? Saya akan menulis tentang ini di bagian selanjutnya. Di sana kita akan melihat algoritma pengurutan cepat yang banyak digunakan, serta pengurutan gabungan, mempelajari perbedaan metode pengurutan array dari tipe primitif dan referensi, dan juga berkenalan dengan antarmuka yang sangat penting dalam hal ini ;) Di Comparablebawah ini Anda dapat mempelajari grafik yang dibangun pada skala logaritmik menggunakan tabel data. Semakin datar garisnya, semakin baik algoritmanya =) Bagi mereka yang ingin mengunduh seluruh proyek dan menjalankan tes sendiri, simpan tautannya: Java Sampai jumpa di bagian selanjutnya! =)