Perbandingan
Penukaran
Putaran

  • Disisipkan
  • Dibandingkan
  • Ditukar
  • Bagian terurut

Info lebih lanjut tentang insertion sort

Insertion sort

Insertion sort bekerja seperti cara banyak orang mengurutkan kartu remi di tangan. Algoritma ini menjaga bagian terurut di depan daftar, mengambil nilai berikutnya, lalu menggesernya mundur melewati setiap nilai yang lebih besar sampai pas. Putar pengurutan dengan kecepatan apa pun, atau jalankan satu perbandingan setiap kali, dan amati penghitung perbandingan, penukaran, dan putaran. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Kotak-kotak menghitung perbandingan, penukaran, dan putaran. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Pilih jumlah batang dan urutan awalnya: acak, hampir terurut, terbalik, atau dengan sedikit nilai unik. Atau ketik angka sendiri.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja.
  3. Coba daftar yang hampir terurut dan daftar terbalik, lalu bandingkan berapa banyak perbandingan yang dibutuhkan masing-masing.

Cara kerja insertion sort

Nilai pertama saja sudah merupakan bagian terurut. Ambil nilai kedua dan bandingkan dengan nilai di depannya; jika nilai itu lebih besar, tukar keduanya, lalu terus bandingkan dan tukar sampai nilai di depannya tidak lebih besar atau nilai itu mencapai posisi paling depan. Sekarang dua nilai pertama sudah berurutan. Lakukan hal yang sama dengan nilai ketiga, keempat, dan seterusnya sampai akhir daftar.

Cepat pada daftar yang hampir terurut

Setiap putaran berhenti pada nilai pertama yang tidak lebih besar, jadi nilai yang sudah dekat dengan tempatnya hanya butuh satu atau dua perbandingan. Daftar terurut butuh n − 1 perbandingan tanpa penukaran; daftar terbalik, kasus terburuk, butuh n(n − 1)/2 untuk masing-masing. Jumlah penukaran selalu sama dengan jumlah inversi pada daftar awal, yaitu pasangan yang salah urutan. Karena itulah insertion sort sering dipakai untuk daftar pendek atau hampir terurut, dan di dalam algoritma yang lebih cepat untuk menyelesaikan bagian-bagian kecil.

Pertanyaan yang sering diajukan

Bagaimana cara kerja insertion sort?

Algoritma ini membangun bagian terurut di depan daftar. Setiap putaran mengambil nilai berikutnya dan memindahkannya mundur melewati setiap nilai lebih besar di depannya sampai pas. Setelah putaran k, k + 1 nilai pertama sudah berurutan, meski nilai yang datang kemudian masih bisa disisipkan di antaranya.

Berapa banyak perbandingan dan penukaran yang dilakukan insertion sort?

Jumlah penukaran selalu sama dengan jumlah inversi pada daftar awal: nol untuk daftar terurut, n(n − 1)/2 untuk daftar terbalik. Jumlah perbandingan adalah jumlah penukaran ditambah paling banyak satu per putaran, jadi antara n − 1 dan n(n − 1)/2.

Mengapa insertion sort cepat pada daftar yang hampir terurut?

Karena satu putaran langsung berhenti begitu bertemu nilai yang tidak lebih besar. Jika setiap nilai sudah dekat dengan tempat akhirnya, setiap putaran pendek, dan seluruh pengurutan butuh waktu mendekati n.

Apakah insertion sort stabil?

Ya. Sebuah nilai hanya melewati nilai yang benar-benar lebih besar, jadi nilai yang sama tidak pernah saling melewati dan tetap dalam urutan aslinya.

Apakah angka saya dikirim ke suatu tempat?

Tidak. Pengurutan berjalan di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor