Insertion Sort

Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dasar dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun membentang dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian bandingkan  kartu tersebut, letakan kartu
dengan nilai terkecil di urutan paling atas. ambil satu kartu lagi dari meja pertama, kemudian bandingkan kartu yang baru diambil tersebut dengan karti yang berada di meja kedua, letakan kartu tersebut sesuai dengan urutannya.  Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua.



Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan. Pengenalan Pemrograman


Contoh

Algoritma

void insertionSort(Object array[], int startIdx, int endIdx) {

          for (int i = startIdx; i < endIdx; i++) { 

                     int k = i;

                     for (int j = i + 1; j < endIdx; j++) {

                             if  (((Comparable) array[k]).compareTo(array[j])>0) {

                                   k = j;

                             }

                     }

                       swap(array[i],array[k]);

          }

}