Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- typedef int int_array_type[10];
- static inline int get_left_child_index(int index)
- {
- return (index << 1) + 1;
- }
- static inline int get_right_child_index(int index)
- {
- return (index << 1) + 2;
- }
- void fill_array(int_array_type array)
- {
- int i;
- for(i = 0; i < sizeof(int_array_type)/sizeof(array[0]); i++)
- array[i] = rand() % 100;
- }
- void print_array(int_array_type array)
- {
- int i;
- for(i = 0; i < sizeof(int_array_type)/sizeof(array[0]); i++)
- printf("%d ", array[i]);
- printf("\n");
- }
- void swap(int *first, int *second)
- {
- int tmp = *first;
- *first = *second;
- *second = tmp;
- }
- void heapify(int_array_type array, int index, unsigned int size)
- {
- int left = get_left_child_index(index);
- int right = get_right_child_index(index);
- int largest = index;
- if(left <= size)
- if(array[left] > array[index])
- largest = left;
- if(right <= size)
- if(array[right] > array[largest])
- largest = right;
- if(largest != index){
- swap(&array[index], &array[largest]);
- heapify(array, largest, size);
- }
- }
- void build_heap(int_array_type array)
- {
- int i;
- const int number_of_elements = sizeof(int_array_type)/sizeof(*array);
- for(i = number_of_elements/2; i >= 0; i--)
- heapify(array, i, number_of_elements);
- }
- void heapsort(int_array_type array)
- {
- int last_index = sizeof(int_array_type)/sizeof(*array);
- //int last_index = sizeof(int_array_type)/sizeof(*array-1);
- int i;
- build_heap(array);
- for(i = last_index; i > 0; i--){
- swap(&array[0], &array[i]);
- heapify(array, 0, --last_index);
- }
- }
- int main(void)
- {
- srand(time(NULL));
- int_array_type array;
- fill_array(array);
- print_array(array);
- printf("\n");
- heapsort(array);
- print_array(array);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement