[코딩테스트 합격자 되기 스터디] 8주차 - 정렬

✅ 정렬의 의미

• 데이터를 특정 기준에 따라 순서대로 배치
  • 예시) 오름차순 (작은 값에서 큰 값으로), 내림차순 (큰 값부터 작은 값으로)

✅ 코테에서 정렬이 필요한 이유

• 정렬된 상태에서 동작하는 알고리즘을 사용해야 하는 경우
  • 이진탐색
  • 병합정렬의 병합

 

✅ 삽입 정렬

• 왼쪽은 정렬된 영역, 오른쪽은 비 정렬된 영역으로 나뉨
• 정렬된 영역이 점점 확장되어 비 정렬된 영역이 없어지는 정렬 방법 
• 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬
• 최악의 경우 - 역정렬된 경우. 시간 복잡도 O(N²) 
• 최선의 경우 - 처음부터 정렬된 경우. 시간 복잡도 O(N)   

• 삽입정렬 과정

✅ 병합 정렬

• 리스트를 반으로 나누어 각각 정렬한 뒤 합치는 방식
• 각 부분 리스트를 재귀적으로 정렬. 최종적으로 정렬된 두 리스트를 합쳐서 전체 리스트 정렬
• 시간 복잡도 O(NlogN)
  • 나누는 횟수 logN, 이를 합치는 횟수 NlogN (N개를 병합하는 과정을 logN번 진행)

 

✅ 힙 정렬

• 힙 : 특정 규칙이 있는 이진 트리
  • 부모 노드가 자식노드보다 항상 크면 최대힙, 항상 작으면 최소힙

 

✅ 우선순위 큐

• 들어온 순서와 상관없이 우선순위가 높은 원소가 먼저 나가는 큐
• 고려할 점
  • 원소가 계속 들어온 상황에서 정렬 상태를 유지해야 함
    • 기존 대부분 정렬방법은 O(NlogN)
    • 힙정렬을 사용할 경우 삽입/삭제 시 O(logN) 보장 -> 우선순위 큐는 힙 사용

 

✅ 각 정렬 알고리즘 비교

---

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

 

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]