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
Sorce: http://www.xybernetics.com/techtalk/SortingAlgorithmsExplained/SortingAlgorithmsExplained.html
// 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
(sebagaii
).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 misalkani
= 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 indexminIdx
, makaj
akan masuk ke minIdx. - Setelah for selesai di eksekusi, maka nilai dari index
minIdx
dan nilai dari indexi
akan saling bertukar. Setelah itu kembali lagi ke point pertama sampai for pertama terselesaikan.
FlowChart :
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]