Algoritma - Insertion Sort

Insertion sort merupakan algoritma yang agak menarik dengan expensive runtime O(n2) dimana algoritma ini termasuk simple sorting yang membangun array akhir yang diurutkan satu per satu. Metode ini mengikuti metode inkremental. Ini dapat dibandingkan dengan teknik bagaimana kartu disortir pada saat bermain game. Hal ini dapat dianggap sebagai skema penyortiran yang mirip dengan menyortir kartu remi, yaitu Anda mengambil satu kartu dan kemudian melihat sisanya dengan maksud membangun satu set kartu yang dipesan di tangan Anda. Pada setiap langkah, awalan ini ditumbuhkan dengan memasukkan nilai berikutnya ke dalamnya di tempat yang benar. Akhirnya, awalannya adalah seluruh array, yang karenanya diurutkan. Angka-angka, yang perlu disortir, dikenal sebagai keys.

Misalnya diaplikasikan pada data. Jika data yang anda ingin kelola sudah ada, pengurutan dimulai dengan mengambil satu data kemudian membandingkannya dengan data-data yang ada didepannya. Misal data yang diambil ternyata sudah memenuhi syarat perbandingan, sehingga data yang diambil tersebut akan diletakan di depan data yang dibandingkan, selanjutnya lihat data-data yang dibandingkan akan bergeser mundur.

box1

Sekali lagi bahwa running time dari algoritma ini sangat tergantung pada input yang diberikan. Jika nomor yang diberikan diurutkan, algoritma ini berjalan dalam waktu O(n). Jika nomor yang diberikan dalam urutan terbalik, algoritma berjalan dalam waktu O(n2). Ingat juga bahwa ketika melakukan pengurutan data menggunakan algoritma insertion sort maka data yang diambil pertama adalah data kedua sebagaimana contoh diatas, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri atau data sebelumnya sampai proses tersebut selesai. Kemudian dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

Nah dari dengan memiliki gambaran yang lebih besar tentang bagaimana teknik Insertion sort ini bekerja, sehingga kita dapat mengambil langkah-langkah sederhana yang dengannya kita dapat mencapai penyisipan. Maka algoritmanya bisa seperti ini:

  • Langkah 1 - Jika itu adalah elemen pertama, itu sudah diurutkan. return 1;
  • Langkah 2 - Pilih elemen berikutnya
  • Langkah 3 - Bandingkan dengan semua elemen dalam sub-daftar yang diurutkan
  • Langkah 4 - Geser semua elemen dalam sub-daftar yang diurutkan yang lebih besar dari nilai yang akan disortir
  • Langkah 5 - Masukkan nilainya
  • Langkah 6 - Ulangi sampai daftar diurutkan

Pseudocode secara garis besarnya seperti ini:

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert

   for i = 1 to length(A) inclusive do:

      / * pilih nilai yang akan dimasukkan * /
      valueToInsert = A[i]
      holePosition = i

      / * Cari posisi lubang untuk elemen yang akan dimasukkan * /

      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while

      / * masukkan nomor pada posisi lubang * /
      A[holePosition] = valueToInsert

   end for

end procedure

Untuk Kompleksitas Algoritma Insertion sort ini: Kompleksitas Waktu atau Time Complexity: O(n) untuk kasus terbaik, O(n^2) untuk kasus rata-rata dan terburuk Kompleksitas Ruang atau Space Complexity: O(1)

Keuntungan dari Algoritma Insertion sort: 1. Efisien untuk set data kecil 2. Sederhana untuk diimplementasikan 3. Melewati array hanya sekali. 4. Mereka bersifat adaptif; efisien untuk kumpulan data yang sudah disortir.

Kerugian dari Algoritma Insertion sort: Kurang efisien pada daftar dan array yang lebih besar Kasus terbaik: array sudah disortir Kasus terburuk: elemen benar-benar mundur