fork download 
  1. //(c)Terminator
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5.  
  6. // функция восстановления свойства бинарной кучи
  7. void  __heapify(int* arr, int i, int cnt) {
  8.     int t, l, r, large;
  9.  
  10.     while(1){
  11.         l = i*2 + 1;
  12.         r = i*2 + 2;
  13.         if((l < cnt) && (arr[l] > arr[i]))
  14.             large = l;
  15.         else
  16.             large = i;
  17.  
  18.         if((r < cnt) && (arr[r] > arr[large]))
  19.             large = r;
  20.  
  21.         if(large != i){
  22.             t          = arr[i];
  23.             arr[i]     = arr[large];
  24.             arr[large] = t;
  25.  
  26.             i = large;
  27.         } else
  28.             break;
  29.     }
  30. }
  31.  
  32.  
  33. // Пирамидальная сортировка
  34. void heap_sort(int* arr, int cnt){
  35.     int t, i;
  36.     // в начале из массива делаем make-heap
  37.     for(i = cnt/2-1; i >= 0; --i)
  38.         __heapify(arr, i, cnt);
  39.  
  40.     //pop_min
  41.     for(i = cnt - 1; i >= 0; --i) {
  42.         t      = arr[0];
  43.         arr[0] = arr[i];
  44.         arr[i] = t;
  45.         __heapify(arr, 0, i);
  46.     }
  47. }
  48.  
  49.  
  50. int main(void){
  51.     int i;
  52.     int arr[] = { 100, 9, 5, 8, 1, 2, 6, 7, 4, 3, -100 };
  53.     int cnt   = sizeof(arr)/sizeof(arr[0]);
  54.  
  55.     heap_sort(arr, cnt);
  56.  
  57.     for(i = 0; i < cnt; ++i)
  58.         printf("%d ", arr[i]);
  59.     return 0;
  60. }
Success #stdin #stdout 0s 2292KB
comments (?)
stdin 
Standard input is empty
stdout 
-100 1 2 3 4 5 6 7 8 9 100
https://ideone.com/8tMxih
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!