Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Heap Sort in action.
#include <stdio.h>
#define size 100
#define FIN "algsort.in"
#define FOUT "algsort.out"
#define SIZE 500005
int arr[SIZE],
n;
void create_heap() {
int i, j;
for(i = 2; i <= n; i++) {
j = i;
while(j > 1) {
if(arr[ j ] <= arr[ j / 2 ]) {
int aux = arr[j]; arr[j] = arr[j/2]; arr[j/2] = aux;
j /= 2;
} else j = 1;//or break
}
}
};
int eliminate() {
int i,
j,
x = arr[1];
arr[ 1 ] = arr[ n ];
n--;
i = 1;
while(i <= n) {
if( 2 * i <= n ) {
j = 2 * i;
if(j + 1 <= n && arr[j + 1] <= arr[ j ]) j++;
if(arr[ i ] >= arr[ j ]) {
int aux = arr[i]; arr[i] = arr[j]; arr[j] = aux;
i = j;
} else break;
} else break;
}
return x;
};
void print() {
int i;
for(i = 1; i <= n; i++) printf("%d ",arr[i]);
printf("\n");
};
int main() {
int i;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d", &arr[i]);
create_heap();
for(i = n; i >= 1; i--) {
printf("%d ", eliminate());
}
print();
return(0);
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment