/*------------------------------------------------------------------*/
/* sort4.c                                                          */
/* Author: Bob Dondero                                              */
/* A dynamically expanding array                                    */
/*------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

enum {INITIAL_ARRAY_LENGTH = 2};
enum {ARRAY_GROWTH_FACTOR = 2};

/*------------------------------------------------------------------*/

static void insertionSort(double *pdNumbers, int iNumberCount)

/* Sort pdNumbers[0..iNumberCount-1] in ascending order. */

{
   int i1;
   int i2;
   double dTemp;

   for (i1 = 1; i1 < iNumberCount; i1++)
      for (i2 = i1; i2 > 0; i2--)
         if (pdNumbers[i2] < pdNumbers[i2-1])
         {
            dTemp = pdNumbers[i2];
            pdNumbers[i2] = pdNumbers[i2-1];
            pdNumbers[i2-1] = dTemp;
         }
}

/*------------------------------------------------------------------*/

int main(int argc, char *argv[])

/* Read numbers from stdin, and write them in ascending order to
   stdout.  Return 0. */

{
   double *pdNumbers;
   int iNumberCount;
   int iArrayLength;
   double dNumber;
   int i;

   /* Dynamically allocate an array. */

   iArrayLength = INITIAL_ARRAY_LENGTH;
   pdNumbers = (double*)calloc((size_t)iArrayLength, sizeof(double));
   assert(pdNumbers != NULL);

   /* Read the numbers into the array. */

   iNumberCount = 0;
   while (scanf("%lf", &dNumber) != EOF)
   {
      if (iNumberCount == iArrayLength)
      {
         iArrayLength *= ARRAY_GROWTH_FACTOR;
         pdNumbers =
            (double*)realloc(pdNumbers, iArrayLength * sizeof(double));
         assert(pdNumbers != NULL);
      }
      pdNumbers[iNumberCount] = dNumber;
      iNumberCount++;
   }

   /* Sort the array. */

   insertionSort(pdNumbers, iNumberCount);

   /* Write the numbers from the array. */

   for (i = 0; i < iNumberCount; i++)
      printf("%g\n", pdNumbers[i]);

   /* Free the array. */

   free(pdNumbers);

   return 0;
}