220420_정렬 알고리즘 정리

[정렬 알고리즘]
* 배울 내용
- 퀵 정렬, 힙 정렬, 합병(병합) 정렬
- 이외에도 많은 정렬 알고리즘이 있지만 가장 중요하고
어려운 내용들만 배울 예정.
- 이외에도 다른 정렬 알고리즘들도 공부해놓으면 좋음.

* 정렬의 사용처
- 대표적으로 길 찾기에 가장 많이 사용됨.

* 대부분 정렬은 재귀를 통해 구현됨.

* 힙정렬은 우리가 지난 시간에 배웠던 이진 트리를 기반으로 정렬하므로
힙정렬부터 할 예정.

* 오늘의 목표: 셋 다 만들고 성능 테스트

* 시간복잡도: 알고리즘 성능을 수치화.
빅 오 표기법: 정렬 알고리즘이 최악의 상황에 얼마나 걸리는지를 수치화.

 

<힙 정렬>

* 힙정렬은 최대힙과 최소힙이 있다.
- 최대힙으로 정렬하면 내림차순, 최소힙으로 정렬하면 오름차순으로 정렬됨.
- 최대힙 -> 높은 수를 위로
- 최소힙 - > 낮은 수를 위로

* 정렬 기준은 이전에 했던 방법인,
main에서 선언한 함수를 함수 포인터로 넘겨 대소여부를 비교하는 방식으로 구현함.
(main의 비교함수가 true를 반환하면 자리바꿈, 아니면 놔둠)
- 이 방식으로 했을 때의 장점: 포인터나 클래스 등 대소판별이 어려운 객체들도
함수에 판별기준을 추가하여 대소판별이 가능해진다.



* 실제 값의 저장은 배열에 한다.
- 인덱스 번호를 통해 이진 트리에서의 위치와, 부모 노드의 번호, 자식 노드의 번호
모두 구할 수 있다.

- 인덱스로 부모 노드 찾기: (index - 1) / 2
- 인덱스로 자식 노드 찾기: (index) * 2    + 1(왼쪽자식) or +2(오른쪽자식)

* 나중에 배울, 우선순위 큐와 동작 방식이 유사하다.


<최대 힙 알고리즘 순서>
[Push]
1.  이진 트리의 왼쪽 제일 끝부터 추가한다. 
- 루트노드(인덱스 0) -> 루트노드 왼쪽(1) -> 루트노드 오른쪽(2) 
-> 왼쪽 자식노드의 왼쪽(3) -> 왼쪽 자식노드의 오른쪽(4)
-> 오른쪽 자식노드의 왼쪽 -> 오른쪽 자식노드의 오른쪽 -> ...

2. 값이 추가되면, 같은 부모를 가진 자식노드와 크기를 비교한다.


3. 둘중 큰 자식노드와 부모노드를 비교하여 부모노드보다 크면 해당 서로 스왑한다.
3-1. 스왑이 일어났고, 위에 또 부모노드가 존재하면 해당 노드에서도 3번을 반복한다.(루트노드까지)
- 자식간 비교 -> 큰 값과 부모노드와 비교 -> 자식이 더 큰 값을 가지면 부모노드와 스왑

[Pop]
1. 루트노드의 값을 뺀다.

2. 제일 끝에 있는 값을 루트로 올린다.

3. 루트 노드의 두 개의 자식노드 중 큰 값과, 루트 노드를 비교한다.
5-1. 둘 중 큰 수를 루트노드로 올린다.(자리를 바꿔준다.)
5-2. 자리 바꿈이 일어났으면 하위 노드도 4 ~ 5를 반복한다.

4. 1 ~ 3을 반복한다.


* 최소 힙 정렬은 최대 힙의 반대로 해 주면 된다.




* 제일 끝에 있는걸 
*
* 장점: 절반씩 잘라내므로 속도가 O(log2)

https://hyrule.tistory.com/61

220420_정렬_힙 정렬(Heap Sort) 처리 과정

https://hyrule.tistory.com/62

220420_정렬_힙 정렬(Heap Sort) 구현

 

 

 

 

<퀵 정렬 >
* 비대칭 정렬
* 최선의 경우에는 가장 빠른 성능을 가지지만
* 최악의 경우에는 매우 느리다.
* 과정 요약
7 9 5 1 3 6 4
Pivot(중심점)을 하나 정함 -> (일반적으로 맨 앞 자리)7
Pivot보다 작은 건 왼쪽, Pivot보다 큰 건 오른쪽

Pivot: 7
5 1 3 6 4 7 9

* Pivot 7 기준 왼쪽 배열부터 정렬(1, 3, 4, 5, 6만 놓고 정렬)
다시 Pivot 설정 -> 5(맨 앞자리)
1 3 4 5 6 7 9

다시 Pivot 설정 -> 1
정렬 필요 없음

다시 Pivot 설정 -> 3
정렬 필요 없음 

다시 Pivot 설정 -> 4
정렬 필요 없음

다시 Pivot 설정 -> 5
정렬 필요 없음

* 7 기준 왼쪽 배열 왼쪽부터 정렬 끝. 오른쪽부터 정렬 시작.
Pivot: 6
정렬되어 있음.


* 7 기준 오른쪽 배열 정렬 시작
9밖에 없음 -> 정렬 끝.

https://hyrule.tistory.com/63

220420_정렬_퀵 정렬(Quick Sort) 이론

https://hyrule.tistory.com/64

220420_정렬_퀵 정렬(Quick Sort) 구현

 

 

 

 

< 분할 정렬 / 합병 정렬 >

* 이 정렬방식은 속도가 빠른 대신, 공간이 두 배 필요하다.
* 먼저 분할부터 한 후, 다시 병합하면서 정렬하는 과정을 가진다.
* 이 때, 정렬된 데이터를 복사본에 저장하기 때문에 새 공간이 필요한 것이다.
* 분할-정복 알고리즘
* 오름차순 정렬 예시
8 3 5 9 1 6 7

8 3 5 9 1 6 7

8 3 5 9 1 6 7

8 3 5 9 1 6 7

3 8 5 9 1 6 7
↑ ↑
* 3 5 비교 -> 3이 더 작으므로 3을 배열에 등록하고
포인터를 이동
3

3 8 5 9 1 6 7
  ↑ ↑
* 8 5 비교 -> 5가 더 작으므로 5를 배열에 등록하고
포인터를 이동
3 5

3 8 5 9 1 6 7
  ↑   ↑
* 8 9 비교 -> 8이 더 작으므로 8을 배열에 등록하고
포인터를 이동
3 5 8 

* 마지막 포인터를 등록
3 5 8 9
 

* 1 6 / 7도 같은 순서로 비교해줌 -> 1 6 7


3 5 8 9 1 6 7

* 3 1 비교: 스왑 -> 1 5 8 9 3 6 7
- 스왑이 일어났으므로 바로 통과
* 5 3 비교: 스왑 -> 1 3 8 9 5 6 7
- 스왑이 일어났으므로 마찬가지로 통과.

 

https://hyrule.tistory.com/65

220420_정렬_병합정렬(Merge Sort) 알고리즘

 

https://hyrule.tistory.com/66

220420_정렬_병합 정렬(Merge Sort) 구현