Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 69 lines (58 sloc) 1.361 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
#include <stdio.h>
void heapSort(int [], int);
void siftDown(int [], int, int);
int main()
{
  const int MAX=20;
  int a[MAX];
  /* int a[]={5,1,4,88,82,1,42,1,4,5,14,74,5,4,48}; */
  /* size_t size=(sizeof a)/(sizeof *a); */
  printf("How many elements? (MAX: %i)",MAX);
  size_t size;
  scanf("%i",&size);
  int i;
  printf("Enter the Elements:\n");
  for (i=0; i<size; ++i)
    scanf("%i",a+i);
  
  heapSort(a,size);

  for(i=0; i<size; ++i)
    printf("[%i]",a[i]);
  printf("\n");
  return 0;
}

void heapSort(int numbers[], int array_size)
{
  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)
    {
      temp = numbers[0];
      numbers[0] = numbers[i];
      numbers[i] = temp;
      siftDown(numbers, 0, i-1);
    }
}


void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 <= bottom) && (!done))
    {
      if (root*2 == bottom)
maxChild = root * 2;
      else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
      else
maxChild = root * 2 + 1;

      if (numbers[root] < numbers[maxChild])
        {
          temp = numbers[root];
          numbers[root] = numbers[maxChild];
          numbers[maxChild] = temp;
          root = maxChild;
        }
      else
done = 1;
    }
}

Something went wrong with that request. Please try again.