Quicksort vs heapsort

Quicksort dan heapsort melakukan penyortiran di tempat. Mana yang lebih baik? Apa aplikasi dan kasus mana yang lebih disukai?

Makalah ini memiliki beberapa analisis.

Juga, dari Wikipedia:

Pesaing langsung quicksort adalah heapsort. Heapsort biasanya agak lebih lambat daripada quicksort, tetapi waktu pengoperasian terburuk selalu Θ (nlogn). Quicksort biasanya lebih cepat, meskipun masih ada kemungkinan performa kasus terburuk kecuali dalam varian introsort, yang beralih ke heapsort saat kasus buruk terdeteksi. Jika sebelumnya diketahui bahwa heapsort akan diperlukan, menggunakannya secara langsung akan lebih cepat daripada menunggu introsort untuk beralih ke heapsort.

Heapsort dijamin O (N log N), yang jauh lebih baik daripada kasus terburuk di Quicksort. Heapsort tidak membutuhkan lebih banyak memori untuk array lain untuk meletakkan data yang diurutkan seperti yang dibutuhkan oleh Mergesort. Jadi mengapa aplikasi komersial tetap menggunakan Quicksort? Quicksort apa yang begitu istimewa dibandingkan implementasi lainnya?

Saya telah menguji algoritme sendiri dan saya telah melihat bahwa Quicksort memang memiliki sesuatu yang istimewa. Ini berjalan cepat, jauh lebih cepat daripada algoritma Heap and Merge.

Rahasia Quicksort adalah: Ia hampir tidak melakukan pertukaran elemen yang tidak perlu. Swap memakan waktu.

Dengan Heapsort, meskipun semua data Anda sudah diurutkan, Anda akan menukar 100% elemen untuk mengurutkan array.

Dengan Mergesort, lebih buruk lagi. Anda akan menulis 100% elemen di larik lain dan menuliskannya kembali di larik asli, meskipun data sudah diurutkan.

Dengan Quicksort Anda tidak menukar apa yang sudah dipesan. Jika data Anda benar-benar terurut, Anda hampir tidak menukar! Meskipun ada banyak keributan tentang kasus terburuk, sedikit perbaikan pada pilihan pivot, selain mendapatkan elemen array pertama atau terakhir, dapat menghindarinya. Jika Anda mendapatkan pivot dari elemen perantara antara elemen pertama, terakhir dan tengah, itu sudah cukup untuk menghindari kasus terburuk.

Apa yang diunggulkan di Quicksort bukanlah kasus terburuk, tetapi kasus terbaik! Dalam kasus terbaik Anda melakukan jumlah perbandingan yang sama, ok, tetapi Anda hampir tidak menukar. Dalam kasus rata-rata Anda menukar sebagian elemen, tetapi tidak semua elemen, seperti di Heapsort dan Mergesort. Itulah yang memberi Quicksort waktu terbaik. Lebih sedikit pertukaran, lebih cepat.

Implementasi di bawah ini dalam C # di komputer saya, berjalan pada mode rilis, mengalahkan Array. Urutkan 3 detik dengan pivot tengah dan 2 detik dengan pivot yang ditingkatkan (ya, ada overhead untuk mendapatkan pivot yang baik).

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}

Untuk sebagian besar situasi, memiliki kecepatan vs. sedikit lebih cepat tidaklah relevan ... Anda tidak pernah ingin sesekali menjadi lambat. Meskipun Anda dapat mengubah QuickSort untuk menghindari situasi lambat, Anda kehilangan keanggunan QuickSort dasar. Jadi, untuk sebagian besar hal, saya sebenarnya lebih suka HeapSort ... Anda dapat menerapkannya dalam keanggunan sederhana sepenuhnya, dan tidak pernah mendapatkan cara yang lambat.

Untuk situasi di mana Anda INGIN menginginkan kecepatan maksimal dalam banyak kasus, QuickSort mungkin lebih disukai daripada HeapSort, tetapi tidak ada jawaban yang tepat. Untuk situasi yang kritis terhadap kecepatan, ada baiknya memeriksa detail situasinya dengan cermat. Misalnya, dalam beberapa kode kritis-kecepatan saya, sangat umum bahwa datanya sudah diurutkan atau hampir diurutkan (ini mengindeks beberapa bidang terkait yang sering bergerak naik dan turun bersama ATAU bergerak naik dan turun berlawanan satu sama lain, jadi setelah Anda mengurutkan berdasarkan satu, yang lain akan diurutkan atau diurutkan terbalik atau ditutup ... salah satunya dapat mematikan QuickSort). Untuk kasus itu, saya tidak menerapkan keduanya ... sebagai gantinya, saya mengimplementasikan SmoothSort Dijkstra ... varian HeapSort yang O (N) ketika sudah diurutkan atau hampir diurutkan ... tidak begitu elegan, tidak terlalu mudah dipahami, tapi cepat ... bacahttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF jika Anda menginginkan sesuatu yang lebih menantang untuk dikodekan.

Quicksort-Heapsort in-place hybrid juga sangat menarik, karena kebanyakan dari mereka hanya membutuhkan perbandingan n * log n dalam kasus terburuk (mereka optimal sehubungan dengan istilah pertama dari asimtotik, sehingga mereka menghindari skenario terburuk dari Quicksort), O (log n) ruang ekstra dan mereka mempertahankan setidaknya "setengah" dari perilaku baik Quicksort sehubungan dengan kumpulan data yang sudah diurutkan. Algoritme yang sangat menarik disajikan oleh Dikert dan Weiss di http://arxiv.org/pdf/1209.4214v1.pdf :

• Pilih pivot p sebagai median dari sampel acak elemen sqrt (n) (ini dapat dilakukan paling banyak 24 sqrt (n) perbandingan melalui algoritma Tarjan & co, atau perbandingan 5 sqrt (n) melalui laba-laba yang jauh lebih berbelit-belit algoritma -factory Schonhage);
• Partisi larik Anda dalam dua bagian seperti pada langkah pertama Quicksort;
• Heapifikasi bagian terkecil dan gunakan O (log n) bit ekstra untuk menyandikan heap di mana setiap anak kiri memiliki nilai yang lebih besar dari saudaranya;
• Ekstrak akar tumpukan secara rekursif, saring lacune yang ditinggalkan oleh akar hingga mencapai daun tumpukan, lalu isi lacune dengan elemen yang sesuai yang diambil dari bagian lain dari larik;
• Perulangan atas sisa bagian tak berurutan dari larik (jika p dipilih sebagai median yang tepat, tidak ada rekursi sama sekali).

Comp. antara quick sortdan merge sortkarena keduanya adalah jenis penyortiran di tempat, ada perbedaan antara waktu pengoperasian wrost case dari waktu pengoperasian wrost case untuk pengurutan cepat O(n^2)dan untuk penyortiran heap masih O(n*log(n))dan untuk jumlah rata-rata data pengurutan cepat akan lebih berguna. Karena ini adalah algoritma acak sehingga kemungkinan mendapatkan jawaban yang benar. dalam waktu yang lebih singkat akan tergantung pada posisi elemen pivot yang Anda pilih.

Jadi a

Keputusan yang bagus: ukuran L dan G masing-masing kurang dari 3s / 4

Panggilan buruk: salah satu L dan G berukuran lebih besar dari 3s / 4

untuk jumlah kecil, kita dapat menggunakan jenis penyisipan dan untuk jumlah data yang sangat besar menggunakan jenis tumpukan.

Heapsort memiliki keuntungan karena memiliki kasus berjalan terburuk dari O (n * log (n)) sehingga dalam kasus di mana quicksort cenderung berkinerja buruk (umumnya kumpulan data yang diurutkan secara umum) heapsort lebih disukai.

Nah jika Anda pergi ke tingkat arsitektur ... kami menggunakan struktur data antrian di memori cache. Jadi apa pun yang tersedia dalam antrian akan diurutkan. Seperti dalam penyortiran cepat, kami tidak memiliki masalah membagi array menjadi panjang apa pun ... tetapi di heap sort (dengan menggunakan array) mungkin saja terjadi bahwa induk mungkin tidak ada dalam sub array yang tersedia di cache dan kemudian harus membawanya ke dalam memori cache ... yang memakan waktu. Itu quicksort yang terbaik !! 😀

Heapsort membangun sebuah heap lalu berulang kali mengekstrak item maksimum. Kasus terburuknya adalah O (n log n).

Tetapi jika Anda melihat kasus terburuk dari pengurutan cepat , yaitu O (n2), Anda akan menyadari bahwa pengurutan cepat akan menjadi pilihan yang tidak terlalu baik untuk data besar.

Jadi ini membuat penyortiran menjadi hal yang menarik; Saya percaya alasan mengapa begitu banyak algoritme pengurutan aktif hari ini adalah karena semuanya 'terbaik' di tempat terbaiknya. Misalnya, pengurutan gelembung dapat melakukan pengurutan cepat jika datanya diurutkan. Atau jika kita mengetahui sesuatu tentang item yang akan disortir maka mungkin kita bisa lebih baik.

Ini mungkin tidak menjawab pertanyaan Anda secara langsung, saya pikir saya akan menambahkan dua sen saya.

Heap Sort adalah taruhan yang aman saat menangani input yang sangat besar. Analisis asimtotik menunjukkan urutan pertumbuhan Heapsort dalam kasus terburuk adalah Big-O(n logn), yang lebih baik daripada Quicksort Big-O(n^2)sebagai kasus terburuk. Namun, Heapsort agak lebih lambat dalam praktiknya di sebagian besar mesin daripada jenis cepat yang diterapkan dengan baik. Heapsort juga bukan algoritme pengurutan yang stabil.

Alasan heapsort lebih lambat dalam praktiknya daripada quicksort adalah karena lokalitas referensi yang lebih baik (" https://en.wikipedia.org/wiki/Locality_of_reference ") di quicksort, dengan elemen data berada dalam lokasi penyimpanan yang relatif dekat. Sistem yang menunjukkan lokalitas referensi yang kuat adalah kandidat yang tepat untuk pengoptimalan kinerja. Jenis tumpukan, bagaimanapun, berurusan dengan lompatan yang lebih besar. Ini membuat quicksort lebih disukai untuk input yang lebih kecil.

Bagi saya, ada perbedaan mendasar antara heapsort dan quicksort: yang terakhir menggunakan rekursi. Dalam algoritme rekursif, heap bertambah dengan jumlah rekursi. Ini tidak masalah jika n kecil, tapi sekarang saya sedang menyortir dua matriks dengan n = 10 ^ 9 !!. Program ini membutuhkan hampir 10 GB ram dan memori tambahan apa pun akan membuat komputer saya mulai bertukar ke memori disk virtual. Disk saya adalah disk RAM, tetapi tetap menukarnya membuat perbedaan besar dalam kecepatan . Jadi dalam statpack yang dikodekan dalam C ++ yang mencakup matriks dimensi yang dapat disesuaikan, dengan ukuran yang tidak diketahui sebelumnya oleh pemrogram, dan jenis statistik nonparametrik penyortiran saya lebih suka heapsort untuk menghindari penundaan penggunaan dengan matriks data yang sangat besar.

Untuk menjawab pertanyaan asli dan menjawab beberapa komentar lain di sini:

Saya baru saja membandingkan implementasi seleksi, quick, merge, dan heap sort untuk melihat bagaimana mereka akan bertumpuk satu sama lain. Jawabannya adalah mereka semua memiliki kelemahan.

TL; DR: Cepat adalah jenis tujuan umum terbaik (cukup cepat, stabil, dan sebagian besar ada di tempat) Secara pribadi saya lebih suka jenis tumpukan meskipun kecuali saya memerlukan jenis yang stabil.

Seleksi - N ^ 2 - Ini benar-benar hanya bagus untuk kurang dari 20 elemen atau lebih, maka kinerjanya lebih baik. Kecuali jika data Anda sudah diurutkan, atau sangat, sangat mungkin. N ^ 2 menjadi sangat lambat dengan sangat cepat.

Cepat, dalam pengalaman saya, tidak benar-benar yang cepat sepanjang waktu. Namun, bonus untuk menggunakan pengurutan cepat sebagai pengurutan umum adalah cukup cepat dan stabil. Ini juga merupakan algoritme di tempat, tetapi karena umumnya diterapkan secara rekursif, ini akan membutuhkan ruang tumpukan tambahan. Ia juga berada di antara O (n log n) dan O (n ^ 2). Pengaturan waktu pada beberapa jenis tampaknya mengkonfirmasi hal ini, terutama ketika nilainya berada dalam kisaran yang sempit. Ini jauh lebih cepat daripada pemilihan sortir pada 10.000.000 item, tetapi lebih lambat daripada penggabungan atau tumpukan.

Pengurutan gabungan dijamin O (n log n) karena pengurutannya tidak bergantung pada data. Itu hanya melakukan apa yang dilakukannya, terlepas dari nilai apa yang Anda berikan padanya. Ini juga stabil, tetapi jenis yang sangat besar dapat meledakkan tumpukan Anda jika Anda tidak berhati-hati tentang penerapannya. Ada beberapa penerapan pengurutan penggabungan di tempat yang kompleks, tetapi umumnya Anda memerlukan larik lain di setiap tingkat untuk menggabungkan nilai-nilai Anda. Jika array tersebut hidup di stack, Anda dapat mengalami masalah.

Jenis heap adalah max O (n log n), tetapi dalam banyak kasus lebih cepat, tergantung pada seberapa jauh Anda harus memindahkan nilai ke atas log n deep heap. Heap dapat dengan mudah diimplementasikan di tempat dalam larik asli, sehingga tidak memerlukan memori tambahan, dan ini berulang, jadi tidak perlu khawatir tentang stack overflow saat berulang. The besar downside ke semacam tumpukan adalah bahwa hal itu tidak stabil semacam, yang berarti keluar yang tepat jika Anda membutuhkan.