Selection Sort

Prinsip utama dari Selection Sort adalah mencari nilai terkecil dari suatu array dan menempatkannya sebagai elemen yang paling depan dengan cara menukar elemen tersebut dengan elemen yang paling depan. Setelah ditempatkan di paling depan, algoritma kembali melakukan iterasi, tetapi kali elemen yang paling depan tidak diikutkan karena sudah “terurut” dengan baik. Begitu seterusnya..

Untuk mode descending, nilai yang dicari adalah nilai terbesar.

Untuk lebih jelasnya silahkan perhatikan dua buah ilustrasi di bawah ini (ascending)

1. Ilustrasi dengan angka (dari Wikipedia)

   ( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ) Nilai min : 1, Target pertukaran : 5
   ( 1 5 4 2 8 ) -> ( 1 2 4 5 8 ) Nilai min : 2, Target pertukaran : 5
   ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 ) Nilai min : 4, Target pertukaran : 4
   ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 ) Nilai min : 5, Target pertukaran : 5

2. Ilustrasi dengan gambar (refresh browser anda jika gambar tidak bergerak)

   

Berikut ini saya sediakan implementasi Selection Sort dalam Java..

public class Sort {
  private Sort(){}

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

      T t = arr[i];
      arr[i] = arr[min];
      arr[min] = t;
    }

    return arr;
  }

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

      T t = arr[i];
      arr[i] = arr[min];
      arr[min] = t;
    }

    return arr;
  }
}

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