(출처 - 배지호 노션) 왜 정렬을 배워야 하는가

탐색알고리즘

1. 선형탐색
   1. O(n)
2. 이진탐색
   1. O(logN)

<aside> 📌 선형탐색보다 이진탐색이 효율이 좋기 때문에 시간복잡도를 생각해서라도 이진탐색을 진행할 수 있으면 이진탐색을 진행하는 것이 탐색에 효율적

</aside>

이진탐색

이진탐색

• 이진탐색을 위한 필수조건은, ‘정렬’되어 있는 데이터임
• 이진탐색은 왜할까?
  • 선형탐색보다 빠르고
  • 범위를 줄여나가면서 효율적인 탐색이 가능 (시간절약이 가장 큰 이유)

<aside> 📌 그래서 필요에 따라, 탐색을 진행할 때 정렬 후 이진탐색을 진행해야 할 경우가 생기기도 함

</aside>

정렬

• 이진탐색 진행 전, 정렬해야함
• 정렬 알고리즘을 선택하는게 중요한 요소가 될 수 있음
  • 시간복잡도를 줄이기 위해 이진탐색을 채택했고, 이를 위한 정렬을 하기 위해서는 무조건적으로 정렬도 성능이 좋아야함.
  • 가장 빠른 것은 계수정렬
    • 대신에 계수정렬은 원소들이 “정수"여야하고, 범위도 좁아야 하는 등 계수정렬은 특이한 경우에서만 사용 가능함
    • 시간복잡도는 $O(n+k)$이며, 공간복잡도는 계수를 위해서 $O(k)$가 필요함.
  • 혹은, $O(nlogN)$ 시간복잡도를 갖는 정렬이 필요함
    • 퀵정렬
      • 퀵정렬
      • 피봇을 선택하는 횟수 N, 두 구역으로 나뉘기 때문에 정렬은 logN만큼 수행
      • 하지만 퀵정렬의 최악은 O(N)임을 명심해야함. (피봇의 좌우대칭이 심각하게 맞지 않을 경우, 결국 선형탐색과 동일한 과정을 밟음)
    • 병합정렬
      • 병합정렬
      • 배열을 중간을 기준으로 나눠가면서 정렬수행, logN