Insertion Sort

Insertion sort merupakan salah satu algoritma pengurutan dengan cara menyisipkan / insert jika menemukan nilai yang lebih kecil, sehingga algoritma ini menyelesaikan pengurutan secara bertahap dairi kiri ke kanan atau sebaliknya. Dengan syarat elemen yang akan diurutkan selanjutnya diurutkan dulu pada elemen-elemen yang telah terurut sebelumnya dengan cara langsung menyisipkan diantara elemen tersebut yang sesuai. Secara sederhana insertion sort dapat dijelaskan dengan deretan angka dibawah ini :

Data awal : 21 32 4 6 2 7 1

Langkah 1 : 21 32 4 6 2 7 1

Langkah 2 : 21 32 4 6 2 7 1

Langkah 3 : 4 21 32 6 2 7 1

Langkah 4 : 4 6 21 32 2 7 1

Langkah 5 : 2 4 6 21 32 7 1

Langkah 6 : 2 4 6 7 21 32 1

Langkah 7 : 1 2 4 6 7 21 32

Hasil : 1 2 4 6 7 21 32

Data yang berwarna merah merupakan data yang diurutkan (elemen), yang berwarna biru merupakan data yang disisipkan karena nilainya lebih kecil. Data yang berwarna hitam merupakan data yang tidak sorting. Sehingga jika digambarkan akan seperti deretan langkah langkah diatas. Entah itu secara ascending atau descending tetap saja urutan langkahnya seperti diatas, yaitu disisipkan ūüėÄ pelan pelan

Banyak orang analogikan dengan orang yang mengurutkan kartu, karena biasanya kartu diurutkan seperti ini, yaitu pelan-pelan disisipkan yang nilainya sesuai.

Contoh program Insertion Sort :

public class InsertionSort{
  public static void main(String a[]){
  int i;
  int array[] = {12,9,4,99,120,1,3,10};
  System.out.println(" Insertion Sort\n\n"); 
  System.out.println("Values Before the sort:\n");  
  for(i = 0; i < array.length; i++)
  System.out.print( array[i]+"  ");
  System.out.println();
  insertion_srt(array, array.length);  
  System.out.print("Values after the sort:\n");  
  for(i = 0; i <array.length; i++)
  System.out.print(array[i]+"  ");
  System.out.println(); 
  System.out.println("PAUSE"); 
  }

  public static void insertion_srt(int array[], int n){
  for (int i = 1; i < n; i++){
  int j = i;
  int B = array[i];
  while ((j > 0) && (array[j-1] > B)){
  array[j] = array[j-1];
¬†¬†j–;
  }
  array[j] = B;
  }
  }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s