Heap Sort ,index of array starting 1 instead of 0

Question

#include<stdio.h>

int swap(int *a,int *b){

int tmp;

 tmp=*a;
*a=*b;
*b=tmp;

}

void heapify(int a[],int n,int i){

int largest =i;
int left=2*i+1;
int right=2*i+2;

while(left<=n&&a[left]>a[largest]){
    largest=left;
 }

while(right<=n&&a[right]>a[largest]){
    largest=right;
 }

if(largest!=i){
swap(&a[largest],&a[i]);
heapify(a,n,largest);
 }

}

int heapSort(int a[],int n){

int i;

for(i=n/2-1;i>=0;i--){
  heapify(a,n,i);
 }

for(i=n;i>=0;i--){
    swap(&a[0],&a[i]);
    heapify(a,n,0);

 }

}

 void printlist(int A[],int len){

int i;

for(i=0;i<len;i++){
    printf(" %d",A[i]);
 }
 printf("\n");
}

int main(){


int a[]={1,5,4,6,3,9,7};
int len=sizeof(a)/sizeof(a[0]);

printf("before :");
printlist(a,len);
heapSort(a,len-1);
printf("after:");
printlist(a,len);

}

Since index of array in heapsort starting 1,i have manually changed it to 0 by changing value of i,left,right....

But the problems still occurs

Here is the output: before : 1 5 4 6 3 9 7 after: 9 7 6 4 5 3 1

There must be some mistakes i didn't noticed,thanks for helping!!

ps:Could anyone suggest a cool link,that cant spot the bug or mistake of code,it will be nice.

Answer 1

The problem is here:

for(i=n;i>=0;i--){
    swap(&a[0],&a[i]);
    heapify(a,n,0);

}

The call to heapify is still using the entire heap. You need to change that to heapify(a, i-1, 0).

Also, in your heapify function, you have:

while(left<=n&&a[left]>a[largest]){
    largest=left;
 }

while(right<=n&&a[right]>a[largest]){
    largest=right;
 }

There's no need for these to be while statements, because the loop body will never execute more than once. For example if in the first one the body is executed, then largest == left, and there's no way that a[left] > a[largest] will evaluate to true the next time around. Those can both be if statements.