병합정렬, 힙정렬, 도수정렬

<병합정렬>

• 배열을 앞부분과 뒷부분으로 나누어 정렬하고 다시 병합하는 정렬 알고리즘
• 시작 복잡도 = O(nlogn) / 배열 병합의 시간 복잡도(O(n)), 병합 정렬의 시간 복잡도 (O(logn))
• 안정적인 정렬

그림 이해(출처 위키백과)

https://commons.wikimedia.org/wiki/File:Merge-sort-example-300px.gif#/media/파일:Merge-sort-example-300px.gif

File:Merge-sort-example-300px.gif - Wikimedia Commons

코드: 깃 허브 chap6/실습/SixToThirteen

<힙정렬>

• 힙(heap)을 사용한 정렬 알고리즘
• 힙: 부모값이 자식 값보다 항상 큰 조건을 만족하는 완전이진트리(부분순서트리)
• 선택정렬을 활용한 알고리즘이다.
• 시간 복잡도: O(nlogn)

https://commons.wikimedia.org/wiki/File:Heapsort-example.gif#/media/파일:Heapsort-example.gif

File:Heapsort-example.gif - Wikimedia Commons

코드: 깃 허브 chap6/실습/SixToSeventeen

<도수정렬>

• 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 정렬 알고리즘
• 1단계: 도수분포표 만들기
• 2단계: 누적도수분포표 만들기
• 3단계: 목표 배열 만들기
• 4단계: 배열 복사하기
• 시간 복잡도 : O(n)
• 정해진 범위내에서 사용/ 빈 배열이 많아질 수 있음
• 안정적이지 않음

3번째 표에서 요소값-1에 해당하는 인덱스를 찾아가면됨

코드: 깃 허브 chap6/실습/SixToEighteen

 https://github.com/lhj0954/Algorithm-Doit.git