C言語でヒープソートを書く
code:c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define swap(a, b) do { \
typeof(a) (_tmp) = (a); \
(a) = (b); \
(b) = (_tmp); \
} while (0);
void print_array(int64_t *ar, int64_t n) {
for (int64_t i = 0; i < n; ++i) {
printf("%ld ", ari);
}
putc('\n', stdout);
}
void heapify(int64_t *arr, int64_t n, int64_t i) {
for (;;) {
int64_t largest = i;
int64_t left = i * 2 + 1;
int64_t right = i * 2 + 2;
if (left < n &&
arrleft > arrlargest)
largest = left;
if (right < n &&
arrright > arrlargest)
largest = right;
if (largest == i)
break;
swap(arri, arrlargest);
i = largest;
}
}
void heapsort(int64_t *arr, int64_t n) {
// make heap
for (int64_t i = n / 2 - 1; i >= 0; --i )
heapify(arr, n, i);
for (int64_t i = n - 1; i >= 0; --i) {
swap(arri, arr0);
heapify(arr, i, 0);
}
}
int main() {
int64_t ar[] = { 13, 19, 9, 5, 12,
8, 7, 4, 21, 2,
5, 3, 14, 6, 11 };
int64_t n = sizeof ar / sizeof(ar0);
print_array(ar, n);
heapsort(ar,n);
print_array(ar, n);
return 0;
}