Ada beberapa algoritma dasar untuk memecahkan masalah pengurutan array. Salah satu yang paling terkenal di antaranya adalah insertion sort. Karena kejelasan dan kesederhanaannya, tetapi efisiensinya rendah, metode ini digunakan terutama dalam pengajaran pemrograman. Ini memungkinkan Anda untuk memahami mekanisme pengurutan dasar.
Deskripsi algoritma
Inti dari algoritma pengurutan penyisipan adalah bahwa segmen yang diurutkan dengan benar dibentuk di dalam larik awal. Setiap elemen dibandingkan satu per satu dengan bagian yang diperiksa dan dimasukkan ke tempat yang tepat. Jadi, setelah mengulangi semua elemen, mereka berbaris dalam urutan yang benar.
Urutan pemilihan elemen dapat berupa apa saja, mereka dapat dipilih secara sewenang-wenang atau menurut beberapa algoritma. Paling sering, enumerasi sekuensial digunakan dari awal array, di mana segmen yang dipesan terbentuk.
Awal penyortiran mungkin terlihat seperti ini:
- Ambil elemen pertama dari array.
- Karena tidak ada yang bisa dibandingkan, ambil elemen itu sendiri seperti yang diperintahkanurutan.
- Pergi ke item kedua.
- Bandingkan dengan yang pertama berdasarkan aturan pengurutan.
- Jika perlu, tukar elemen di beberapa tempat.
- Ambil dua elemen pertama sebagai barisan terurut.
- Pergi ke item ketiga.
- Bandingkan dengan yang kedua, tukar jika perlu.
- Jika dilakukan penggantian, bandingkan dengan yang pertama.
- Ambil tiga elemen sebagai urutan berurutan.
Dan seterusnya sampai akhir array asli.
Urutan penyisipan kehidupan nyata
Untuk kejelasan, ada baiknya memberikan contoh bagaimana mekanisme pengurutan ini digunakan dalam kehidupan sehari-hari.
Ambil, misalnya, dompet. Uang seratus, lima ratus, dan seribu dolar tergeletak tidak beraturan di kompartemen uang kertas. Ini berantakan, dalam gado-gado seperti itu sulit untuk segera menemukan selembar kertas yang tepat. Susunan uang kertas harus diurutkan.
Yang pertama adalah uang kertas 1000 rubel, dan segera setelahnya - 100. Kami mengambil seratus dan meletakkannya di depan. Yang ketiga berturut-turut adalah 500 rubel, tempat yang tepat untuk itu adalah antara seratus dan seribu.
Dengan cara yang sama kita mengurutkan kartu yang diterima saat memainkan "Fool" untuk memudahkan navigasinya.
Operator dan fungsi pembantu
Metode pengurutan penyisipan mengambil sebagai input array awal yang akan diurutkan, fungsi perbandingan, dan, jika perlu, fungsi yang menentukan aturan untuk enumerasi elemen. Paling sering digunakan sebagai gantinyapernyataan loop reguler.
Elemen pertama itu sendiri merupakan himpunan terurut, jadi perbandingannya dimulai dari yang kedua.
Algoritme sering menggunakan fungsi pembantu untuk menukar dua nilai (swap). Ini menggunakan variabel sementara tambahan, yang menghabiskan memori dan sedikit memperlambat kode.
Alternatifnya adalah menggeser massa sekelompok elemen dan kemudian memasukkan elemen saat ini ke dalam ruang kosong. Dalam hal ini, transisi ke elemen berikutnya terjadi ketika perbandingan memberikan hasil positif, yang menunjukkan urutan yang benar.
Contoh implementasi
Implementasi spesifik sangat tergantung pada bahasa pemrograman yang digunakan, sintaks dan strukturnya.
implementasi C Klasik menggunakan variabel sementara untuk menukar nilai:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; larik[j + 1]=larik[j]; array[j]=suhu; } }
Implementasi PHP:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Di sini, pertama, semua elemen yang tidak cocok dengan kondisi pengurutan digeser ke kanan, lalu elemen saat ini dimasukkan ke dalam ruang kosong.
Kode Java menggunakan while loop:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[kunci sebelumnya]; arr[prevKey]=currElem; prevKey--; } } }
Arti umum dari kode tetap tidak berubah: setiap elemen array secara berurutan dibandingkan dengan yang sebelumnya dan ditukar dengan mereka jika perlu.
Perkiraan waktu berjalan
Jelas, dalam kasus terbaik, masukan dari algoritme akan berupa larik yang sudah diurutkan dengan cara yang benar. Dalam situasi ini, algoritme hanya perlu memeriksa setiap elemen untuk memastikannya berada di tempat yang tepat tanpa melakukan pertukaran. Dengan demikian, waktu berjalan akan secara langsung bergantung pada panjang larik asli O(n).
Input kasus terburuk adalah array yang diurutkan dalam urutan terbalik. Ini akan membutuhkan banyak permutasi, fungsi runtime akan bergantung pada jumlah elemen yang dikuadratkan.
Jumlah permutasi yang tepat untuk array yang benar-benar tidak berurutan dapat dihitung menggunakan rumus:
n(n-1)/2
di mana n adalah panjang larik asli. Jadi, dibutuhkan 4950 permutasi untuk menyusun 100 elemen dalam urutan yang benar.
Metode penyisipan sangat efisien untuk menyortir array yang kecil atau terurut sebagian. Namun, tidak disarankan untuk menerapkannya di mana-mana karena rumitnya perhitungan.
Algoritme ini digunakan sebagai tambahan dalam banyak metode pengurutan lain yang lebih kompleks.
Urutkan nilai yang sama
Algoritme penyisipan termasuk dalam jenis yang disebut stabil. Itu berarti,bahwa itu tidak menukar elemen yang identik, tetapi mempertahankan urutan aslinya. Indeks stabilitas dalam banyak kasus penting untuk pemesanan yang benar.
Di atas adalah contoh visual yang bagus dari insertion sort dalam sebuah tarian.
