[전자전기프로그래밍] 정렬(sorting)

목차

1. Introduction
2. Problem Statement
3. Implementation
4. Result
5. Conclusion & Evaluation
6. Source Code (with suitable comments)

본문내용

1. Introduction
이번 실습에서는 정렬에 대해서 배운다. 가장 간단하게 구현이 가능한 Bubble Sorting과 좀 더 효율적인 정렬 방법인 Heap Sorting을 구현해보고 이 두 가지 알고리즘의 효율성을 비교해본다.

2. Problem Statement
① Describe what is the problem.
· adjust
Heap Sorting을 수행하기 위해 binary tree를 만든다.
· heapSort
Heap Sorting을 수행한다.
· bubbleSort
Bubble Sorting을 수행한다.
② Describe how do you solve the problem.
· adjust
Binary tree를 만들어야 한다. Max heap이어야 한다. 즉, 부모 node의 값이 자식 node의 값보다 커야 한다. 즉, 자식 node가 부모 node보다 크다면 둘을 맞바꿔야 한다.
· heapSort
adjust함수를 통해 max heap을 만들었으므로 tree의 맨 위의 값이 제일 크다. 이 값을 맨 뒤로 보내고, 이 값을 제외한 tree를 가지고 또 같은 방법을 사용해서 그 다음 큰 수를 제일 큰 수 바로 전으로 보낸다. 이런 방식으로 계속 반복한다.
· bubbleSort
만약 n개의 데이터라고 하자. 그렇다면 첫 번째와 두 번째를 비교해서 큰 것을 뒤로 보내고, 두 번째와 세 번째를 비교해서 큰 것을 뒤로 보내고, 이런 방식으로 반복해서 마지막에 n-1 번째와 n 번째를 비교해서 큰 값을 뒤로 보낸다. 즉, 제일 큰 값이 맨 뒤에 가있다. 이 값을 제외하고 같은 방법을 수행한다. 그렇다면 결국에 오름차순으로 정렬이 된다.

참고 자료

없음