성균관대 C프로그래밍-sorting

목차

1. 실습내용
2. 실습목적
3. 과제 해결방안
4. 코드분석
5. 실행결과
6. 결론
7. Appendix. 전체 코드

본문내용

1. 실습내용
여러 가지 정렬 알고리즘 중 다음 두 가지의 함수를 구현한다.
① Bubble Sorting 함수
바로 옆의 데이터와 비교하여 그 결과에 따라서 두 개의 값을 바꾼다. 즉, 첫 번째와 두 번째의 값을 비교하여 작은 값이 앞으로 오게 정렬하고 이 과정을 끝까지 반복하여 데이터를 정렬하는 함수이다.
② Heap Sorting 함수
정렬하고자 하는 리스트를 heap으로 만들고 그 다음에 heap에서 정렬을 수행한다.

2. 실습목적
이번 실습에서는 자료의 정렬에 관한 알고리즘을 구현한다. 여러 가지 알고리즘들 중 가장 간단하게 구현할 수 있는 버블 정렬(Bubble sorting)과 조금 더 효율적인 정렬 알고리즘인 힙 정렬(Heap sorting)에 관하여 알아보고 두 가지 알고리즘의 효율성을 비교한다.

<중 략>

★힙 정렬(Heap Sorting)의 수행 방법은 다음과 같다.
1. 정렬한 원소들을 입력하여 최대 힙을 구성한다.
2. 힙에 대하여 삭제 연산을 수행하여 얻은 원소의 마지막 자리에 배치한다.
3. 나머지 원소에 대하여 다시 최대 힙으로 재구성한다.
4. 원소의 개수만큼 2~3과정을 반복 수행한다.

※힙 정렬의 연산시간을 알아보겠다.
n개의 노드에 대해서 완전 이진 트리는 log₂(n+1)의 레벨을 가지므로 완전 이진트리를 힙으로 구성하는 평균 시간은 O(log n)이다.
n개의 노드에 대해서 n번의 힙 재구성 작업을 수행해야 한다.
예를 들어 정렬되지 않은 [69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 힙 정렬 방법으로 정렬하겠다.
1. 초기 상태: 정렬할 원소가 8개 이므로 노드가 8개인 완전 이진 트리를 만들고, 최대 힙(Max Heap)으로 구성한다.

참고 자료

없음