Data Structures HW5

(1) Brief explanation of the problem
The goal of this problem is that the code is implemented by two methods which are insertion sort and heapsort. So in the process of code implementation, we should understand their principle and differences between them.

(2) Your view as to how it ties in with what we covered in class
-Heapsort is based on heap. Heap is a data structure which is made to find the maximum or minimum value node over nodes. And heap is almost shape of array. So we can use this usefully. So in order to make heapsort, first we build a binary max heap of N elements then perform N delete max operations. The reason why we use delete max operation is that we want the elements in the more increasing sorted order, we can change the ordering property so that the parent has a larger key than children.

<중 략>

for(i=n-1;i>0;i--){ //heapsort 하는 함수
swap(&S[0],&S[i]);
//두개의위치를바꿔줌으로써 sorting이 됨,즉 배열 앞쪽으로 갈수록 수가 큰것이 아니라 수가 작아짐
percdown(S,0,i);
}
printf("After HeapSort : \n{");
for(k=0;k<14;k++){
printf("%d ",S[k]);
}
printf("}\n");
//heapsort된 값들을 출력
}
//root에 젤 큰수를 넣는 함수, 즉 배열 맨 앞쪽에 젤 큰수가 들어 간다.