one-file-projects/heapsort2.c

50 lines
1.1 KiB
C
Raw Permalink Normal View History

2016-02-21 15:35:43 +01:00
#include <stdio.h>
void swap(int* data, unsigned int i, unsigned int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
void siftdown(int* data, unsigned int n, unsigned int i) {
unsigned int left, right, ip;
while( i < n ) {
left = 2 * i + 1;
right = 2 * i + 2;
if( !(left < n) ) break;
ip = left;
if( right < n && data[ip] < data[right] ) ip = right;
if( data[ip] < data[i] ) break;
swap(data,i,ip);
i = ip;
}
}
void heapcreate(int* data, unsigned int n) {
for(unsigned int i = n/2; i > 0; i--) {
siftdown(data, n, i);
}
siftdown(data, n, 0);
}
void heapsort(int* data, unsigned int n) {
heapcreate(data, n);
for(unsigned int heapsize = n-1; heapsize > 0; heapsize--) {
swap(data,0,heapsize);
siftdown(data,heapsize,0);
}
}
int main( int argc, char *argv[] ) {
int data[10] = { 3,7,5,1,2,8,9,0,4,6 };
heapsort(data, 10);
for(unsigned int i = 0; i < 10; i++) printf("%d ", data[i]);
printf("\n");
return 0;
}