heapsort, insertionsort, quicksort, mergesort

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct HeapElementType
{
 int value;
} HeapNode;
typedef struct ArrayHeapType
{
 int maxElementCount;  // 최대 노드 개수
 int currentElementCount; // 현재 노드 개수
 HeapNode *pElement;
} ArrayMaxHeap;

void printArr(int value[]);
void heapSort(ArrayMaxHeap *value, int count);
void MaxHeapify(ArrayMaxHeap *value, int i);
void BuildMaxHeap(ArrayMaxHeap *value);
void printArr2(ArrayMaxHeap *value);
void insertionSort(int value[], int count);
void quickSort(int value[], int p, int r);
int partition(int value[], int p, int r);
void MergeSort(int Arr[], int p, int r);
void Merge(int Arr[], int p, int q, int r);
int partitionQuickSort(int value[], int start, int end);

int n;

int main()
{
 int i;
 FILE *fp; //파일포인터 선언
 fp = fopen("input2.txt","r");
 int *p, *p2, *p3; //insertion sort 위한 배열 
 int *pTemp;

 clock_t start, finish;//시작, 종료시간

 if(!fp)  //파일포인터가 널값이라면
 {
  printf("can't read the file\n");
  exit(0); //프로그램종료
 }

 fscanf(fp, "%d", &n); //파일의 첫번째 라인 숫자 읽어옴

 p = (int*)malloc(sizeof(int)*n); //읽어와서 n에 입력된 수만큼 동적할당을 한다. 
 p2 = (int*)malloc(sizeof(int)*n); //읽어와서 n에 입력된 수만큼 동적할당을 한다.
 p3 = (int*)malloc(sizeof(int)*n); //읽어와서 n에 입력된 수만큼 동적할당을 한다.
 ArrayMaxHeap *p4 = (ArrayMaxHeap *)malloc(sizeof(ArrayMaxHeap));
 ArrayMaxHeap *pTemp2 = (ArrayMaxHeap *)malloc(sizeof(ArrayMaxHeap));
 
 pTemp = (int*)malloc(sizeof(int)*n);
 printf("counter = %d\n", n);

 p4->maxElementCount = n;
 p4->currentElementCount = n;
 p4->pElement = (HeapNode *)malloc(sizeof(HeapNode) * (n));
 pTemp2->maxElementCount = n;
 pTemp2->currentElementCount = n;
 pTemp2->pElement = (HeapNode *)malloc(sizeof(HeapNode) * (n));
 memset(p4->pElement, 0, sizeof(HeapNode) * (n));
 memset(pTemp2->pElement, 0, sizeof(HeapNode) * (n));

 for(i=0; i<n; i++)//txt파일의 값을 p, p2 배열에 저장한다.
 {  
  fscanf(fp, "%d", &p[i]);
  p2[i] = p[i];
  p3[i] = p[i];
  p4->pElement[i].value = p[i];
 }

 
 fclose(fp); // 파일포인터 해제

 start = clock();
 insertionSort(p, n); //insertion sort 수행
 finish = clock();
 printArr(p);// insertion sort 된 p 출력
 printf("\n1.insertion sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC);  
 start = clock();
 insertionSort(p, n);
 finish = clock();
 printf("\n2.insertion sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC); 
 for(i = 0;i<n;i++){
  pTemp[n-i] = p[i];
 }
 start = clock();
 insertionSort(pTemp, n);
 finish = clock();
 printf("\n3.insertion sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC); 

 
 start = clock();
 quickSort(p2, 0, n-1); // quick sort 수행
 finish = clock(); 
 printArr(p2); // quick sort 된 p2 출력
 printf("\n1.quick sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC);  
 start = clock();
 quickSort(p2, 0, n-1);
 finish = clock();
 printf("\n2.quick sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC); 
 for(i = 0;i<n;i++){
  pTemp[n-i] = p2[i];
 }
 start = clock();
 quickSort(pTemp, 0, n-1);
 finish = clock();
 printf("\n3.quick sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC); 
 
 
 
 start = clock();
 MergeSort(p, 0, n-1); // quick sort 수행
 finish = clock(); 
 printArr(p); // quick sort 된 p2 출력
 printf("\n1.merge sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC);  
 start = clock();
 MergeSort(p, 0, n-1);
 finish = clock();
 printf("\n2.merge sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC); 
 for(i = 0;i<n;i++){
  pTemp[n-i] = p3[i];
 }
 start = clock();
 MergeSort(pTemp, 0, n-1);
 finish = clock();
 printf("\n3.merge sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC); 

 

 start = clock();
 heapSort(p4, n); // quick sort 수행
 finish = clock(); 
 printArr2(p4); // quick sort 된 p2 출력
 printf("\n1.heap sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC);  
 start = clock();
 heapSort(p4, n);
 finish = clock();
 printf("\n2.heap sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC); 
 for(i = 0;i<n;i++){
  pTemp2->pElement[n-i].value = p4->pElement[i].value;
 }
 start = clock();
 heapSort(pTemp2, n);
 finish = clock();
 printf("\n3.heap sort duration is %f\n", (double)(finish-start)/CLOCKS_PER_SEC);

 /*
 free(p); // free
 free(p2); // free
 free(p3);
 free(p4);
 free(pTemp);
 free(pTemp2);
 */
}

void insertionSort(int value[], int count)
{
 int i = 0, j = 0;
 int temp = 0;

 for(i=0; i<count; i++){
  temp = value[i]; // 삽입 될 값 임시 저장

  for(j=i-1; j>=0; j--){
   if(value[j] > temp){
    value[j+1] = value[j]; // 한 칸씩 우측으로 밀음
   }else
    break;
  }
  value[j+1] = temp;//밀린 자리에 삽입될 값 저장
 }
}

void quickSort(int value[], int p, int r){
 int q;
 if(p < r){
  q = partitionQuickSort(value, p, r); // pivot을 가져옴
  quickSort(value, p, q-1); // recursive 로 좌측
  quickSort(value, q+1, r); // recursive 로 우측
 }
}
/*
int partition(int value[], int p, int r){ // pivot 위치 리턴
 int x = value[r]; // pivot
 int i = p-1;
 int j, temp = 0;
 for(j=p; j<r; j++){ //right의 좌측에서
  if(value[j] <= x){ // pivot보다 작으면
   i = i + 1; //index증가 후 값 교환  
   temp = value[i];
   value[i] = value[j];
   value[j] = temp;
  }
 }
 temp = value[i+1];//pivot 값 교환 후
 value[i+1] = value[r];
 value[r] = temp;
 return i+1;//pivot 인덱스 리턴
}
*/
int partitionQuickSort(int value[], int start, int end)
{
 int pivot = 0;
 int temp = 0, left = 0, right = 0;
 left = start;
 right = end;
 pivot = end;

 while(left < right) {
  while((value[left] < value[pivot]) && (left < right)) {
   left++;
  }
  while((value[right] >= value[pivot]) && (left < right)) {
   right--;
  }

  if (left < right) {
   temp = value[left];
   value[left] = value[right];
   value[right] = temp;

   //printf("start-[%d],end-[%d],pivot-[%d],in-loop,", start, end, value[pivot]);
   //printArray(value, end - start + 1);
  }
 }
 temp = value[pivot];
 value[pivot] = value[right];
 value[right] = temp;

 //printf("start-[%d],end-[%d],pivot-[%d],out-loop,", start, end, value[right]);
 //printArray(value, end - start + 1);

 return right;
}

void printArr(int value[]){
 printf("\nfront 50\n");
 int i;

 for(i=0; i< 50; i++){
  printf("%d ", value[i]); 
 }

 printf("\nrear 50\n");
 for(i=n-50; i<n; i++){
  printf("%d ", value[i]);
 }
}

void MergeSort(int Arr[], int p, int r){
 int q = 0;
 if(p < r){
  q = (p+r)/2;
  MergeSort(Arr,  p, q); // 왼쪽
  MergeSort(Arr,  q+1, r); // 오른쪽
  Merge(Arr, p, q, r); // 하나씩 나눠진 값들을 하나로 합쳐줌.
 }
}

void Merge(int Arr[], int p, int q, int r){
 int n1 = q - p;
 int n2 = r - q - 1;
 int *L = NULL;
 int *R = NULL;
 L = (int*)malloc(sizeof(int)*(n1+2));
 R = (int*)malloc(sizeof(int)*(n2+2));
 //let L[1 ~ n1+1], R[1 ~ n2+1] be new arrays;
 int i, j;
 for(i=0; i<=n1; i++)
  L[i] = Arr[p+i];

 for(j=0; j<=n2; j++)
  R[j] = Arr[q+j+1];
 
  
 L[n1+1] = 100000;
 R[n2+1] = 100000;

 i = 0;
 j = 0;
 int k = 0;
 for(k=p ; k<=r ; k++){  
  if(L[i]<=R[j]){ 
   Arr[k] = L[i];
   i = i+1;
  }else{
   Arr[k] = R[j];
   j = j+1;
  }

  
 }
 free(L);
 free(R);
}

// 힙 정렬.
void heapSort(ArrayMaxHeap *value, int count)
{
 BuildMaxHeap(value); //maxheap 생성
 int temp = 0;
 for(int i=value->currentElementCount; i >= 1; i--){ //heap의 길이부터 1까지
  //0의 값과 i의 값을 exchange - > 마지막으로 옮김
  temp = value->pElement[i].value;
  value->pElement[i].value = value->pElement[0].value;
  value->pElement[0].value = temp;
  value->maxElementCount -=1; // 최대 노드 갯수를 감소한다.
  
  MaxHeapify(value, 0); // maxheapify
 }

}

void MaxHeapify(ArrayMaxHeap *value,int  i){
 int l = 2*i; // 왼쪽 자식
 int r = 2*i+1; // 오른쪽 자식
 int temp =0;
 int largest = 0;

 if((l<=value->maxElementCount) && (value->pElement[l].value > value->pElement[i].value)){ // 왼쪽자식이 크기에 벗어나지 않고 root보다 크면
  largest = l; // 왼쪽 자식이 largest가 된다
 }else{
  largest = i; // 아니면 현재 root가 largest가 된다
 }

 if((r<=value->maxElementCount) && (value->pElement[r].value > value->pElement[largest].value)){ // 오른쪽 자식이 크기에 벗어나지 않고 largest보다 크면
  largest = r; // 오른쪽 자식이 largest가 된다.
 }

 if(largest != i){ // root가 largest가 아닐 경우에는
  //largest의 값과 root의 값을 변경한다.
  temp = value->pElement[largest].value;
  value->pElement[largest].value = value->pElement[i].value;
  value->pElement[i].value = temp;
  //largest값으로 maxheapify 다시 수행
  MaxHeapify(value, largest);
 }
}

void BuildMaxHeap(ArrayMaxHeap *value){ // max heap 생성
 value->maxElementCount = value->currentElementCount; // max값에 현재노드 갯수를 대입
 for(int i=(value->currentElementCount/2); i>0; i--){
  //현재 노드 갯수의 반 부터 하나씩 감소하며 heap 수행
  MaxHeapify(value, i);
 }
}

void printArr2(ArrayMaxHeap *value){
 printf("\nfront 50\n");
 int i;

 for(i=1; i<= 50; i++){
  printf("%d ", value->pElement[i].value); 
 }

 printf("\nrear 50\n");
 for(i=n-50; i<n; i++){
  printf("%d ", value->pElement[i].value);
 }
}