Algoritma Menyusun: Ketahui Mengapa Anda Tidak Boleh Menggunakan Bubblesort

Pendedahan: Sokongan anda membantu mengekalkan laman web ini! Kami memperoleh bayaran rujukan untuk beberapa perkhidmatan yang kami cadangkan di halaman ini.


Pernahkah anda terfikir bagaimana komputer mengatur sesuatu? Apabila anda mengklik butang A-Z di Excel, apa yang sebenarnya berlaku?

Komputer menyusun senarai dengan mengikuti prosedur yang disebut “algoritma penyortiran.” Algoritma adalah sekumpulan arahan yang dapat diikuti berulang kali, secara mekanis. Terdapat beberapa algoritma penyortiran yang berbeza – prosedur yang berbeza untuk memasukkan senarai mengikut urutan yang betul. Masing-masing mempunyai kekuatan dan kelemahannya.

Berikut adalah algoritma penyusun yang paling popular.

Susun Gelembung

Jenis gelembung adalah algoritma yang tidak cekap, tetapi sederhana. Ia jarang digunakan dalam praktik, tetapi mudah difahami.

Urutan gelembung berfungsi dengan membandingkan pasangan unsur berturut-turut dalam satu senarai. Elemen pertama dan kedua dibandingkan, kemudian unsur kedua dan ketiga, kemudian ketiga dan keempat, dan seterusnya melalui senarai. Selepas setiap perbandingan, kedua-dua elemen tersebut ditukar jika tidak sesuai. Selepas satu lelaran, elemen terbesar akan “digelegak” hingga akhir senarai. Prosedur ini diulang berulang kali sehingga senarai disusun.

Dalam varian dua arah, perbandingan dibuat secara bergantian ke hadapan melalui senarai dan kemudian ke belakang melalui senarai. Ini mengembangkan bahagian yang disusun di setiap hujung senarai. Ini juga disebut “semacam koktail shaker.”

Bilakah Menggunakan Bubble Sort

Tidak pernah, selain daripada demonstrasi.

Maklumat Lanjut Mengenai Bubble Sort

  • Penjelasan Bubble Sort dari Algorithmist, dengan contoh kod;
  • Algoritma Bubble Sort dikodkan dalam lebih dari 100 bahasa pengaturcaraan yang berbeza;
  • Bubble Sort digambarkan dengan Legos;
  • Bubble Sort digambarkan dengan tarian rakyat Hungary.

Susun Sisipan

Jenis penyisipan adalah bagaimana kebanyakan orang menyusun sesuatu secara intuitif secara manual – contohnya, ketika mengarang kertas dengan huruf. Ini melibatkan memindahkan setiap elemen, pada gilirannya, ke tempat yang tepat dalam bahagian yang sudah disusun.

Elemen pertama senarai dianggap “disusun.” Kemudian elemen kedua dipertimbangkan. Sekiranya lebih besar daripada elemen sebelumnya, ia berada di tempat yang betul dan menjadi sebahagian daripada bahagian “disusun”. Jika tidak, ia digerakkan ke belakang satu slot dan dibandingkan dengan elemen di belakangnya. Elemen itu terus bergerak ke belakang sehingga berada di kedudukan yang betul dalam bahagian senarai yang disusun. Prosedur ini kemudian diulang dengan elemen ketiga, keempat, kelima, dan seterusnya.

Bilakah Menggunakan Isi Sisipan

Penyisipan penyisipan umumnya merupakan penyelesaian terpantas untuk menyusun senarai kecil (10 atau lebih sedikit elemen), dan melakukan sekurang-kurangnya cukup dalam senarai bersaiz sederhana. Walau bagaimanapun, ia boleh menjadi lambat dalam set yang lebih besar.

Penyisipan penyisipan juga berkinerja baik, walaupun dalam kumpulan besar, jika senarai sudah banyak disusun. Ini menjadikannya sesuai untuk membersihkan data yang disusun berdasarkan manusia, atau untuk digunakan bersama dengan algoritma penyortiran yang lain. Sebagai contoh, adalah perkara biasa untuk memulakan dengan jenis cepat, dan kemudian beralih ke penyisipan selepas beberapa lelaran.

Maklumat Lanjut Mengenai Penyisipan Penyisipan

  • Penjelasan Sisipan dan latihan pengekodan, di Khan Academy;
  • Penyisipan Algoritma Pengekodan dalam hampir 100 bahasa pengaturcaraan yang berbeza;
  • Susunan Sisipan digambarkan dengan cawan styrofoam dan diceritakan oleh pelajar Harvard CS;
  • Susunan Sisipan digambarkan dengan tarian rakyat Hungary.

Isih timbunan

Jenis timbunan adalah jenis dua bahagian yang menggunakan struktur data timbunan binari sebagai pemegang perantaraan untuk elemen dalam senarai.

Timbunan binari adalah struktur pokok di mana setiap nod mempunyai hingga dua nod anak. Unsur terbesar berada di bahagian atas pokok. Setiap simpul anak lebih kecil daripada nod induknya. Ini bermaksud bahawa proses membina timbunan menyusun sebahagian senarai. Setelah timbunan dibina, elemen terbesar dikeluarkan dan dimasukkan ke dalam susunan yang disusun – kemudian timbunan terbesar dari timbunan yang tersisa, dan seterusnya.

Bilakah Menggunakan Isi Tumpukan

Rata-rata, timbunan memberikan prestasi yang baik. Selain itu, senario terburuknya jauh lebih baik daripada senario terburuk untuk hampir semua algoritma lain. Oleh itu, ia sering digunakan dengan kumpulan data yang besar dan diedarkan.

Maklumat Lanjut mengenai Heap Sort

  • Penjelasan terperinci mengenai Heap Sort dari profesor CS di Kent State;
  • Ceramah Video Heap dan Heap Sort dari MIT;
  • Untuk pemahaman mendalam mengenai timbunan dan jenis timbunan, lihat Siri Video Lima Bahagian ini.

Gabungan Susun

Menggabungkan dua senarai yang sudah disusun ke dalam senarai yang sudah disusun baru agak mudah: bandingkan elemen pertama masing-masing dan letakkan yang lebih kecil ke dalam senarai baru, ulangi. Ini adalah asas untuk penggabungan.

Untuk memulakan penggabungan, senarai dibahagikan kepada satu set “senarai” 1 elemen. Kemudian, pasangan senarai ini digabungkan menjadi senarai 2 elemen, yang kemudian digabungkan menjadi senarai 4 elemen, dan seterusnya sehingga keseluruhan senarai digabungkan kembali.

Bilakah Menggunakan Susun Gabungan

Penggabungan jenis sangat berkesan. Satu-satunya masalah ialah penggabungan jenis biasanya memerlukan memori aktif (RAM) yang cukup untuk menyimpan senarai dua kali. Oleh itu, ia tidak dapat dilaksanakan dalam keadaan tertentu.

Maklumat Lanjut mengenai Merge Sort

  • Merge Sort dari Khan Academy adalah pelajaran enam bahagian yang sangat baik dengan latihan pengaturcaraan termasuk;
  • Merge Sort dikodkan dalam lebih daripada 80 bahasa pengaturcaraan yang berbeza;
  • Merge Sort with German Folk Dance menyediakan rutin tarian yang menunjukkan algoritma penyortiran.

Susun Pantas

Jenis cepat tidak begitu intuitif. Walau bagaimanapun, ia sangat berkesan.

Langkah pertama dalam proses cepat adalah memilih elemen pangsi. Ini boleh menjadi unsur dalam senarai. Seterusnya, semua nilai lebih besar daripada pangsi diletakkan setelahnya, sementara semua nilai lebih kecil daripada yang diletakkan sebelumnya. Ini mewujudkan dua partisi yang tidak disusun, tetapi saling berkaitan antara satu sama lain. Prosedur yang sama ini dilakukan pada setiap partisi, kemudian pada setiap sub-partisi, dan seterusnya. Apabila partisi masing-masing mencapai ukuran satu elemen, senarai disusun.

Bilakah Menggunakan Urutan Pantas

Urutan pantas adalah salah satu algoritma penyortiran yang paling popular untuk penggunaan praktikal. Kelajuan purata sangat pantas. Walau bagaimanapun, senario terburuk (yang jarang berlaku dalam set data semula jadi) menjadi bermasalah dengan set yang sangat besar.

Maklumat Lanjut mengenai Urutan Pantas

  • Quick Sort dikodkan dalam lebih dari 100 bahasa pengaturcaraan;
  • Urutan Pantas Dijelaskan dengan Blok dari kelas CS-50 Harvard;
  • Quick Sort Tutorial dari Tutorials Point mempunyai banyak perincian, contoh kod, dan gambar animasi.

Sumber Algoritma Pengisytiharan Umum

  • Struktur Data – Teknik Pengisihan adalah siri yang sangat terperinci dari Tutorials Point;
  • Menyusun Algoritma mempunyai visualisasi setiap jenis, dalam keadaan yang berbeza – anda bahkan dapat melihat algoritma yang berlainan saling berlainan;
  • 15 Menyusun Algoritma dalam 6 Minit adalah visualisasi video yang menarik;
  • Mendapatkan Urutan adalah video yang meneroka masalah penyusunan berkomputer;
  • Apa Algoritma Penyortiran Berbeza Seperti Sound adalah video “audibilisasi” yang luar biasa yang menerjemahkan beberapa algoritma penyortiran menjadi bunyi.

Ringkasan

Selalunya, semasa memprogram, jika anda memerlukan sesuatu yang sepele – susunan nilai pendek, lajur data – anda hanya akan menggunakan kaedah atau fungsi apa pun yang terdapat dalam bahasa pengaturcaraan atau perpustakaan kegemaran anda.

Tetapi semasa mengusahakan aplikasi data besar, penting untuk memikirkan bagaimana algoritma pilihan anda akan mempengaruhi prestasi sistem anda. Di luar itu, algoritma penyortiran adalah aspek asas dalam sains komputer, dan harus difahami dengan baik oleh sesiapa sahaja yang bekerja dalam pembangunan atau pengaturcaraan.

Bacaan dan Sumber Lanjut

Kami mempunyai lebih banyak panduan, tutorial, dan infografik yang berkaitan dengan pengekodan dan pengembangan:

  • Sumber Pembangun C ++: salah satu bahasa pengaturcaraan yang paling popular, sesuai untuk kebanyakan jenis aplikasi.
  • Pengenalan dan Sumber Unicode: belajar semua tentang pengekodan watak.
  • Pengenalan dan Sumber MantisBT: MantisBT adalah salah satu program pengesanan pepijat yang paling popular.

Kod Apa yang Perlu Anda Pelajari?

Keliru dengan bahasa pengaturcaraan yang harus anda pelajari untuk membuat kod? Lihat infografik kami, Kod Apa yang Perlu Anda Pelajari? Ia tidak hanya membincangkan aspek bahasa yang berlainan, tetapi juga menjawab pertanyaan penting seperti, “Berapa banyak wang yang akan saya buat untuk memprogram Java?”

Kod Apa yang Perlu Anda Pelajari?
Kod Apa yang Perlu Anda Pelajari?

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map