Insertion Sort: Metode Pengurutan Data dengan Cara Melakukan Perbandingan dan Penyisipan

by

Salah satu masalah yang sering dihadapi dalam bidang teknologi informasi dan komputer adalah pengurutan data. Terdapat banyak teknik pengurutan yang sudah ada dan digunakan, salah satunya adalah Insertion Sort. Dalam artikel ini, kita akan membahas mengenai metode pengurutan data tersebut, Insertion Sort, yang merupakan metode pengurutan dengan cara melakukan perbandingan dan penyisipan.

Apa itu Insertion Sort?

Insertion Sort adalah algoritma pengurutan sederhana yang bekerja dengan cara membandingkan elemen satu per satu dan menyisipkannya pada posisi yang tepat dalam array yang sudah diurutkan. Algoritma ini efektif untuk mengurutkan data jumlah kecil karena memiliki kompleksitas waktu O(n^2).

Cara Kerja Insertion Sort

Berikut adalah langkah-langkah dalam algoritma Insertion Sort:

  1. Pertama, anggap elemen pertama di dalam array sebagai array yang sudah diurutkan (subarray), dan sisanya sebagai array yang belum diurutkan.
  2. Kemudian, ambil elemen pertama dari array yang belum diurutkan (subarray selanjutnya) dan bandingkan dengan elemen-elemen pada array yang sudah diurutkan.

    3.0 Jika elemen yang dibandingkan lebih kecil dari elemen pertama yang sudah diurutkan, sisipkan elemen tersebut di posisi sebelum elemen yang dibandingkan.

    3.1 Jika elemen yang dibandingkan lebih besar, lanjutkan perbandingan ke elemen selanjutnya pada array yang sudah diurutkan.

  3. Ulangi langkah 2-3 hingga semua elemen dalam array yang belum diurutkan telah dibandingkan dan disisipkan ke posisi yang tepat pada array yang sudah diurutkan.
  4. Setelah semua elemen telah disisipkan, proses pengurutan selesai.

Metode ini efisien dalam mengurutkan sejumlah kecil data, tetapi kurang efisien bila digunakan untuk data yang lebih besar.

Contoh Penggunaan Insertion Sort

Misalkan kita memiliki array sebagai berikut:

[ 5, 3, 4, 1, 2 ]

Proses pengurutan dengan Insertion Sort akan dilakukan sebagai berikut:

  1. Elemen pertama (5) dianggap sudah diurutkan.
  2. Ambil elemen kedua (3), dan bandingkan dengan elemen yang sudah diurutkan (5). Karena 3 lebih kecil dari 5, elemen 3 disisipkan sebelum elemen 5.
  3. Array menjadi: [ 3, 5, 4, 1, 2 ]
  4. Ambil elemen ketiga (4), dan bandingkan dengan elemen yang sudah diurutkan (3, 5). Karena 4 lebih besar dari 3 dan lebih kecil dari 5, elemen 4 disisipkan di antara 3 dan 5.
  5. Array menjadi: [ 3, 4, 5, 1, 2 ]
  6. Ambil elemen keempat (1), dan bandingkan dengan elemen yang sudah diurutkan (3, 4, 5). Karena 1 lebih kecil dari 3, elemen 1 disisipkan sebelum elemen 3.
  7. Array menjadi: [ 1, 3, 4, 5, 2 ]
  8. Ambil elemen kelima (2), dan bandingkan dengan elemen yang sudah diurutkan (1, 3, 4, 5). Karena 2 lebih besar dari 1 dan lebih kecil dari 3, elemen 2 disisipkan di antara 1 dan 3.
  9. Array menjadi: [ 1, 2, 3, 4, 5 ]

Sekarang, array sudah diurutkan secara ascending.

Kesimpulan

Insertion Sort merupakan metode pengurutan data dengan cara melakukan perbandingan dan penyisipan. Metode ini cukup efisien untuk mengurutkan jumlah data yang kecil, namun kurang efisien untuk data yang lebih besar. Pemahaman tentang Insertion Sort dapat membantu pemrogram dalam memilih metode pengurutan yang tepat sesuai dengan kebutuhan mereka.

Leave a Comment