Insertion Sort

Pada prinsipnya, Insertion Sort mengambil suatu elemen dari array lalu “menyisipkannya” di tempat yang benar. Proses dilakukan terus menerus sampai seluruh elemen telah berada di tempat yang benar.

Coba perhatikan ilustrasi di bawah ini..

( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ) karena 5 > 1
( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ) karena 5 > 4
( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ) karena 5 > 2, -> ( 1 2 4 5 8 ) karena 4 > 2
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

Berikut ini saya sediakan implementasi dari Insertion Sort dalam java :

public class Sort {
  private Sort(){}

  public static <T extends Comparable> T[] insertion(T[] arr, boolean isAscending){
    for (int i = 1; i < arr.length; i++) {
      int j = i;
      T t = arr[i];
      while ((j > 0) && (
          isAscending && (arr[j - 1].compareTo(t) > 0) ||
          !isAscending && (arr[j - 1].compareTo(t) < 0))) {
        arr[j] = arr[j - 1];
        j--;
      }
      arr[j] = t;
    }

    return arr;
  }

  public static T[] insertion(T[] arr, Comparator comparator, boolean isAscending){
    for (int i = 1; i < arr.length; i++) {
      int j = i;
      T t = arr[i];
      while ((j > 0) && (
          isAscending && (comparator.compare(arr[j - 1], t) > 0) ||
          !isAscending && (comparator.compare(arr[j - 1], t) < 0))) {
        arr[j] = arr[j - 1];
        j--;
      }
      arr[j] = t;
    }

    return arr;
  }
}

Untuk eksekusi kode di atas, silahkan lihat post Bubble Sort.