💻 [코테08] 13장 정렬

13장. 정렬

13-1. 정렬 개념

• 사용자가 정의한 순서로 데이터를 나열하는 것

1) 정렬이 필요한 이유

• 원하는 데이터를 쉽게 찾는 것 가능

2) 삽입 정렬

• 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역으로 구분
• 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치에 넣으며 정렬
• 시간 복잡도 : 최악인 경우 O(N^2), 최선인 경우 O(N)

3) 병합 정렬

• 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬
• 시간 복잡도 : 최악인 경우 O(NlogN), 최선인 경우 O(NlogN)

4) 힙 정렬

• 힙 자료구조를 사용한 정렬
• 힙 : 특정 규칙이 있는 이진 트리(최대힙, 최소힙)
• 시간 복잡도 : 최악인 경우 O(NlogN), 최선인 경우 O(NlogN)

5) 우선순위 큐

• 우선순위가 높은 데이터부터 먼저 처리하는 큐
• 힙으로 구현

6) 위상 정렬

• 일의 순서가 있는 작업을 순서에 맞춰 정렬하는 알고리즘
• 진입차수 : 자신을 향한 화살표의 개수
• 시간 복잡도 : 최악인 경우 O(V+E), 최선인 경우 O(V+E)

7) 계수 정렬

• 데이터에 의존하는 정렬 방식
• 데이터의 빈도수로 정렬
• 한계점 : 저장할 값의 전체 범위 내에 값이 듬성 듬성 있거나 음수가 있는 경우 사용하기 곤란
• 시간 복잡도 : 최악인 경우 O(N+K), 최선인 경우 O(N+K)