κ±°ν μ λ ¬μ΄λΌκ³ λ λΆλ¦¬λ λ²λΈ μ λ ¬μ λν΄μ μμ보μ.
1. μ μ π
λ²λΈ μ λ ¬μ μλ‘ μΈμ ν λ μμλ₯Ό κ²μ¬νμ¬ μ λ ¬νλ μκ³ λ¦¬μ¦μ΄λ€.
2. λμ λ°©μ π
Nκ°μ μμκ° μλ€κ³ νμ.
첫 λ²μ§Έ μμμ λ λ²μ§Έ μμλ₯Ό λΉκ΅νμ¬ λ§μ½ 첫 λ²μ§Έ μμκ° λ ν¬λ€λ©΄ λμ μ리λ₯Ό λ°κΏμ€λ€. κ·Έλ¦¬κ³ λ λ²μ§Έ μμμ μΈ λ²μ§Έ μμλ₯Ό λΉκ΅νμ¬ λ§μ½ λ λ²μ§Έ μμκ° λ ν¬λ€λ©΄ λμ μ리λ₯Ό λ°κΏμ€λ€. μ΄λ¬ν λμμ (λ§μ§λ§ - 1) λ²μ§Έμ μμμ λ§μ§λ§ μμλ₯Ό λΉκ΅ν λκΉμ§ μννλ€.
μ΄κ²μ΄ 1νμ μνν κ²μ΄λ€. μ΄λ κ² λλ©΄ λ§μ§λ§μ μμΉν μμκ° κ°μ₯ ν° μμκ° λλ€. 2νμ μ μνν λ λ§μ§λ§ μμλ₯Ό μ μΈν λλ¨Έμ§λ€μ μ λ ¬ν΄ μ€λ€. (N - 1) νμ κΉμ§ μννλ©΄ μ λ ¬μ΄ λ§λ¬΄λ¦¬λλ€.
μμ λ°©μμ μ€λ¦μ°¨μμΌλ‘ μ λ ¬μ νκ³ μλ€. λ§μ½ λμλ₯Ό λΉκ΅νμ¬ λ€μ μμκ° λ ν΄ λ μμ μμμ μ리λ₯Ό λ°κΎΌλ€λ©΄ λ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬μ ν μ μλ€.
3. ꡬν(JAVA) π₯Ύ
static void bubbleSort(int[] arr) {
int temp = 0;
// (μμμ κ°μ - 1)λ² λ°λ³΅
for(int i = 0; i < arr.length - 1; i++) {
// μΈμ ν λ μμλ₯Ό λμλΉκ΅
// νμ μκ° μ¦κ°ν¨μ λ°λΌμ μ λ ¬μ΄ λ λ€μ μλ μμλ€μ λΉκ΅μμ μ μΈ
for(int j = 1; j < arr.length - i; j++) {
if(arr[j - 1] < arr[j]) {
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
4. μκ°λ³΅μ‘λ & 곡κ°λ³΅μ‘λ π’
1. μκ°λ³΅μ‘λ
μμμ μ΄ν΄λ΄€λ―μ΄ μ΄ (N - 1)λ² νμ νκ³ , iλ²μ§Έ νμ μμ (N - i)μ μ°μ°μ μννλ€. κ·Έλ¬λ©΄, μλμ ν΄λΉνλ μλ§νΌ μ°μ°μ μννλ€.
(N - 1) + (N - 2) + (N - 3) + ... + 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λμ κ±°ν μ λ ¬(Bubble 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 |
μ ν μ λ ¬(Selection Sort) (2) | 2023.03.04 |