cpp sort

Akan lebih baik jika hanya satu atau dua metode penyortiran yang mendominasi metode lainnya, terlepas dari aplikasi atau komputer yang digunakan. Namun pada kenyataannya, setiap metode memiliki kelebihannya masing-masing. [...] Jadi kami menemukan bahwa hampir semua algoritme layak untuk diingat, karena ada beberapa aplikasi yang ternyata merupakan yang terbaik. — Donald Knuth, Seni Pemrograman Komputer, Volume 3

cpp-sort adalah pustaka pengurutan khusus header C++14 generik. Ini berkisar pada satu antarmuka penyortiran umum utama dan menyediakan beberapa alat kecil untuk memilih dan/atau merancang algoritma penyortiran. Menggunakan fitur penyortiran dasarnya seharusnya cukup sepele:

# include < array >
# include < iostream >
# include < cpp-sort/sorters/smooth_sorter.h >

int main ()
{
    std::array< int , 5 > arr = { 5 , 8 , 3 , 2 , 9 };
    cppsort::smooth_sort (arr);

    // prints 2 3 5 8 9
    for ( int val: arr) {
        std::cout << val << ' ' ;
    }
}

Fitur utama & fitur tambahan

cpp-sort menyediakan serangkaian fitur lengkap terkait penyortiran. Berikut adalah blok bangunan utama perpustakaan:

• Setiap algoritma pengurutan ada sebagai objek fungsi yang disebut penyortir
• Penyortir dapat dibungkus dengan adaptor penyortir untuk meningkatkan perilakunya
• Perpustakaan menyediakan fasad penyortir untuk membuat penyortir dengan mudah
• Penyortir ukuran tetap dapat digunakan untuk mengurutkan koleksi kecil berukuran tetap secara efisien
• Ukuran presortedness dapat digunakan untuk mengevaluasi ketidakteraturan dalam suatu koleksi

Berikut adalah contoh lebih lengkap tentang apa yang dapat dilakukan dengan perpustakaan:

# include < algorithm >
# include < cassert >
# include < forward_list >
# include < functional >
# include < vector >
# include < cpp-sort/adapters.h >
# include < cpp-sort/sorters.h >

int main ()
{
    struct wrapper { int value; };

    std::forward_list<wrapper> li = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
    std::vector<wrapper> vec = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };

    // When used, this sorter will use a pattern-defeating quicksort
    // to sort random-access collections, and a mergesort otherwise
    cppsort::hybrid_adapter<
        cppsort::pdq_sorter,
        cppsort::merge_sorter
    > sorter;

    // Sort li and vec in reverse order using their value member
    sorter (li, std::greater<>{}, &wrapper::value);
    sorter (vec, std::greater<>{}, &wrapper::value);

    assert ( std::equal (
        li. begin (), li. end (),
        vec. begin (), vec. end (),
        []( const auto & lhs, const auto & rhs) { return lhs. value == rhs. value ; }
    ));
}

Meskipun fungsi penyortiran digunakan tanpa fitur tambahan, fungsi tersebut tetap memberikan beberapa jaminan menarik (ide sering kali diambil dari Ranges TS):

• Mereka menyediakan iterator dan antarmuka jangkauan
• Jika memungkinkan, mereka menerima parameter pembanding khusus
• Kebanyakan dari mereka menerima parameter proyeksi
• Mereka menangani iterator proxy dengan iter_swap dan iter_move dengan benar
• Mereka juga berfungsi ketika iterator tidak menyediakan pasca-kenaikan atau pasca-pengurangan
• Tipe nilai dari koleksi yang akan diurutkan tidak harus dapat dibuat secara default
• Tipe nilai dari koleksi yang akan diurutkan tidak perlu dapat disalin (hanya dapat dipindahkan)
• Penyortir tanpa kewarganegaraan dapat dikonversi menjadi penunjuk fungsi untuk setiap operator() yang kelebihan beban
• Penyortir adalah objek fungsi: mereka dapat langsung diteruskan sebagai "kumpulan kelebihan beban" ke fungsi lain

Anda dapat membaca lebih lanjut tentang semua alat yang tersedia dan menemukan beberapa tutorial tentang menggunakan dan memperluas cpp-sort di wiki.

Tolok ukur

Grafik berikut telah dibuat dengan skrip yang ditemukan di direktori benchmark. Ini menunjukkan waktu yang dibutuhkan heap_sort untuk mengurutkan satu juta elemen tanpa diadaptasi, kemudian diadaptasi dengan drop_merge_adapter atau split_adapter .

Seperti dapat dilihat di atas, membungkus heap_sort dengan salah satu adaptor membuatnya adaptif terhadap jumlah inversi dengan cara yang tidak mengganggu. Algoritme yang digunakan untuk mengadaptasinya memiliki kelebihan dan kekurangan yang berbeda, terserah Anda untuk menggunakannya.

Tolok ukur ini sebagian besar bertujuan untuk menunjukkan kemungkinan-kemungkinan yang ditawarkan oleh perpustakaan. Anda dapat menemukan lebih banyak tolok ukur yang dikomentari di halaman wiki khusus.

Dukungan & perkakas kompiler

cpp-sort memerlukan dukungan C++14, dan harus bekerja dengan kompiler berikut:

• g++7 atau lebih baru.
• clang++6.0 atau yang lebih baru (dengan libstdc++ dan libc++).
• Versi MinGW-w64 dan AppleClang setara dengan kompiler yang disebutkan di atas.
• Visual Studio 2019 versi 16.8.3 atau lebih baru, hanya dengan /permissive- . Beberapa fitur tidak tersedia.
• clang-cl sesuai dengan versi Visual Studio di atas.

Kompiler yang tercantum di atas adalah yang digunakan oleh pipeline CI, dan pustaka juga diuji dengan versi terbaru dari kompiler tersebut secara rutin. Semua versi kompiler lain di antaranya belum diuji, tetapi seharusnya juga berfungsi. Jangan ragu untuk membuka terbitan jika bukan itu masalahnya.

Fitur di perpustakaan mungkin berbeda tergantung pada versi C++ yang digunakan dan ekstensi kompiler yang diaktifkan. Perubahan tersebut didokumentasikan di wiki.

Repositori utama berisi dukungan tambahan untuk perkakas standar seperti CMake atau Conan. Anda dapat membaca lebih lanjut tentang hal tersebut di wiki.

Terima kasih

Saya mendapat mobil baru. Saya hanya perlu menyatukannya. Mereka lebih mudah untuk dicuri sepotong demi sepotong. — Jarod Kintz, $3,33

Meskipun beberapa bagian dari perpustakaan adalah penelitian asli dan beberapa lainnya sesuai dengan implementasi algoritme pengurutan standar yang kustom dan agak naif, cpp-sort juga menggunakan kembali banyak kode dan ide dari proyek sumber terbuka, sering kali diubah untuk diintegrasikan dengan mulus ke dalam perpustakaan. Berikut adalah daftar sumber daya eksternal yang digunakan untuk membuat perpustakaan ini. Saya harap banyak lisensi berbeda yang kompatibel. Jika tidak demikian, silakan hubungi saya (atau kirimkan masalah) dan kita akan melihat apa yang dapat dilakukan untuk mengatasinya:

• Beberapa algoritma yang digunakan oleh insertion_sorter dan pdq_sorter berasal dari quicksort yang mengalahkan pola Orson Peters. Beberapa bagian tolok ukur juga berasal dari sana.

• Algoritme yang digunakan oleh tim_sorter berasal dari implementasi Timsort oleh Goro Fuji (gfx).

• Ketiga algoritma yang digunakan spread_sorter berasal dari modul Steven Ross Boost.Sort.

• Algoritma yang digunakan oleh d_ary_spread_sorter berasal dari modul Boost.Heap milik Tim Blechmann.

• Algoritma yang digunakan oleh spin_sorter berasal dari algoritma eponymous yang diimplementasikan di Boost.Sort. oleh Francisco Jose Tapia.

• utility::as_function , utility::static_const , dan beberapa algoritme pembantu yang ditingkatkan proyeksinya berasal dari perpustakaan Range v3 Eric Niebler. Beberapa ide seperti iterator proxy, titik penyesuaian dan proyeksi, serta beberapa fungsi utilitas lainnya juga berasal dari perpustakaan tersebut atau dari artikel terkait dan proposal standar C++.

• Algoritma yang digunakan oleh ska_sorter berasal dari implementasi algoritma ska_sort miliknya sendiri oleh Malte Skarupke.

• Algoritma yang digunakan oleh drop_merge_sorter berasal dari implementasi ulang Adrian Wielgosik C++ dari pengurutan drop-merge Emil Ernerfeldt.

• Banyak algoritma standar yang disempurnakan diadaptasi secara langsung dari rekan-rekan mereka di libc++, ditingkatkan untuk menangani proyeksi dan iterator proksi.

• Perpustakaan secara internal menggunakan fungsi inplace_merge yang bekerja dengan iterator maju. Implementasinya menggunakan algoritma penggabungan yang diusulkan oleh Dudziński dan Dydek, dan diimplementasikan oleh Alexander Stepanov dan Paul McJones dalam buku mereka Elements of Programming .

• Kelebihan inplace_merge untuk iterator akses acak menggunakan algoritme Symmerge yang diusulkan oleh Pok-Son Kim dan Arne Kutzner dalam Penggabungan Penyimpanan Minimum Stabil dengan Perbandingan Simetris ketika tidak ada cukup memori yang tersedia untuk melakukan penggabungan di luar tempatnya.

• Implementasi smoothsort Dijkstra yang digunakan smooth_sorter diadaptasi langsung dari implementasi algoritma Keith Schwarz.

• Algoritma yang digunakan oleh wiki_sorter telah diadaptasi dari WikiSort milik BonzaiThePenguin.

• Algoritma yang digunakan grail_sorter telah diadaptasi dari GrailSort milik Mrrl.

• Algoritme yang digunakan oleh indirect_adapter dengan iterator maju atau dua arah adalah versi indiesort Matthew Bentley yang sedikit dimodifikasi.

• Implementasi kelebihan akses acak nth_element yang digunakan oleh beberapa algoritma berasal dari perpustakaan miniselect Danila Kutenin dan menggunakan algoritma AdaptiveQuickselect milik Andrei Alexandrescu.

• Jaringan penyortiran yang digunakan oleh sorting_network_sorter semuanya berasal dari daftar yang dikelola oleh Bert Dobbelaere. Halaman ini memiliki referensi ke sumber dari semua jaringan penyortiran yang dicantumkannya.

• Beberapa optimasi yang digunakan oleh sorting_network_sorter berasal dari diskusi di StackOverflow dan didukung oleh artikel Menerapkan Jaringan Penyortiran untuk Mensintesis Perpustakaan Penyortiran yang Dioptimalkan .

• Rangkaian pengujian menerapkan kembali algoritma bilangan acak yang awalnya ditemukan di tempat berikut:

  • xoshiro256**
  • Pembuatan Seragam Diskrit Optimal dari Pembalikan Koin, dan Aplikasi
  • Semua nomor dalam rentang tertentu tetapi urutannya acak

• Skrip LaTeX yang digunakan untuk menggambar jaringan penyortiran adalah versi modifikasi dari sortingnetwork.tex milik kaayy, sedikit diadaptasi menjadi berbasis 0 dan menggambar jaringan dari atas ke bawah.

• Alat CMake yang tertanam dalam proyek termasuk skrip dari RWTH-HPC/CMake-codecov dan Crascit/DownloadProject.

• Beberapa tolok ukur menggunakan palet ramah buta warna yang dikembangkan oleh Thøger Rivera-Thorsen.