Insertion Sort

Insertion sort juga merupakan teknik pengurutan yang memiliki kompleksitas waktu O(n²), tetapi sedikit lebih optimal daripada bubble sort.

Dalam algoritma ini, array dibagi menjadi dua bagian. Satu bagian terurut dan bagian lainnya belum terurut. Kita memilih sebuah elemen dari array yang belum terurut dan menempatkannya di posisi yang tepat dalam array yang terurut.

Kita mengulangi proses ini sampai semua elemen terurut.

1. Misalkan kita memiliki array {8,4,1,5}. Anggap elemen pertama sudah terurut dan semua elemen lainnya belum terurut. Awalnya, elemen ke-0 dianggap sudah terurut.

2. Buat variabel temp dan masukkan elemen ke-(i) (dalam contoh ini, nilainya 4). Bandingkan temp dengan array yang saat ini sudah terurut, yaitu 8. Karena 4<8, geser array yang terurut ke kanan sampai 4 berada di posisi yang tepat. Dalam kasus ini, 8 harus dipindahkan satu kali. Sekarang panjang array yang terurut menjadi 2.

3. Kita mengulangi proses ini sampai seluruh array terurut.

for(int i=1;i<n;i++){           //Mulai dari elemen pertama karena elemen ke-0 dianggap sudah terurut
    int temp=arr[i];
    
    int j=i-1;                  //Periksa semua elemen di sebelah kirinya 
    
    while(arr[j]>temp && j>=0){ //Geser elemen selama nilainya lebih besar dari temp, hingga elemen pertama
      arr[j+1]=arr[j];          //Geser elemen satu posisi ke kanan
      j--;                      
    }
    
    arr[j+1]=temp;              //Tempatkan temp pada posisi yang tepat
  
}

Untuk melihat insertion sort secara visual

Visualisasi Insertion Sort