[알고리즘]Selection Sort,Insertion Sort,Merge Sort,quick Sort, Quick Sort 종합분석

목차

1)Source code (5개 sorting program + random# 생성 progrlam + 전 과정 실행 main pgm)
2)제일 작은 size file 첫 10개 데이터 출력 및 그 10개에 대한 a~e 각각의 sorting 결과
3)알고리즘 별 데이터 갯수에 따른 실행시간 (표 및 그래프) - 첨부 file 참조
4)Discussion

본문내용

1)Source code (5개 sorting program + random# 생성 progrlam + 전 과정 실행 main pgm)
1-1)Selection Sort
void selectionsort(int n, int S[]) //선택 정렬
{
int temp;
int i,j, smallest;
for(i=0;i<=n-1; i++)
{
smallest = i; //i에 smallest 저장.
for(j=i+1; j<=n-1; j++){
if(S[j] < S[smallest])
smallest =j;
}
//S[j]가 S[i]보다 작다고 판정될때마다 교환정렬.
temp = S[i];
S[i]=S[smallest];
S[smallest]=temp;
}
}
*Documentation
선택정렬은 정렬순서상 가장 앞서는 것을 선택해서 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈자리에 가져다 놓는다. 즉, 빈자리를 활용하는 과정에서 비롯된 교환과정을 거친다.
1-2)Insertion Sort
void insertionsort(int n, int S[])
{
int i,j;
int x;
int temp;
for(i=1;i<=n;i++)
{
x=S[i];
j=i-1;
while(j>0 && S[j] >x)
{
S[j+1]=S[j];
j--;
}
S[j+1]=x;
}
}
*Documentation
x를 I번째 슬롯에 있는 키라고 하면 이 함수는 x와 (i-1)번째 슬롯에 있는 키, (i-2)번째 슬롯에 있는 키, ..., 등등 차례로 비교하되, x보다 작은 키를 찾을 때까지 비교한다. j를 키가 위치한 슬롯이라고 한다면 (j+1)번째 슬롯에서 (i-1)번째 슬롯에 있는 키들을 (j+2)번째 슬롯에서 I번째 슬롯으로 옮기고 (j+1)번째 슬롯에 x를 삽입한다. 이 과정을 i=2에서부터 i=n까지 반복한다.
1-3)Merge Sort
void Merge(int *S, int low, int mid, int high)

참고자료

· 없음