자료구조 Shellsort Mergesort Heapsort Quicksort

목차

(1) Program code for 6 algorithms
(2) Sorted output for all 6 algorithms when inputs are :
(3) CPU-time for all
(4) your analysis on CPU-time comparison

본문내용

1번 문제는 6가지 Sort에 관한 Algorithm code를 프로그램하는 것이다. 하지만 웬만한 알고리즘은 교재와 인터넷에 있었기 때문에 큰 난관은 없이 프로그램할 수 있었다.

그래서 Algorithm에 대한 code만 단순하게 붙여넣기 보다는 이에 대한 약간의 주석과 약간의 특징을 첨부하여 code에 대한 이해도를 높이도록 하였다.

① Insertion sort
Source Code of InsertionSort

각각의 Element의 값을 각각 서로 비교하는 sorting방법으로 N개의 Element가 있다면 하나당 N번의 비교를 N번 해야 되므로 총 O()의 시간이 걸리게 된다.

② Shellsort using shell's original sequence
Source Code of Shellsort

Increment값을 총 개수의 반만큼의 크기부터 시작해서 듬성듬성 비교해서 sorting하고 Increment의 값을 계속 반으로 줄여서 점점 촘촘하게 sorting하는 방법으로 경우에 따라 sorting속도가 달라지고, worst case의 경우 O()까지 걸릴 수 있다.

③ Shellsort using Hibbard's sequence
Source Code of HibbardIncrement

HibbardIncrement함수는 Hibbardsort를 하기에 앞서, 첫 Increment의 값을 결정하기 위한 함수이다. 그래서 N개의 Element가 있다면 -1이 N보다 커지는 가장 첫 I를 구해서 -1을 리턴하여 N보다 작은 최대의 Increment를 구하게 되는 것이다.

참고자료

· 없음