[자료구조/정렬알고리즘] 힙 정렬(Heap Sort) C언어

1. 힙정렬(Heap Sort)

 

 

2. 소스 코드

#include
int BuildHeap(int A[],int n);
int Heapify(int A[], int k, int n);
int HeapSort(int A[], int n);
void swap(int *a, int *b);
int YONG = 0;
int count = 0;
int main()
{
int A[10000];
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
HeapSort(A,n);
printf("%d",count);

}
int BuildHeap(int A[],int n){
for(int i=n/2;i>0;i--)
{
Heapify(A,i,n);
}
}

int Heapify(int A[], int k, int n){
int left, right;
int MAX;
left = 2*k;
right = (2*k)+1;
if(right<=n)
{
if(A[left]>A[right])
{
MAX = left;
}
else
{
MAX = right;
}
}
else if(left<=n)
{
MAX = left;
}
else{
return 0;
}
if(A[MAX]>A[k])
{
swap(&A[MAX],&A[k]);
if(YONG==1)
{
count++;
}
Heapify(A,MAX,n);
}
}

int HeapSort(int A[], int n){
BuildHeap(A,n);
YONG = 1;
for(int i=n;i>1;i--)
{
swap(&A[1],&A[i]);
Heapify(A,1,i-1);
}
}

void swap(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}

 

 

2-(1) 선언

#include<stdio.h>
int BuildHeap(int A[],int n);
int Heapify(int A[], int k, int n);
int HeapSort(int A[], int n);
void swap(int *a, int *b);
int YONG = 0;
int count = 0;

 

2-(2) Main 문

int main() 
{ 
    int A[10000]; 
    int n; 
    scanf("%d",&n); 
    for(int i=1;i<=n;i++) scanf("%d",&A[i]); 
    HeapSort(A,n); 
    printf("%d",count); 
} 

 

 

2-(3) HeapSort 함수

int HeapSort(int A[], int n){ 
    BuildHeap(A,n); 
    YONG = 1; 
    for(int i=n;i>1;i--) 
    { 
        swap(&A[1],&A[i]); 
        Heapify(A,1,i-1); 
    } 
} 

 

2-(4) BuildHeap 함수

int BuildHeap(int A[],int n){
    for(int i=n/2;i>0;i--)
    {
        Heapify(A,i,n);
    }
}

 

2-(5) Heapify 함수

int Heapify(int A[], int k, int n){
    int left, right;
    int MAX;
    left = 2*k;
    right = (2*k)+1;
    if(right<=n)
    {
        if(A[left]>A[right])
        {
            MAX = left;
        }
        else
        {
            MAX = right;
        }
    }
    else if(left<=n)
    {
        MAX = left;
    }
    else{
        return 0;
    }
    if(A[MAX]>A[k])
    {
        swap(&A[MAX],&A[k]);
        if(YONG==1)
        {
            count++;
        }
        Heapify(A,MAX,n);
    }
}