μ ν μ λ ¬μ μ¬λ¬ κ°μ§ λ©΄μμ μμμ μ΄ν΄λ³Έ λ²λΈ μ λ ¬κ³Ό μλΉν λΉμ·νλ€. λ κ°μ§ μ λ ¬ λ°©λ²μ ꡬλΆνλ κ² μ΄λ ΅μ§λ μμΌλ, μ ν μ λ ¬μ 곡λΆνλ κΉμ λ²λΈ μ λ ¬λ κ°μ΄ 곡λΆνλ κ²μ μΆμ²νλ€.
1. μ μ πΏ
μ ν μ λ ¬μ μμλ₯Ό λ£μ μμΉλ μ΄λ―Έ μ ν΄μ Έ μκ³ , μ΄λ€ μμλ₯Ό λ£μμ§ μ ννλ μκ³ λ¦¬μ¦μ΄λ€.
2. λμ λ°©μ π§¦
Nκ°μ μμκ° μλ€κ³ νμ.
μ°μ , λ°°μ΄μμ μ΅μκ°μ μ°Ύλλ€. κ·Έλ¦¬κ³ μ²« λ²μ§Έ μμμ λ°°μ΄μμ μ°Ύμ μ΅μκ°μ μμλ₯Ό λ°κΏμ€λ€. μ΄κ²μ΄ 1νμ μνν κ²μ΄λ€. μ΄λ κ² λλ©΄ λ°°μ΄μ 첫 λ²μ§Έμ μμΉν μμκ° κ°μ₯ μμ κ°μ κ°μ§κ² λλ€.
2νμ μ μνν λλ 첫 λ²μ§Έ μμλ₯Ό μ μΈν λλ¨Έμ§ λ°°μ΄λ€ μ€μμ μ΅μκ°μ μ°Ύλλ€. κ·Έλ¦¬κ³ ν΄λΉ μμμ λ°°μ΄μ λ λ²μ§Έ μμλ₯Ό λ°κΏμ€λ€. μ΄μ κ°μ λ°©μμΌλ‘ (N -1) νμ κΉμ§ μννλ©΄ μ λ ¬μ΄ λ§λ¬΄λ¦¬λλ€.
μμ λ°©μμ μ€λ¦μ°¨μμΌλ‘ μ λ ¬μ νκ³ μλ€. λ§μ½ λ°°μ΄ μ€μμ μ΅μκ°μ΄ μλ μ΅λκ°μ μ°Ύμμ μ λ ¬νλ€λ©΄ λ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬ν μ μλ€.
3. ꡬν(JAVA) π‘
void selectionSort(int[] arr) {
int indexMin, temp;
// (μμμ κ°μ - 1)λ² λ°λ³΅
for(int i = 0; i < arr.length - 1; i++) {
// μ£Όμ΄μ§ λ°°μ΄μμ μ΅μκ° μμμ μΈλ±μ€ λ²νΈ μ°ΎκΈ°
indexMin = i;
for(int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[indexMin]) {
indexMin = j;
}
}
// μ΄λ―Έ μ ν΄μ Έμλ κ΅ν μμΉμ κ°κ³Ό μ΅μκ° κ΅ν
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
}
4. μκ°λ³΅μ‘λ & 곡κ°λ³΅μ‘λ π
1. μκ°λ³΅μ‘λ
μμμ μ΄ν΄λ³΄μλ―μ΄ μ΄ (N - 1)λ² νμ νκ³ , iλ²μ§Έ νμ μμ (N - i)μ μ°μ°μ μννλ€. κ·Έλ¬λ©΄, μλμ ν΄λΉνλ μλ§νΌ μ°μ°μ μννκ² λλ€.
(N - 1) + (N - 2) + ... + 2 + 1 = N * (N - 1) / 2
λ°λΌμ, μκ°λ³΅μ‘λλ O(N^2)μ΄λ€.
μ λ ¬μ΄ λμ΄μλ μλμ΄ μλ νμ λΉκ΅λ₯Ό μννλ―λ‘ μ΅μ , νκ· , μ΅μ
μ μν©μμ λͺ¨λ O(N^2)μ μκ°λ³΅μ‘λλ₯Ό κ°μ§λ€.
μ΅μ (BEST) | νκ· (AVERAGE) | μ΅μ (WORST) | |
μκ°λ³΅μ‘λ | O(N^2) | O(N^2) | O(N^2) |
2. 곡κ°λ³΅μ‘λ
곡κ°λ³΅μ‘λμ κ²½μ° μΆκ°μ μΈ λ°°μ΄μ λ§λ€μ§ μκ³ ν΄λΉ λ°°μ΄μμ κ΅νμ΄ μ΄λ£¨μ΄μ§λ―λ‘ O(N)μ΄λ€.
5. μ₯μ & λ¨μ π¦Ά
1. μ₯μ
- μ½λκ° λ§€μ° λ¨μνλ€.
- λ€λ₯Έ λ©λͺ¨λ¦¬ 곡κ°μ νμλ‘ νμ§ μλλ€.
2. λ¨μ
- μκ°λ³΅μ‘λκ° O(N^2)μ΄λ―λ‘ μλΉν λΉν¨μ¨μ μ΄λ€.
- μ λ ¬μ΄ λμ΄μλλΌλ λΉκ΅ μ°μ°μ μννλ€.
ν΄λΉ κΈμ Gyoogleλμ μ ν μ λ ¬(Selection Sort)μ μ°Έκ³ νμμ΅λλ€.
'π μλ£κ΅¬μ‘° > μ λ ¬' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
ν μ λ ¬ (Heap Sort) (0) | 2023.03.12 |
---|---|
μμ μ λ ¬(Topology Sort) (2) | 2023.03.07 |
λ³ν© μ λ ¬(Merge Sort) (0) | 2023.03.07 |
μ½μ μ λ ¬(Insertion Sort) (0) | 2023.03.06 |
λ²λΈ μ λ ¬(Bubble Sort) (0) | 2023.03.04 |