Advertisement
thevipershowita

heapsort.c

Mar 3rd, 2021
984
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.08 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3.   void swap(int *a, int *b) {
  4.     int tmp = *a;
  5.     *a = *b;
  6.     *b = tmp;
  7.   }
  8.  
  9.   void heapify(int arr[], int n, int i) {
  10.     int max = i;
  11.     int leftChild = 2 * i + 1;
  12.     int rightChild = 2 * i + 2;
  13.  
  14.     if (leftChild < n && arr[leftChild] > arr[max])
  15.       max = leftChild;
  16.  
  17.     if (rightChild < n && arr[rightChild] > arr[max])
  18.       max = rightChild;
  19.  
  20.     if (max != i) {
  21.       swap(&arr[i], &arr[max]);
  22.       heapify(arr, n, max);
  23.     }
  24.   }
  25.  
  26.   void heapSort(int arr[], int n) {
  27.     for (int i = n / 2 - 1; i >= 0; i--)
  28.       heapify(arr, n, i);
  29.  
  30.     for (int i = n - 1; i >= 0; i--) {
  31.       swap(&arr[0], &arr[i]);
  32.  
  33.       heapify(arr, i, 0);
  34.     }
  35.   }
  36.  
  37.   void display(int arr[], int n) {
  38.     for (int i = 0; i < n; ++i)
  39.       printf("%d ", arr[i]);
  40.     printf("\n");
  41.   }
  42.  
  43.   int main() {
  44.     int arr[] = {55,22,44,11,8,3,1,52,66,26};
  45.     int n = sizeof(arr) / sizeof(arr[0]);
  46.    
  47.     printf("Original array:\n");
  48.     display(arr, n);
  49.     heapSort(arr, n);
  50.  
  51.     printf("Sorted array:\n");
  52.     display(arr, n);
  53.   }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement