selection_sort.md

🏹 Selection Sort

📝 Deskripsi

Sorting ini akan dimulai dengan deklarasi index = 0. Setelah itu mencari nilai yang paling kecil dari list, lalu menukarkan posisi nilai terkecil dengan nilai di index saat ini.

Lalu index berpindah ke index = 1, dan mengulang bagian sebelumnya. Index bertambah dan mengulang pencarian sampai index mencapai index ke-2 dari akhir list(Misalkan : index terakhir list = 4(index pertama dari akhir), maka akhir index di index = 3)

Pencarian nilai tidak lagi melakukan cek ke nilai index dibawahnya, jadi jika index sudah di index = 1, index = 0 tidak akan diperiksa dan seterusnya

🖼️ Visualisasi

Sorce: http://www.xybernetics.com/techtalk/SortingAlgorithmsExplained/SortingAlgorithmsExplained.html

📎 Sample Code

// Selection Sort
List<int> selectionSort(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n -1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    int temp = arr[minIdx];
    arr[minIdx] = arr[i];
    arr[i] = temp;
  }
  
  return arr;
}

Penjelasan Code:

• For pertama akan digunakan untuk penetapan nilai index (sebagai i). i akan dimasukkan dulu dalam variable(minIdx contohnya), dimana variable ini akan diganti dengan index baru jika ada nilai dari index tersebut lebih kecil.
• Untuk Range dari for pertama, dimulai dari 0 sampai dengan index terakhir kurang 1. (Jadi misalkan index terakhir dari list 4 (dari panjang list 5), range nya hanya 0 - 3)
• Lalu masuk for ke-2 dengan mencari nilai yang terkecil dari list. Range dari for ini dari index setelah i sampai index terakhri (Jadi misalkan i = 0, dan index terakhir 4, range nya menjadi 1 - 4)
• Di for ini pengecekan nilai dari minIdx dilakukan. Kondisinya: _Jika nilai index dari for (yaitu j) lebih kecil dari nilai dari index minIdx, maka j akan masuk ke minIdx.
• Setelah for selesai di eksekusi, maka nilai dari index minIdx dan nilai dari index i akan saling bertukar. Setelah itu kembali lagi ke point pertama sampai for pertama terselesaikan.

FlowChart :

📜 Log

Contoh log yang dijalankan. Misalkan list yang dipunya ada [2, 8, 3, 1].
arr = [2, 8, 3, 1]
int n = arr.length; => int n = 4;
through For : (condition i = 0; i < n - 1; i++ => i = 0; i < 3; i++) (Range index : 0 - 2)
For i = 0 :
int minIdx = i; => int minIdx = 0;
through For : (condition j = i + 1; j < n; j++ => j = (0) + 1; i < 4; i++) (Range index : 1 - 3)
For j = 1 :
if (arr[j] < arr[minIdx]) => if (arr[1] < arr[0]) => if (8 < 2) :
execute: {}
For j = 2 :
if (arr[j] < arr[minIdx]) => if (arr[2] < arr[0]) => if (3 < 2) :
execute: {}
For j = 3 :
if (arr[j] < arr[minIdx]) => if (arr[3] < arr[0]) => if (1 < 2) :
execute: {
minIdx = j; => minIdx = 3;
}
For End
int temp = arr[minIdx]; => int temp = arr[3] => int temp = 1
arr[minIdx] = arr[i]; => arr[3] = arr[0] => arr[3] = 2
arr[i] = temp; => arr[0] = 1
now the current arr => [1, 8, 3, 2]
For i = 1 :
int minIdx = i; => int minIdx = 1;
through For : (condition j = i + 1; j < n; j++ => j = (1) + 1; i < 4; i++) (Range index : 2 - 3)
For j = 2 :
if (arr[j] < arr[minIdx]) => if (arr[2] < arr[1]) => if (3 < 8) :
execute: {
minIdx = j; => minIdx = 2;
}
For j = 3 :
if (arr[j] < arr[minIdx]) => if (arr[2] < arr[0]) => if (2 < 3) :
execute: {
minIdx = j; => minIdx = 3;
}
For End
int temp = arr[minIdx]; => int temp = arr[3] => int temp = 2
arr[minIdx] = arr[i]; => arr[3] = arr[1] => arr[3] = 8
arr[i] = temp; => arr[1] = 2
now the current arr => [1, 2, 3, 8]
For i = 2 :
int minIdx = i; => int minIdx = 2;
through For : (condition j = i + 1; j < n; j++ => j = (2) + 1; i < 4; i++) (Range index : 3)
For j = 3 :
if (arr[j] < arr[minIdx]) => if (arr[3] < arr[2]) => if (8 < 3) :
execute: {}
For End
int temp = arr[minIdx]; => int temp = arr[2] => int temp = 3
arr[minIdx] = arr[i]; => arr[2] = arr[2] => arr[3] = 3
arr[i] = temp; => arr[2] = 3
now the current arr => [1, 2, 3, 8]
For end
return arr => [1, 2, 3, 8]