πŸ–‹οΈ μžλ£Œκ΅¬μ‘°μ™€ μ•Œκ³ λ¦¬μ¦˜/μ•Œκ³ λ¦¬μ¦˜,자료ꡬ쑰

[μ •λ ¬] 특수 μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜(κ³„μˆ˜/기수/버킷)

OR15A 2023. 11. 21. 18:25
  • κ³„μˆ˜ μ •λ ¬, 기수 μ •λ ¬, 버킷 정렬은 각각 νŠΉμ •ν•œ μƒν™©μ—μ„œ 빛을 λ°œν•˜λŠ” μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜
  • 이듀 μ•Œκ³ λ¦¬μ¦˜μ˜ νš¨μœ¨μ„±μ€ λ°μ΄ν„°μ˜ νŠΉμ„±κ³Ό 뢄포에 크게 μ˜μ‘΄ν•¨

 

κ³„μˆ˜ μ •λ ¬ (Counting Sort)

νŠΉμˆ˜ν•œ μ‚¬μš© 상황:

  • μ •μˆ˜μ™€ μž‘μ€ λ²”μœ„:
    • κ³„μˆ˜ 정렬은 μ •μˆ˜ 데이터에 μ΅œμ ν™”. 특히 μ •μˆ˜ κ°’μ˜ λ²”μœ„κ°€ μ œν•œμ μΌ λ•Œ 맀우 효율적
  • λ™μΌν•œ κ°’μ˜ λΉˆλ²ˆν•œ 반볡:
    • λ™μΌν•œ 값이 데이터셋 내에 λΉˆλ²ˆν•˜κ²Œ λ°˜λ³΅λ˜λŠ” κ²½μš°μ—λ„ κ³„μˆ˜ 정렬이 유리
  • λ°μ΄ν„°μ˜ λ²”μœ„κ°€ μž‘κ³ , 데이터 양이 λ§Žμ€ 경우:
    • 예λ₯Ό λ“€μ–΄, μ μˆ˜λ‚˜ λ‚˜μ΄μ™€ 같이 νŠΉμ • λ²”μœ„ 내에 μžˆλŠ” μ •μˆ˜λ₯Ό μ •λ ¬ν•  λ•Œ 유용

 

 

기수 μ •λ ¬ (Radix Sort)

νŠΉμˆ˜ν•œ μ‚¬μš© 상황:

  • κΈ΄ μ •μˆ˜λ‚˜ λ¬Έμžμ—΄ μ •λ ¬:
    • κΈ΄ μ •μˆ˜λ‚˜ λ¬Έμžμ—΄κ³Ό 같은 데이터λ₯Ό μ •λ ¬ν•  λ•Œ 기수 정렬은 효과적 (μžλ¦Ώμˆ˜λ³„λ‘œ μ •λ ¬ν•˜κΈ° λ•Œλ¬Έ)
  • 비ꡐ 기반 μ •λ ¬μ˜ ν•œκ³„λ₯Ό λ„˜μ–΄μ„œλ €λŠ” 경우:
    • 큰 λ°μ΄ν„°μ…‹μ—μ„œ 비ꡐ 기반 정렬보닀 λΉ λ₯Ό 수 있으며, 특히 λ°μ΄ν„°μ˜ 크기가 κ³ λ₯΄κ²Œ λΆ„ν¬λ˜μ–΄ μžˆμ„ λ•Œ 효율적\

 

 

버킷 μ •λ ¬ (Bucket Sort)

νŠΉμˆ˜ν•œ μ‚¬μš© 상황:

  • κ· μΌν•˜κ²Œ λΆ„ν¬λœ 데이터:
    • 데이터가 κ· μΌν•˜κ²Œ λΆ„ν¬λ˜μ–΄ 있고, λ°μ΄ν„°μ…‹μ˜ λ²”μœ„κ°€ μ•Œλ €μ Έ μžˆμ„ λ•Œ 버킷 정렬은 맀우 효율적
  • 뢀동 μ†Œμˆ˜μ  숫자:
    • 버킷 정렬은 뢀동 μ†Œμˆ˜μ  숫자 같은 λΉ„μ •μˆ˜ 데이터에도 잘 μž‘λ™. (데이터λ₯Ό 버킷에 ν• λ‹Ήν•˜κ³  각 버킷을 κ°œλ³„μ μœΌλ‘œ μ •λ ¬ν•  수 있기 λ•Œλ¬Έ)
  • μΆ”κ°€ λ©”λͺ¨λ¦¬ μ‚¬μš© κ°€λŠ₯:
    • 버킷 정렬은 좔가적인 λ©”λͺ¨λ¦¬ 곡간을 ν•„μš”λ‘œ ν•˜λ©°, 이λ₯Ό 효율적으둜 μ‚¬μš©ν•  수 μžˆλŠ” μƒν™©μ—μ„œ 적합

 

 

 

참고자료 : γ€Œμ‰½κ²Œ λ°°μš°λŠ” μžλ£Œκ΅¬μ‘° with μžλ°”」