1. κ°λ π
'κ³μ μ λ ¬'μ΄λΌκ³ λ λΆλ¦¬λ 'μΉ΄μ΄ν μ λ ¬(Counting Sort)'μ κ° μμλ€μ΄ λͺ κ°μ© μλμ§ λνλ΄λ countλ°°μ΄μ νμ©νλ μ λ ¬ μκ³ λ¦¬μ¦μ΄λ€.
κ° μμμ κ°μ΄ count λ°°μ΄μ μΈλ±μ€κ° λλ―λ‘ 'μ μλ μ μλ‘ ννν μ μλ μλ£'μ λν΄μλ§ μ μ© κ°λ₯νλ€.
2. λμλ°©μ π
λμ λ°©μμ λ€μκ³Ό κ°λ€.
- μμμ μ΅λκ°μ ν¬ν¨ν μ μλ λ°°μ΄ μ€μ
- κ°κ°μ μμκ° λͺ λ² λ±μ₯νλμ§ μΉ΄μ΄ν
count λ°°μ΄μ μΈλ±μ€ = μμ κ°
count λ°°μ΄μ κ° = λ±μ₯ νμ - count λ°°μ΄μ λμ ν©μΌλ‘ λ§λ€μ΄μ£ΌκΈ°
- μ λ ¬λμ§ μμ λ°°μ΄(μ΄κΈ°κ°)μ λ€μμλΆν° λλ©΄μ, μμμ κ°κ³Ό λμΌν μΈλ±μ€κ° κ°λ¦¬ν€λ κ³³μ μμ λ°°μΉν΄ μ£ΌκΈ°
'0 2 1 1 4 4 4 3 5'κ° μ£Όμ΄μ‘μ λ λμλ°©μμ μλμ κ·Έλ¦Όμ ν΅νμ¬ μ΄ν΄ν΄ 보μ.
λμλ°©μμμ 2κ°μ§ μλ¬Έμ μ΄ μκΈΈ μ μλ€.
- λ°°μ΄μ λ€μμλΆν° λλ©΄μ μ리λ₯Ό λ°°μΉν λ countκ°μ κ°μμν€λ μ΄μ λ?
countκ°μ κ°μμμΌμΌμ§ λ€μμ κ°μ κ°μ΄ λ€μ΄μμ λ μλ§μ μ리μ μ°Ύμκ° μ μλ€. μμμ count[4]μ ν΄λΉνλ κ°μ κ³μν΄μ κ°μμμΌ°κΈ° λλ¬Έμ '7, 6, 5'μ μΈλ±μ€μ ν΄λΉνλ μμΉμ 4κ° λ°°μΉλ μ μμλ€. - λμ ν©μ ν΄μ€μΌ νλ μ΄μ λ?
λμ ν©μ νμ§ μλ κ²½μ°μλ count λ°°μ΄μ λλ©΄μ 'idxκ°μ idxμ ν΄λΉνλ κ°'λ§νΌ λ°°μΉνλ©΄ λλ€. μμ μμ μμλ '0μ 1λ², 1μ 2λ², 2λ₯Ό 1λ², 3μ 1λ², 4λ₯Ό 3λ², 5λ₯Ό 1λ²' λ°°μΉνλ©΄, '0 1 1 2 3 4 4 4 5'λ₯Ό μ»μ μ μλ€.
νμ§λ§, μμ κ²½μ°μ λ¬λ¦¬ μ°μλ κ°μ΄ μλ '1 2023 0'μ μ λ ¬νλ κ³Όμ μ μκ°ν΄ 보μ. μ΄λ° κ²½μ° 0λΆν° 2023κΉμ§ countλ₯Ό λμμΌ νλ€.
κ·Έλ¬λ λμ ν©μ μ¬μ©νλ©΄ μμμ λμνλ κ²μ²λΌ μμμ κ°μμΈ Nλ§νΌλ§ countμ μ κ·Όνλ©΄ λλ€. μ΄λ¬ν μ μΌλ‘ μΈν΄ countλ₯Ό λμ ν©ν΄μ μ¬μ©νλ€.
3. ꡬν(JAVA) π©
public static void main(String[] args) {
int arr[] = {0, 2, 1, 1, 4, 4, 4, 3, 5};
int sorted_arr[] = new int[arr.length];
int maxValue = 0;
for(int i : arr) {
maxValue = Math.max(maxValue, i);
}
// 1. μμμ μ΅λκ°μ ν¬ν¨ν μ μλ λ°°μ΄ μ€μ
int count[] = new int[maxValue + 1];
// 2. κ°κ°μ μμκ° λͺ λ² λ±μ₯νλμ§ μΉ΄μ΄ν
for(int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
// 3. count λ°°μ΄μ λμ ν©μΌλ‘ λ§λ€κΈ°
for(int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 4. λ€μμλΆν° λ°°μ΄μ λλ©΄μ μμμ κ°κ³Ό λμΌν μΈλ±μ€κ° κ°λ₯΄ν€λ κ³³μ μμ λ°°μΉν΄μ£ΌκΈ°
for(int i = arr.length - 1; i >= 0; i--) {
count[arr[i]]--;
sorted_arr[count[arr[i]]] = arr[i];
}
for(int i : sorted_arr) {
System.out.print(i + " ");
}
// 0 1 1 2 3 4 4 4 5
}
4. μκ°λ³΅μ‘λ & 곡κ°λ³΅μ‘λ π
μκ°λ³΅μ‘λ
μμμ κ°μλ₯Ό Nμ΄λΌ νκ³ μμμ μ΅λκ°μ KλΌκ³ νμ. λμκ³Όμ μμμ μκ°λ³΅μ‘λλ μλμ κ°λ€.
- counting λ°°μ΄μ λ§λ€κΈ° → O(N)
- counting λ°°μ΄μ λμ ν© μν€κΈ° → O(N + K)
- λ€μμλΆν° λ°°μ΄μ λλ©΄μ, ν΄λΉνλ κ°μ μ΄μ©νμ¬ μΈλ±μ€μ μμ λ£μ΄μ£ΌκΈ° → O(N)
κ·Έλ¬λ―λ‘ μκ°λ³΅μ‘λλ O(N + K)μ΄λ€. νμ§λ§ μΌλ°μ μΌλ‘λ Kκ° ν° κ°μ κ°μ§μ§ μμΌλ―λ‘ νκ· μ μΈ μκ°λ³΅μ‘λλ O(N)μ΄λ€.
μ΅μ (BEST) | νκ· (AVERAGE) | μ΅μ (WORST) | |
μκ°λ³΅μ‘λ | O(N) | O(N) | O(N + K) |
곡κ°λ³΅μ‘λ
Kλ§νΌ λ°°μ΄μ λ§λ€μ΄μ€μΌ νλ―λ‘ κ³΅κ°λ³΅μ‘λλ O(K)μ΄λ€.
5. μ₯μ & λ¨μ π§’
μ₯μ
- μκ°λ³΅μ‘λ(νκ· )κ° O(N)μ΄λ€. (μΌλ°μ μΈ μν©μμ κ°μ₯ λΉ λ₯Έ μ λ ¬ μκ³ λ¦¬μ¦μΈ ν΅ μ λ ¬μ μκ°λ³΅μ‘λ O(N logN)μ λΉνλ©΄ λ§€μ° λΉ λ₯Έ κ²μ΄λ€.)
λ¨μ
- μΆκ°μ μΈ λ©λͺ¨λ¦¬ 곡κ°μ΄ νμνλ€.
- μΌλΆ κ°(μ΅λκ°)μ μν΄ λ©λͺ¨λ¦¬μ λλΉκ° μ¬ν΄μ§ μ μλ€.
ν΄λΉ κΈμ
Gyoogle λμ 'κ³μ μ λ ¬(Counting Sort)',
λ©λ©λ© λμ 'Counting Sort : κ³μ μ λ ¬',
Chappi λμ 'μκ³ λ¦¬μ¦ 6μΌμ°¨ - O(n) μ λ ¬, κ³μ μ λ ¬'
μ μ°Έκ³ νμμ΅λλ€.
'π μλ£κ΅¬μ‘° > μ λ ¬' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
ν΅ μ λ ¬ (Quick Sort) (0) | 2023.03.20 |
---|---|
ν μ λ ¬ (Heap Sort) (0) | 2023.03.12 |
μμ μ λ ¬(Topology Sort) (2) | 2023.03.07 |
λ³ν© μ λ ¬(Merge Sort) (0) | 2023.03.07 |
μ½μ μ λ ¬(Insertion Sort) (0) | 2023.03.06 |