# μ ν μ λ ¬(Selection Sort)
# Goal
- Selection Sortμ λν΄ μ€λͺ ν μ μλ€.
- Selection Sort κ³Όμ μ λν΄ μ€λͺ ν μ μλ€.
- Selection Sortμ ꡬνν μ μλ€.
- Selection Sortμ μκ°λ³΅μ‘λμ 곡κ°λ³΅μ‘λλ₯Ό κ³μ°ν μ μλ€.
# Abstract
Selection Sortλ Bubble Sortκ³Ό μ μ¬ν μκ³ λ¦¬μ¦μΌλ‘, ν΄λΉ μμμ μμλ₯Ό λ£μ μμΉλ μ΄λ―Έ μ ν΄μ Έ μκ³ , μ΄λ€ μμλ₯Ό λ£μμ§ μ ννλ μκ³ λ¦¬μ¦μ΄λ€.
Selection Sortμ Insertion Sortλ₯Ό ν·κ°λ €νλ μ¬λλ€μ΄ μ’ μ’ μλλ°, Selection Sortλ λ°°μ΄μμ ν΄λΉ μ리λ₯Ό μ ννκ³ κ·Έ μ리μ μ€λ κ°μ μ°Ύλ κ²μ΄λΌκ³ μκ°νλ©΄ νΈνλ€.
# Process (Ascending)
- μ£Όμ΄μ§ λ°°μ΄ μ€μ μ΅μκ°μ μ°Ύλλ€.
- κ·Έ κ°μ 맨 μμ μμΉν κ°κ³Ό κ΅μ²΄νλ€. (pass)
- 맨 μ²μ μμΉλ₯Ό λΊ λλ¨Έμ§ λ°°μ΄μ κ°μ λ°©λ²μΌλ‘ κ΅μ²΄νλ€.
# Java Code (Ascending)
void selectionSort(int[] arr) {
int indexMin, temp;
for (int i = 0; i < arr.length-1; i++) { // 1.
indexMin = i;
for (int j = i + 1; j < arr.length; j++) { // 2.
if (arr[j] < arr[indexMin]) { // 3.
indexMin = j;
}
}
// 4. swap(arr[indexMin], arr[i])
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
μ°μ , μμΉ(index)λ₯Ό μ νν΄μ€λ€.
i+1λ²μ§Έ μμλΆν° μ νν μμΉ(index)μ κ°κ³Ό λΉκ΅λ₯Ό μμνλ€.
μ€λ¦μ°¨μμ΄λ―λ‘ νμ¬ μ νν μ리μ μλ κ°λ³΄λ€ μννκ³ μλ κ°μ΄ μλ€λ©΄, μμΉ(index)λ₯Ό κ°±μ ν΄μ€λ€.
'2'λ² λ°λ³΅λ¬Έμ΄ λλ λ€μλ indexMinμ '1'λ²μμ μ νν μμΉ(index)μ λ€μ΄κ°μΌνλ κ°μ μμΉ(index)λ₯Ό κ°κ³ μμΌλ―λ‘ μλ‘ κ΅ν(swap)ν΄μ€λ€.
# GIFλ‘ μ΄ν΄νλ Selection Sort
# μκ°λ³΅μ‘λ
λ°μ΄ν°μ κ°μκ° nκ°λΌκ³ νμ λ,
첫 λ²μ§Έ νμ μμμ λΉκ΅νμ : 1 ~ (n-1) => n-1
λ λ²μ§Έ νμ μμμ λΉκ΅νμ : 2 ~ (n-1) => n-2
...
(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
λΉκ΅νλ κ²μ΄ μμ μκ°μ μ΄λ£¨μ΄μ§λ€λ κ°μ μλ, nκ°μ μ£Όμ΄μ§ λ°°μ΄μ μ λ ¬νλλ° O(n^2) λ§νΌμ μκ°μ΄ κ±Έλ¦°λ€. μ΅μ , νκ· , μ΅μ μ κ²½μ° μκ°λ³΅μ‘λλ O(n^2) μΌλ‘ λμΌνλ€.
# 곡κ°λ³΅μ‘λ
μ£Όμ΄μ§ λ°°μ΄ μμμ κ΅ν(swap)μ ν΅ν΄, μ λ ¬μ΄ μνλλ―λ‘ O(n) μ΄λ€.
# μ₯μ
Bubble sortμ λ§μ°¬κ°μ§λ‘ μκ³ λ¦¬μ¦μ΄ λ¨μνλ€.
μ λ ¬μ μν λΉκ΅ νμλ λ§μ§λ§, Bubble Sortμ λΉν΄ μ€μ λ‘ κ΅ννλ νμλ μ κΈ° λλ¬Έμ λ§μ κ΅νμ΄ μΌμ΄λμΌ νλ μλ£μνμμ λΉκ΅μ ν¨μ¨μ μ΄λ€.
Bubble Sortμ λ§μ°¬κ°μ§λ‘ μ λ ¬νκ³ μ νλ λ°°μ΄ μμμ κ΅ννλ λ°©μμ΄λ―λ‘, λ€λ₯Έ λ©λͺ¨λ¦¬ 곡κ°μ νμλ‘ νμ§ μλλ€. => μ μ리 μ λ ¬(in-place sorting)
# λ¨μ
μκ°λ³΅μ‘λκ° O(n^2)μΌλ‘, λΉν¨μ¨μ μ΄λ€.
λΆμμ μ λ ¬(Unstable Sort) μ΄λ€.
# Conclusion
Bubble Sortμ μ μ¬νμ§λ§, μ‘°κΈ λ λΉ λ₯Έ Selection Sortμ λν΄ μμλ΄€λ€. κΈ°μ λ©΄μ μ΄λ μν(nλ²μ§Έ νμ μ μ λ ¬ μν)μμλ μ’ μ’ λμ€λ μ λ ¬μ΄λ μμλλ©΄ μ’λ€.