Home > Archive > DataStructure > πŸ“¦[DataStructure] μ‚½μž… μ •λ ¬

πŸ“¦[DataStructure] μ‚½μž… μ •λ ¬
DataStructure

μ‚½μž… μ •λ ¬.

λ°°μ—΄ ꡬ쑰λ₯Ό μ–΄λ–»κ²Œ μ‚¬μš©ν•  수 μžˆλŠ”μ§€ μ΄ν•΄ν•˜λŠ” κ°€μž₯ 쒋은 방법은 μ‹€μ œ μ•Œκ³ λ¦¬μ¦˜μ„ κ²€ν† ν•˜λŠ” κ²ƒμž…λ‹ˆλ‹€.

  • μ‚½μž… μ •λ ¬(insertion sort) 은 λ°°μ—΄μ˜ 값을 μ •λ ¬ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, μˆœμ„œλ₯Ό μ •ν•  수 μžˆλŠ” λͺ¨λ“  μœ ν˜•μ˜ κ°’μ—μ„œ μž‘λ™ν•©λ‹ˆλ‹€.
    • μ •μˆ˜, λ¬Έμžμ—΄, 심지어 μœ ν†΅κΈ°ν•œμ— 따라 μ €μž₯된 μ°½κ³  μ•ˆ μ»€ν”ΌκΉŒμ§€ μ‚½μž… μ •λ ¬λ‘œ μ •λ ¬ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

μ‚½μž… 정렬은 λ°°μ—΄μ˜ 일뢀λ₯Ό μ •λ ¬ν•˜κ³ , 이 μ •λ ¬λœ λ²”μœ„λ₯Ό 전체 배열이 정렬될 λ•ŒκΉŒμ§€ ν™•μž₯ν•©λ‹ˆλ‹€.

  • μ•Œκ³ λ¦¬μ¦˜μ€ μ •λ ¬λ˜μ§€ μ•Šμ€ λ°°μ—΄μ˜ 각 μ›μ†Œλ₯Ό λ°˜λ³΅ν•˜λ©΄μ„œ μ •λ ¬λœ λΆ€λΆ„μ˜ μ˜¬λ°”λ₯Έ μœ„μΉ˜λ‘œ μ΄λ™ν•©λ‹ˆλ‹€.

i의 λ°˜λ³΅μ„ μ‹œμž‘ν•˜λŠ” μ‹œμ μ— i-1 μ΄ν•˜μ˜ μœ„μΉ˜μ— μžˆλŠ” μ›μ†ŒλŠ” λͺ¨λ‘ μ •λ ¬λ˜ μžˆμŠ΅λ‹ˆλ‹€.

  • μ•Œκ³ λ¦¬μ¦˜μ€ 이제 인덱슀 i에 μžˆλŠ” μ›μ†Œλ₯Ό μ„ νƒν•˜κ³ , μ •λ ¬λœ μ ‘λ‘μ‚¬μ—μ„œ 이 μ›μ†Œμ˜ μ˜¬λ°”λ₯Έ μœ„μΉ˜λ₯Ό μ°Ύμ•„ λ‚˜λ¨Έμ§€ μ›μ†Œλ₯Ό λ’€λ‘œ μ΄λ™μ‹œμΌœμ„œ μ„ νƒν•œ μ›μ†Œκ°€ λ“€μ–΄κ°ˆ 곡간을 λ§Œλ“  수 μ‚½μž…ν•©λ‹ˆλ‹€.
    • 그러면 μ •λ ¬λœ 접두사가 ν•˜λ‚˜ 더 μ»€μ§€λ©΄μ„œ 0μ—μ„œ iκΉŒμ§€ λͺ¨λ“  μƒμžκ°€ μ •λ ¬λœ μƒνƒœκ°€ λ©λ‹ˆλ‹€.
      • μ²˜μŒμ—λŠ” 첫 번째 μ›μ†Œλ₯Ό 초기 μ •λ ¬λœ μ ‘λ‘μ‚¬λ‘œ μ„ μ–Έν•˜κ³  i = 1λΆ€ν„° λ°˜λ³΅μ„ μ‹œμž‘ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

컀피 μ»¬λ ‰μ…˜μ„ μ‹ μ„ λ„μˆœμœΌλ‘œ μ •λ ¬ν•˜κ³  μ‹Άλ‹€κ³  ν•©μ‹œλ‹€.

무엇보닀 프리미엄 컀피가 μ°½κ³  κΉŠμˆ™μ΄ λ°•ν˜€ μžˆλ‹€ μƒν•΄λ²„λ¦¬λŠ” 비극은 λ°”λžŒμ§ν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

  • λ”°λΌμ„œ μœ ν†΅κΈ°ν•œμ΄ 제일 짧게 남은 컀피λ₯Ό κ°€μž₯ μ•žμͺ½μ— λ„£μ–΄μ„œ μ‰½κ²Œ μ ‘κ·Όν•  수 있게 ν•΄μ•Όν•©λ‹ˆλ‹€.

μš°μ„  컀피백 ν•˜λ‚˜λ₯Ό μ •λ ¬λœ λΆ€λΆ„μœΌλ‘œ μ„ μ–Έν•˜κ³ , 이λ₯Ό κΈ°μ€€μœΌλ‘œ μ •λ ¬ λ²”μœ„λ₯Ό μ„€μ •ν•¨μœΌλ‘œμ¨ 컀피 정렬을 μ‹œμž‘ν•©λ‹ˆλ‹€.

  • κ·Έ λ‹€μŒμ—λŠ” κ°€μž₯ μ•žμͺ½μ—μ„œ 두 번째 λ°±λΆ€ν„° λ‚ μ§œλ₯Ό 비ꡐ해 μ •λ ¬λœ λΆ€λΆ„μ˜ 백보닀 더 μ•žμ— λ„£μ–΄μ•Ό 할지λ₯Ό νŒλ‹¨ν•©λ‹ˆλ‹€.
    • μœ„μΉ˜λ₯Ό λ°”κΏ€ ν•„μš”κ°€ μžˆλŠ” κ²½μš°μ—” μˆœμ„œλ₯Ό λ°”κΎΈκ³ , 그렇지 μ•Šμ€ κ²½μš°μ—” 자리λ₯Ό μœ μ§€ν•©λ‹ˆλ‹€.
      • 이제 μžμ‹  있게 맨 μ•žμ˜ 두 백이 정렬됐닀고 말할 수 μžˆμŠ΅λ‹ˆλ‹€.

μ΄λ ‡κ²Œ λΆ€λΆ„μ μœΌλ‘œ μ •λ ¬ν•˜λŠ” 과정을 λ§ˆμ§€λ§‰ λ°±κΉŒμ§€ μ§„ν–‰ν•˜λ©΄μ„œ μœ„μΉ˜λ₯Ό λ°”κΎΈλŠ” μž‘μ—…μ„ λ°˜λ³΅ν•˜λ©΄, 컀피 μ»¬λ ‰μ…˜μ„ μ™„λ²½ν•˜κ²Œ 정리할 수 μžˆμŠ΅λ‹ˆλ‹€.

μ•„λž˜ μ½”λ“œμ™€ 같이 μ€‘μ²©λœ 루프λ₯Ό μ΄μš©ν•΄ μ‚½μž… 정렬을 κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

InsertionSort(array: A):
    Integer: N = length(A)
    Integer: i = 1
    WHILE i < N: // 1
        Type: current = A[i]
        Integer: j = i - 1
            WHILE j >= 0 AND A[j] > current: // 2
                A[j + 1] = A[j]
                j = j - 1
            A[j + 1] = current
            i = i +1
  • λ°”κΉ₯μͺ½ λ£¨ν”„λŠ” 졜초의 μ •λ ¬λ˜μ§€ μ•Šμ€ μ›μ†ŒμΈ 인덱슀 iκ°€ 1인 μ›μ†ŒλΆ€ν„° μ‹œμž‘ν•˜κ³  μ •λ ¬λ˜μ§€ μ•Šμ€ λ²”μœ„μ— μžˆλŠ” 각 값을 λ°˜λ³΅ν•©λ‹ˆλ‹€(1)
    • μ•ˆμͺ½ λ£¨ν”„λŠ” 인덱슀 jλ₯Ό μ‚¬μš©ν•΄ μ •λ ¬λœ μ ‘λ‘μ‚¬μ˜ μ›μ†Œλ₯Ό 맨 λ’€μ—μ„œλΆ€ν„° ν•˜λ‚˜μ”© λ°˜λ³΅ν•©λ‹ˆλ‹€(2)
      • 반볡 각 λ‹¨κ³„μ—μ„œ ν˜„μž¬ κ°’κ³Ό μ •λ ¬λœ 접두사 μ•ˆμ— μžˆλŠ” 인덱슀 j의 값을 비ꡐ해 ν™•μΈν•©λ‹ˆλ‹€.
      • j에 μžˆλŠ” μ›μ†Œκ°€ 더 크면 두 κ°’μ˜ μˆœμ„œκ°€ 잘λͺ»λμœΌλ―€λ‘œ κ΅ν™˜ν•΄μ•Ό ν•©λ‹ˆλ‹€.
      • ν˜„μž¬ 값을 λ³„λ„μ˜ λ³€μˆ˜μΈ current에 μ €μž₯ν–ˆκΈ° λ•Œλ¬Έμ— 이전 μƒμžμ—μ„œ 데이터λ₯Ό 직접 λ³΅μ‚¬ν•©λ‹ˆλ‹€.
        • 즉, iλ²ˆμ§Έμ™€ j번째의 값을 μ™„μ „νžˆ κ΅ν™˜ν•  ν•„μš”κ°€ μ—†μŠ΅λ‹ˆλ‹€.
        • λ‚΄λΆ€ λ£¨ν”„λŠ” ν˜„μž¬ 값을 λ°°μ—΄μ˜ 맨 μ•žμ— λ°€μ–΄λ„£κ±°λ‚˜ ν˜„μž¬ 값보닀 이전 값이 더 μž‘μ„ λ•ŒκΉŒμ§€λ§Œ(이 κ²½μš°κ°€ λ°”λ‘œ ν˜„μž¬ 값이 μ •λ ¬λœ μ ‘λ‘μ‚¬μ˜ μ˜¬λ°”λ₯Έ μœ„μΉ˜μ— μžˆμŒμ„ λ‚˜νƒ€λƒ…λ‹ˆλ‹€.) 계속 μ§„ν–‰ν•©λ‹ˆλ‹€.
          • 이제 λ‚΄λΆ€ λ£¨ν”„μ˜ λμ—μ„œ ν˜„μž¬ 값을 μ˜¬λ°”λ₯Έ μœ„μΉ˜μ— μ“°κΈ°λ§Œ ν•˜λ©΄ λ©λ‹ˆλ‹€.
          • λ°”κΉ₯μͺ½ λ£¨ν”„λŠ” λ‹€μŒ μ •λ ¬λ˜μ§€ μ•Šμ€ κ°’μœΌλ‘œ μ§„ν–‰ν•©λ‹ˆλ‹€.

μ•„λž˜ 그림은 μ•Œκ³ λ¦¬μ¦˜μ΄ μ–΄λ–»κ²Œ λ™μž‘ν•˜λŠ”μ§€ μ‹œκ°ν™”ν•΄ λ³΄μ—¬μ€λ‹ˆλ‹€.

  • 각 쀄은 반볡 μ‹œμž‘ μ‹œ λ°°μ—΄μ˜ μƒνƒœλ₯Ό λ³΄μ—¬μ€λ‹ˆλ‹€.
    • 빨간색 μƒμžλŠ” ν˜„μž¬ μœ„μΉ˜μ— μžˆλŠ” μ›μ†Œλ₯Ό λ‚˜νƒ€λ‚΄λ©°, ν™”μ‚΄ν‘œλŠ” ν˜„μž¬ μœ„μΉ˜μ˜ μ›μ†Œλ₯Ό μ‚½μž…ν•˜λ©΄μ„œ λ°œμƒν•˜λŠ” 이동을 λ‚˜νƒ€λƒ…λ‹ˆλ‹€.

μ‚½μž… 정렬은 κ·Έλ ‡κ²Œ νš¨μœ¨μ μ΄μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

  • 배열에 μ›μ†Œλ₯Ό μ‚½μž…ν•  λ•Œ, 상당 뢀뢄을 이동해야 ν•  μˆ˜λ„ μžˆμŠ΅λ‹ˆλ‹€.
  • μ΅œμ•…μ˜ 경우(worst-case), μ•Œκ³ λ¦¬μ¦˜μ˜ λΉ„μš©μ€ μ‹œν€€μŠ€ μ›μ†Œ 수의 μ œκ³±μ— λΉ„λ‘€ν•©λ‹ˆλ‹€.
    • 즉, μ΅œμ•…μ˜ 경우 리슀트의 λͺ¨λ“  μ›μ†Œλ§ˆλ‹€ μ•žμ˜ λͺ¨λ“  μ›μ†Œλ₯Ό μ΄λ™ν•΄μ•Όν•©λ‹ˆλ‹€.
      • λ°°μ—΄μ˜ 크기λ₯Ό 2배둜 늘리면, μ΅œμ•…μ˜ 경우 λΉ„μš©μ΄ 4λ°° μ¦κ°€ν•©λ‹ˆλ‹€.

κ·ΈλŸΌμ—λ„ λΆˆκ΅¬ν•˜κ³  μ‚½μž… 정렬은 배열이 μ–΄λ–»κ²Œ μž‘λ™ν•˜λŠ”μ§€ μ€‘μš”ν•œ 톡찰을 μ œκ³΅ν•©λ‹ˆλ‹€.

이 κ°„λ‹¨ν•œ μ•Œκ³ λ¦¬μ¦˜μ€ 인덱슀λ₯Ό μ‚¬μš©ν•΄ μ›μ†Œλ ˆ 직접 μ ‘κ·Όν•  수 μžˆμ–΄μ•Ό ν•˜λ©°, μƒˆ μ›μ†Œλ₯Ό μ‚½μž…ν•  λ•Œ 값을 κ΅ν™˜ν•  수 μžˆμ–΄μ•Ό ν•˜λ©°, λͺ¨λ“  μ›μ†Œλ₯Ό 반볡(iteration)ν•  수 μžˆμ–΄μ•Ό ν•œλ‹€λŠ” λ°°μ—΄μ˜ μ—¬λŸ¬ νŠΉμ„±μ„ λ³΄μ—¬μ€λ‹ˆλ‹€.