[알고리즘] sort

소개글

[알고리즘] sort에 대한 보고서 자료입니다.

목차

1. 소팅결과

2. 분석

3. 소스코드

본문내용

ective memory deallocate! It is important for this program that the memory is done usefully */
free(R);
}
/******** QUICK SORTING *********/
void Quick_sort(int *A, int p, int r){
int q;
if(p q = Partition(A, p, r);
Quick_sort(A, p, q);
Quick_sort(A, q+1, r);
}
}
int Partition(int *A, int p, int r){
int x=A[p];
int i=p-1;
int j=r+1;
while(1){
do{
j--;
}while(A[j] > x);
do{
i++;
}while(A[i] < x);
if(i SWAP(&A[i], &A[j]);
else return j;
}
}
/******** HEAP SORTING *********/
void Heap_sort(int *A, int line){
int heap_size = line, i;
for(i=heap_size/2 ; i>=1; i--)
Heapify(A, i, heap_size);
for(i=line; i>=2; i--){
SWAP(&A[1], &A[i]);
heap_size--;
Heapify(A, 1, heap_size);
}
}
void Heapify(int *A, int i, int heap_size){
int largest = i;
int left = 2*i, right = 2*i+1;
if(left <= heap_size){
if(A[left] > A[i])
largest = left;
else
largest = i;
}
if(right <= heap_size){
if(A[right] > A[largest])
largest = right;
}
if(largest != i){
SWAP(&A[i], &A[largest]);
Heapify(A, largest, heap_size);
}
}
/******** COUNTING SORTING *********/
void Counting_sort(int *A, int line){
int i, j;
int *B, *C;
if((B = (int *)malloc(sizeof(int)*(line+1))) == NULL){
fprintf(stderr, "Memory allocating error\n");
exit (0);
}
if((C = (int *)malloc(sizeof(int)*(MAX+1))) == NULL){
fprintf(stderr, "Memory allocating error\n");
exit (0);
}
for(i=0; i<=MAX; i++)
C[i]=0;
for(j=1; j<=line; j++)
C[A[j]]++;
for(i=1; i<=MAX; i++)
C[i] += C[i-1];
for(j=line; j>=1; j--){
B[C[A[j]]] = A[j];
C[A[j]]--;
}
for(i=1; i<=line; i++){
A[i] = B[i];
}
free(B);
free(C);
}
int readMakeArray(char *input_name, int *A){
int line=1, temp;
FILE *fp;
if((fp=fopen(input_name, "r")) == NULL){
fprintf(stderr, "File opening error");
exit (0);
}
while(!feof(fp)){
if(fscanf(fp, "%d", &temp) == EOF) break;
A[line] = temp;
line++;
}
fclose(fp);
return (line-1); /* Total line is line-1 because array index is started at 1. */
}
void writeOutfile(char *output_name, int *A, int line){
int j;
FILE *fp;
if((fp=fopen(output_name, "w")) == NULL){
fprintf(stderr, "File opening error");
exit (0);
}
for(j=1; j<=line; j++){
fprintf(fp, "%d\n", A[j]);
}
fclose(fp);
}
void SWAP(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}

키워드

알고리즘,   sort,   quick,   merge,   count,   소스코드