Cormen의 HeapSort 알고리즘 구현 C

Question

Cormen에서 제공하는 힙 정렬 알고리즘을 구현하려고합니다. 내 코드는 다음과 같습니다 :

#include<stdio.h> 
    #include<conio.h> 
    void max_heapify(int *,int); 
    void build_max_heap(int *,int); 
    void heapsort(int *,int); 
    void swap(int,int); 
    int heapsize; 
    int main() 
    { 
      int *arr,n,i; 
      printf("Enter no. of elements = "); 
      scanf("%d",&n); 
      arr=(int *)malloc(sizeof(int)*n); 
      for(i=0;i<n;i++) 
      { 
      printf("Enter array elements = "); 
      scanf("%d",&arr[i]); 
      } 
      //heapsize = n; 
      heapsort(arr,n); 
      printf("\nAfter heapsort \n"); 
      for(i=0;i<n;i++) 
      { 
       printf("%d ",arr[i]); 
      } 
     return 0; 
    } 
void heapsort(int *arr,int len) 
{ 
    int i; 
    build_max_heap(arr,len); 
    for(i= len-1;i>=1;i--) 
    { 
     swap(&arr[0],&arr[i]); 
     heapsize = heapsize -1; 
     max_heapify(arr,0); 
    } 
} 
void max_heapify(int *arr,int i) 
{ 
    int l=2*i,r=2*i+1,largest; 
    if(l<heapsize && arr[l]>arr[i]) 
     largest = l; 
    else 
     largest = i; 
    if(r<heapsize && arr[r]>arr[largest]) 
     largest = r; 

    if(largest != i) 
    { 
     swap(&arr[i],&arr[largest]); 
     max_heapify(arr,largest); 
    } 
    } 
void build_max_heap(int *arr,int len) 
{ 
    heapsize = len; 
    int i; 
    for(i =len/2;i>=0;i--) 
    { 
     max_heapify(arr,i); 
    } 
} 
void swap(int *a ,int *b) 
{ 
    int temp = *a; 
    *a= *b; 
    *b= temp; 
} 

내 코드에서 정확히 무엇이 잘못되었는지 알 수 없습니다. 배열이 정렬되지 않습니다. 사실 원래 배열이 인쇄됩니다. 내가 어디로 잘못 가고 있니?

Answer 1

1) 스왑을 수정하면 값으로 전달됩니다. 어떤 뜻이라면 스왑이 변경된 것입니다!

2) max_heapify 기능이 잘못되었습니다. 왼쪽 및 오른쪽 자식 계산은 1 씩 바뀝니다. 교체 할 때 배열 값 yikes로 인덱스를 바꿉니다.

3) for heaport for-loop가 잘못되었습니다. 첫 번째 요소 (힙에있는 최대 요소)를 현재 힙의 마지막 인덱스에 놓고 힙 크기를 줄여서 마지막 요소가 힙이 아닌 정렬 된 목록의 일부가되도록해야합니다. 그런 다음 마지막 요소에서가 아니라 루트에서 파생시킵니다. 다음과 같아야합니다 :

for(i= len-1;i>=1;i--) 
    { 
    swap(arr[0],arr[i]); 
    heapsize = heapsize -1; 
    max_heapify(arr,0); 
    } 

Answer 2

swap 함수는 값별로 인수를 사용합니다. 따라서 원본 값이 복사되고 원본은 원본 대신 교체됩니다.

swap(int *a, int *b) 

Answer 3

배열이 전혀 정렬되지 않습니다. 전체 힙 정렬 단위로 작업 해보십시오. 따라서 디버깅 기술로이 코드의 복사본을 만들고 힙 정렬을 버블 정렬로 바꿉니다. 거품 형은 코드 작성이 훨씬 쉽습니다. 버블 정렬을 작동 시키려면 매개 변수를 전달하고 정렬 전후에 배열을 인쇄해야합니다.

그런 다음 힙 정렬을 수행하십시오.

Answer 4

Cormen에 나열된 알고리즘은 실수 한 것 같습니다. 코드에서 다음 줄만 바꾸기 만하면됩니다.

max_heapify (arr, 0); \ 힙 정렬 기능에

build_max_heap와

(도착, 힙 크기);