Unduh AlgoLab dari drive Google ( AlgoLab (Excel 2007-2013) .xlsm dan AlgoLab (Excel 97-2003) .xls file ).

Apa yang sudah lama dibicarakan kaum Bolshevik dan apa yang saya kejar selama beberapa tahun dengan kecepatan yang berbeda akhirnya terjadi. Beberapa tahun yang lalu, ia menulis sebuah makro kecil untuk membuat animasi algoritmik gif untuk habrastaty. Seiring waktu, instrumen saya yang sederhana telah berkembang ke ukuran yang mengesankan, yang sekarang tidak memalukan untuk diungkapkan kepada dunia.

Jadi ketemu.

AlgoLab adalah aplikasi Excel (yaitu, file Excel dengan makro) di mana Anda dapat selangkah demi selangkah membiasakan diri dengan algoritma pengurutan. Dan juga ada kesempatan untuk menyiapkan animasi gif.

Contoh animasi yang dihasilkan

Pemilahan pohon biner

Penyortiran spageti

Semacam tidur

Hanya 4 lembar - 2 utama dan 2 begitu, informasi. Inilah mereka:

Sortir lembar		Lembar proses



Sortir Lembar		Grafik Lembar

_{Mengklik pada gambar akan membuka gambar ukuran penuh}

Sortir lembar. Pada lembar ini, Anda dapat dengan cepat membentuk array dan memilih algoritma pengurutan.
Proses lembar. Di sini kita mengamati langkah demi langkah bagaimana algoritma ini atau itu bekerja.
Sortir Lembar. Berikut ini ringkasan algoritmanya.
Grafik Lembar. Ada juga jadwal rilis yang direncanakan untuk artikel tentang penyortiran.

Mari berkenalan dengan lembaran ini secara lebih rinci.

Sortir lembar

Bagian atas sheet dikhususkan untuk pembuatan array yang tidak disortir (sehingga ada sesuatu yang bisa memberi makan algoritma), serta menyimpan visualisasi dalam bentuk gambar di komputer Anda:

Pada baris pertama adalah array itu sendiri. Jika perlu, Anda dapat secara manual mengubah nilai elemen individual di dalamnya:

Di kiri atas, Anda perlu menentukan karakteristik utama untuk array yang dihasilkan:

Ukurannya, apakah nilai dalam array harus non-berulang (0 - tidak, 1 - ya), yang sama dengan elemen minimum dan maksimum dalam array. Macro VBA termasuk resistensi perusak untuk memasukkan data, sehingga Anda dapat memasukkan beberapa nilai yang salah. Dalam hal ini, aplikasi akan menentukan karakteristik apa ini atau itu harus sama.

Dan juga opsi untuk menentukan apakah perlu untuk menjalankan algoritme langkah demi langkah (= 1) atau apakah dimungkinkan untuk menerapkan penyortiran ke struktur dan hanya menampilkan hasil akhir (= 0). Tentu saja, aplikasi excel itu sendiri dibuat untuk mengamati seluruh proses dalam mode langkah-demi-langkah, sehingga nilai di sini biasanya sama dengan satu. Tetapi kadang-kadang saat pengujian, saya membatalkan opsi ini hanya untuk memeriksa apakah algoritma baru yang saya tambahkan ke AlgoLab.xlsm bekerja sama sekali (yaitu, saya pertama-tama perlu melihat apakah array yang diurutkan adalah hasil akhir, tanpa membuang waktu untuk melihat visualisasi. )

Sedikit ke kanan adalah area di mana Anda dapat menentukan bagaimana tepatnya elemen-elemen dalam array yang tidak disortir yang dihasilkan tidak diurutkan.

Hasilkan array campuran acak? Atau mungkin mengatur elemen dalam urutan menurun? Atau membuat array hampir diurutkan (dan juga tentukan koefisien hampir menyortir)?

Untuk memilih salah satu dari metode ini, Anda hanya perlu mengklik sel dengan item tersebut. Akibatnya, array dibuat ulang di baris pertama. Sel yang dipilih akan berubah menjadi biru.

Di sebelah kiri adalah wilayah yang akan dibutuhkan jika Anda tidak hanya perlu mengagumi visualisasi, tetapi juga untuk menyimpan seluruh proses bingkai demi bingkai sebagai gambar.

Pertama, Anda perlu menentukan apakah akan mengekspor langkah-langkah penyortiran secara umum ke gambar (= 0, jika tidak, = 1 jika ya, dan opsi ini adalah "satu kali", yaitu, ulang ke nol setelah penyortiran selesai). Kedua, Anda perlu menentukan format gambar (hanya 4 opsi yang mungkin: GIF, JPG, PNG, dan BMP. Opsi terakhir memberikan hasil kualitas tertinggi, jadi saya merekomendasikannya). Ketiga, Anda perlu menentukan jalur ke folder tempat menyimpan gambar (klik pada sel ini dan kotak dialog akan terbuka untuk memilih direktori). Kemudian muncul sel yang diisi oleh makro itu sendiri - pengidentifikasi sesi (diperlukan untuk nama unik subfolder untuk menyimpan bingkai aplikasi pengurutan khusus ini). Dan juga perlu untuk menentukan area penangkapan dengan benar (koordinat sel kiri atas dan kanan bawah, itu akan menjadi frame yang akan terbatas pada mereka - jangan menyalin seluruh lembar?)

Nah, di bagian paling kanan Anda akan menemukan sel "Sort" (yang bertindak sebagai tombol untuk memulai proses, ketika memilih menyortir dan menghasilkan array, cukup klik di atasnya).

Bahkan di sebelah tombol ini tinggal berbagai karakter khusus yang dapat digunakan dalam visualisasi. Sel-sel ini tidak perlu disentuh.

Di bagian bawah, yang paling penting adalah pilihan algoritma. Anda hanya perlu mengeklik nama pengurutan, setelah itu sel dengan itu akan berubah menjadi biru.

Dari lebih dari 80 algoritma, sekitar setengahnya tersedia saat ini. Sejauh ini, yang belum direalisasi memiliki tampilan pucat dibandingkan dengan yang sudah diterapkan. Saya masih belum berhasil melakukan beberapa (dan bahkan belum memulai implementasi). Beberapa sedang dalam pengembangan. Beberapa dari mereka ditulis dan diuji dan akan segera tersedia (khususnya, hampir semua penyortiran dengan sisipan siap untuk saya, namun, saya akan menambahkannya ke aplikasi segera setelah habrastat dirilis untuk penyortiran ini dalam beberapa minggu mendatang dan membagikan AlgoLab.xlsm yang diperbarui - dan apa yang harus dilakukan, saya tidak ingin merusak episode baru dari seri saya).

Saya berencana untuk memodifikasi beberapa penyortiran yang sudah diterapkan. Visualisasi tidak memuaskan saya di mana-mana.

Tetapi di area ini, ketika memilih suatu algoritma, ringkasan informasi tentang itu dimuat. Informasi diambil dari lembar "Sortir", itu secara otomatis ditarik dengan makro. Omong-omong, jika Anda mengubah teks di area ini, maka pada lembar asli juga akan berubah.

Sortir, seperti yang bisa Anda lihat banyak. Agar tidak menjadi bingung dalam semua kemegahan ini, mereka dibagi menjadi beberapa kelas, tergantung pada metode dasar pengorganisasian data yang digunakan. Apa kelas-kelas ini?

Penyortiran acak. Elemen-elemen dari array dicampur secara acak dan ini berlanjut sampai struktur tiba-tiba dipesan.
Mengurutkan pertukaran. Suatu perbandingan berpasangan (dan pertukaran) unsur-unsur array yang diatur secara total.
Sisipkan sisipan. Elemen dipilih dan masing-masing dimasukkan di tempatnya.
Urutkan berdasarkan pilihan. Dalam subarray, elemen maksimum dipilih, yang dimasukkan di akhir subarray. Kemudian, ke bagian yang tidak disortir yang tersisa, prosedur yang sama diulang.
Gabungkan Urusan. Subarrays yang dipesan yang dicari yang terhubung satu sama lain.
Urutkan berdasarkan distribusi. Elemen dibagi menjadi beberapa kelas sampai ini mengarah pada hasil yang diinginkan.
Sortasi Hibrid. Metode pertukaran, masukkan, pilih, gabungkan dan algoritma distribusi digabungkan.
Pemilahan paralel. Algoritma tempat pemrosesan paralel berbagai bagian array disediakan.
Menyortir jaringan. Array dilewatkan melalui jaringan pengurutan; pada output, itu dipesan.
Pemilahan lainnya. Algoritma semu, komik, dan penyortiran sederhana.

Di harastings mendatang, nuansa detail untuk setiap kelas akan disorot. Baiklah, kita beralih ke lembar berikutnya.

Lembar proses

Sebenarnya, ketika membuat array, memilih algoritma dan mengklik tombol "Sort", makro melempar ke sheet ini. Di sinilah misteri pengorganisasian data berlangsung.

Selama seluruh proses di atas, Anda akan ditemani oleh jendela indah ini:

Karena mode tampilan adalah langkah-demi-langkah, untuk melanjutkan ke langkah berikutnya, perlu untuk menekan tombol "Langkah Baru" di dalamnya. Sangat tidak nyaman untuk melakukan ini dengan mouse, jadi fokus input jendela selalu pada tombol ini. Artinya, untuk melanjutkan ke langkah berikutnya, Anda tidak perlu malas untuk menekan Enter keyboard (tidak ada gerakan lain yang diperlukan).

Tombol "Selesai" menampilkan proses dari tampilan langkah-demi-langkah. Algoritme akan secara diam-diam menyelesaikan pekerjaannya dan hanya menampilkan hasil akhir. Anda tidak akan melihat tahap akhir dari operasi penyortiran.

Tombol "Batalkan" sepenuhnya menghentikan pekerjaan makro pada langkah ini.

Tombol "Snapshot" memungkinkan Anda untuk menyimpan tangkapan layar dari langkah khusus ini. Anda kemudian akan menemukan gambar di folder yang ditentukan dalam pengaturan pada lembar sortir.

Sortir Lembar

Sebuah meja besar dengan segala macam pengetahuan tentang jenis disimpan di sini. Seperti yang Anda ingat, informasi ditarik dari sini ketika memilih pengurutan pada lembar pengurutan. Saya bertobat, sementara kualitas isian begitu-begitu, tidak ada cukup ketekunan untuk dengan susah payah memperkenalkan jumlah maksimum data yang benar. Harapan untuk mengejar ketinggalan dalam waktu dekat.

Grafik Lembar

Pada lembar ini Anda bisa berkenalan dengan fantasi saya tentang tanggal rilis habrastatik terdekat tentang macam-macam.

Saya akan berbicara tentang algoritma dalam urutan ini.

Pertukaran → Sisipan → Pilihan → Gabung → Distribusi →
→ Hibrida → Paralel → Jaringan → Acak

Kelas-kelas umum terdaftar, tetapi secara umum, beberapa karya yang mematuhi skema umum semacam itu akan dikhususkan untuk masing-masing kelas.

Deskripsi kelas sortir. Pendahuluan, nuansa dasar yang melekat dalam semua jenis kelas, jenis kelas dasar. Biasanya, artikel pengantar ini akan berisi informasi yang cukup terkenal. Tapi tetap saja, saya akan berusaha untuk tidak bosan.
Beberapa kelas kurang dikenal. Di sini saya akan senang Anda dengan materi baru, yang praktis tidak ada informasi dalam bahasa Rusia. Dan Anda tidak akan menemukan sesuatu bahkan dalam bahasa Inggris. Artikel yang terpisah tidak akan hanya tentang penyortiran pertukaran, karena sudah lama tidak ada waktu untuk eksklusif yang menarik.
Perbandingan praktis berbagai kelas di antara mereka sendiri. Untuk setiap kelompok algoritma akan ada artikel akhir yang ditujukan untuk menguji pengurutan pada set data yang berbeda. Di sini saya menjanjikan banyak penemuan luar biasa!

Perbandingan Sortir Praktis

Direncanakan untuk membandingkan hanya implementasi python-algoritma. Namun, setelah melihat hasil pertama pada contoh penyortiran gnome, saya sampai pada kesimpulan bahwa mereka akan memberikan kesalahpahaman tentang kecepatan relatif.

Python memiliki sistem sendiri untuk mengakses memori variabel (terutama jika variabel-variabel ini ditugaskan satu sama lain), itulah sebabnya algoritma yang dioptimalkan dapat berjalan lebih lambat.

Sortir Kurcaci	Sortir Kurcaci yang Dioptimalkan

`def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data`	`def gnome_opt(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data`
10 array 1000 elemen masing-masing
Total waktu: 3,39134 dtk.	Total waktu: 5,6809 dtk.

Situasi serupa dengan Shaker / Bubble. Bertolak belakang dengan ekspektasi, pengurutan gelembung bekerja lebih cepat daripada pengurutan pengocok (meskipun Pengocok Pengocok adalah peningkatan pengurutan gelembung)

Untuk kontrol, saya juga menguji penyortiran dalam PHP (saya terutama bekerja dalam bahasa ini, jadi tes alternatif lebih cepat dan lebih mudah dibuat di atasnya). Di sana situasinya sudah "normal" - "gnome" yang dioptimalkan pada semua set data bekerja dengan jelas lebih cepat dari biasanya.

Namun, PHP juga memiliki reputasi sebagai "tidak sempurna" dan alat yang lambat, jadi saya memutuskan bahwa itu juga tidak cocok untuk kesimpulan global. Untuk meminimalkan kemungkinan celaan [dalam memilih bahasa yang salah untuk menguji kecepatan sebenarnya], saya memutuskan untuk meminimalkan tes utama juga di Jawa. Namun, saya kekurangan pengetahuan untuk bahasa ini. Sayangnya, itu tidak tumbuh bersama.

Dengan demikian, pengujian akan segera dalam ~~tiga~~ dua bahasa:

Python Pertama-tama, bahasa ini paling cocok untuk menggambarkan algoritma. Karena ada fungsi yang berfungsi dengan benar, maka kami akan mengukur waktu untuk mereka. Tetapi hasilnya akan agak meragukan.
PHP Awalnya, saya tidak akan menggunakan bahasa ini dengan cara apa pun dalam serangkaian artikel. Tetapi karena saya menulis sebuah lingkungan di atasnya untuk menguji penyortiran dan implementasi sendiri pada PL ini tersedia, lalu mengapa tidak. Hasil praktis yang dengannya seseorang dapat menilai efektivitas relatif dari algoritma lebih memadai dibandingkan dengan Python.
~~Jawa~~ ~~Ini didasarkan pada hasil di Jawa bahwa kita akan menarik kesimpulan utama.~~

Tentu saja, semua opsi dalam semua bahasa akan dibagikan.

Faq

Saya sudah melihat beberapa pertanyaan dari audiens, saya akan segera menjawab.

Mengapa program untuk memvisualisasikan algoritma diimplementasikan di Excel?

Jadi pada satu waktu itu lebih cepat dan lebih mudah (bagi saya). Ruang kisi spreadsheet ternyata menjadi solusi turnkey yang sangat, sangat nyaman untuk memvisualisasikan kerja dengan array.

Ok, mari kita lihat semua ini. Apa selanjutnya

Berdasarkan AlgoLab saya akan melakukan visualisasi untuk pohon, grafik. Taplak meja Ulam, semut Langton, itu saja. Masih ada yang kosong untuk 2048 (AI bermain menggunakan metode minimax dan Monte Carlo - Anda harus menyelesaikannya). Pekerjaan banyak tanah.

Referensi

Unduh AlgoLab dari drive Google ( AlgoLab (Excel 2007-2013) .xlsm dan AlgoLab (Excel 97-2003) .xls file ).

Macam-macam sepanjang masa