Daftar Isi[Bersembunyi][Menunjukkan]
Ilmu komputer adalah tentang memahami kompleksitas algoritma dan struktur data.
Anda memiliki daftar item yang perlu diurutkan, tetapi Anda tidak memiliki waktu atau sumber daya untuk menggunakan algoritme pengurutan yang lebih kompleks.
Penyortiran penyisipan adalah salah satu algoritme pengurutan yang paling sederhana, tetapi bisa lambat untuk daftar besar.
Implementasi dan pemahaman yang mudah membuat metode ini menjadi favorit di kalangan programmer. Ini sempurna untuk daftar kecil atau ketika Anda membutuhkan solusi cepat.
Dalam posting blog ini, kita akan melihat kompleksitas waktu pengurutan penyisipan. Algoritma ini digunakan untuk mengurutkan array, dan memiliki runtime O(n2). Ini berarti bahwa kompleksitas waktu meningkat dengan ukuran array.
Namun, algoritme ini seringkali lebih cepat daripada algoritme pengurutan lainnya, seperti quicksort.
Mari kita lihat lebih dekat cara kerja pengurutan penyisipan!
Apa Itu Algoritma Pengurutan Sisipan?
Satu elemen pada satu waktu, insertion sort menghasilkan array yang dapat diurutkan, yang sering disebut sebagai daftar.
Misalnya, pengurutan diterapkan dalam program komputer yang rumit seperti kompiler, di mana urutan token penting untuk interpretasi program.
Bagaimana Cara Kerja Insertion Sort?
Saat kita menggunakan insertion sort untuk mengurutkan array, algoritme dimulai dengan menemukan item terkecil dalam daftar dan memasukkannya ke posisi yang benar.
Kemudian menemukan item terkecil berikutnya dan memasukkannya ke posisi yang benar, dan seterusnya.
Algoritme bekerja dengan mengulang daftar, membandingkan setiap item dengan item sebelumnya.
Jika item berada dalam urutan yang salah, algoritme menukarnya. Kemudian memeriksa untuk melihat apakah daftar diurutkan, dan jika ya, algoritme berakhir.
Dalam praktiknya, insertion sort sering diimplementasikan menggunakan beberapa baris kode, menjadikannya pilihan populer untuk menyortir array kecil. Namun, kompleksitas waktu harus dipertimbangkan ketika menggunakan algoritma ini.
Contoh:
Berikut adalah contoh cara kerja pengurutan penyisipan. Kami akan menggunakan array berikut:
1, 2, 3, 4, 5, 6
Algoritma dimulai dengan menemukan item terkecil dalam daftar, yaitu 1. Kemudian memasukkannya ke posisi yang benar, posisi pertama. Ia kemudian menemukan item terkecil berikutnya, yaitu 2. Ia memasukkannya ke posisi yang benar, yaitu posisi kedua.
Ia kemudian menemukan item terkecil berikutnya, yaitu 3. Ia memasukkannya ke posisi yang benar, yaitu posisi ketiga.
Kemudian menemukan item terkecil berikutnya, yaitu 4. Ia memasukkannya ke posisi yang benar, yaitu posisi keempat, dan seterusnya. Daftarnya sekarang diurutkan!
Kita dapat melihat dari contoh bahwa algoritma membutuhkan enam perbandingan dan swap untuk mengurutkan daftar. Hal ini karena dibutuhkan n2 perbandingan dan swap untuk mengurutkan daftar n item. Dalam hal ini, n=6.
Bagaimana Meningkatkan Kompleksitas Waktu Pengurutan Penyisipan?
Sementara insertion sort memiliki runtime O(n2), dapat ditingkatkan dengan menggunakan algoritma pengurutan yang lebih baik, seperti quicksort.
Quicksort memiliki runtime O(n log n), yang jauh lebih cepat daripada O(n2).
Namun, dalam beberapa kasus, pengurutan penyisipan bisa lebih cepat daripada pengurutan cepat.
Misalnya, jika daftar sudah diurutkan, pengurutan penyisipan akan memakan waktu lebih sedikit daripada quicksort.
Dalam praktiknya, insertion sort sering diimplementasikan menggunakan beberapa baris kode, menjadikannya pilihan populer untuk menyortir array kecil.
Namun, kompleksitas waktu harus dipertimbangkan ketika menggunakan algoritma ini.
Kompleksitas Waktu
Kompleksitas Kasus Terburuk O(n2):
Kompleksitas waktu meningkat dengan ukuran array. Dibutuhkan n2 perbandingan dan swap untuk mengurutkan daftar n item.
Misalnya, jika kita memiliki array berukuran 1000, algoritma akan mengambil 1,000,000 perbandingan dan swap untuk mengurutkan array.
Kompleksitas Kasus Terbaik O(n):
Kompleksitas waktu sama dengan ukuran array input. Saya
t mengambil n perbandingan dan menukar untuk mengurutkan daftar n item. Sebagai contoh, pertimbangkan sebuah array berukuran 5. Algoritme akan mengambil lima perbandingan dan swap untuk mengurutkan array.
Kompleksitas Kasus Rata-rata O(n2):
Kompleksitas waktu berada di antara kompleksitas kasus terburuk dan terbaik dalam kasus ini.
Dibutuhkan n2 perbandingan dan swap untuk mengurutkan daftar n item.
Dengan demikian, pengurutan penyisipan adalah algoritma pengurutan yang stabil.
Mengapa Insertion Sort Stabil?
Jenis penyisipan stabil karena mempertahankan urutan elemen yang sama dalam array input.
Ini penting untuk banyak aplikasi, seperti pengambilan data atau analisis keuangan. Misalnya, jika kita memiliki dua daftar angka dan ingin membandingkannya, kita perlu memastikan bahwa urutan elemen dipertahankan.
Jika daftar tidak diurutkan, kami tidak akan membandingkannya secara akurat.
Tinggalkan Balasan