/* Program to use Shell sort to sort an array.

   For simplicity the program will sort float data only.

*/

#include <stdio.h>
#define MAX (1000)

void shell(float fltarr[], int size);

main() {
    float fltarr[MAX];
    int numelts, status;

    /* Input the number to be sorted. */
    printf("Please enter numbers to be sorted, End of File to finish.\n");
    numelts = 0;
    while ((status = scanf("%f", &fltarr[numelts])) >= 0) {
        /* Here, not EOF */
        if (status == 0) {
            printf("Error in input data.  Re-enter that number.\n");

            /* Flush the line with the bad data value. */
            while (getchar() != '\n') {
                /* nothing */
            }
        } else {
            /* All OK */
            numelts++;          /* That's one more valid data item. */
        }
    }

    /* Have the data - sort it. */
    shell(fltarr, numelts);

    /* Print the sorted data */
    for (status=0; status<numelts; status++) {
        printf("%g\n", fltarr[status]);
    }
    return 0;
}

/* shell: Performs a shell sort into ascending order on size elements
   in array fltarr.
*/

void shell(float fltarr[], int size) {

    /* Sorts and searches are the kinds of algorithms that need special
       care to get right because it is so hard to be absolutely certain
       that they are not malfunctioning.  No matter how many trials you
       make, you can never be sure that some peculiar combination of
       data values won't cause the logic to malfunction.  Therefore it
       is important to produce at least an informal proof of the
       correctness of the algorithm.

       The logic is:

           Set gap to size/2.
           while gap >= 1
               do
                   Set not_sorted to false
                   Pass through from i==0 to i==size-1-gap, comparing
                     fltarr[i] with fltarr[i+gap]; if wrongly ordered,
                       exchange and set not-sorted to true.
               while still not_sorted.
               Divide gap by 2.

       Informal correctness check:
       The while loop cannot stop unless gap is 0, therefore, either gap
       was set to zero to start with (meaning that size==1 and the array
       is sorted trivially) or the while loop executed last with gap==1.
       When gap==1, the contents of the while loop execute the basic
       bubble sort algorithm, which we shall verify shortly.  Therefore
       if the while loop stops, it is correct.  The while loop must stop
       because the value of gap is the bound function.  The loop stops
       when gap is 0, and gap must eventually become 0 because integer
       division reduces it by at least 1 each time through.

       We have seen that the final pass through the while loop is with
       gap==1.  Therefore, we need only verify that the do...while will
       sort the array if gap==1.  What it does when gap!=1 cannot alter
       the correctness of the algorithm (although we hope it will speed
       it up!).

       Correctness of do...while loop when gap==1:
       Invariant: After iteration N, at least N items are in their correct
       position.
       Therefore, provided the loop detects when the array is sorted,
       it must eventually stop with the array sorted.
       Therefore on pass N+1, either at least one more item is placed
       correctly (meaning not_sorted is set to true) or ALL the items
       are now sorted, because the comparison pass WILL swap elements
       if any items are out of order.  Therefore detection of failure
       to change the array means the array is sorted.  Therefore the
       not_sorted test is the correct one.

       Correctness of the comparison scan when gap==1:
       Consider all items NOT in their correct position in the array.
       If there are any, there must be a greatest one.  Call it X.
       Invariant: When about to compare items i and i+1, either X has been
       placed correctly or X is at or after element i.
       This is true on entry to the scan, as i==0, the minimum subscript.
       If X is in fltarr[i], the comparison will detect that it is wrongly
       ordered, or else it will have reached its correct place.  If it
       is wrongly ordered, it will be placed in fltarr[i+1].
       The loop will stop when i==size-1, at which point either X is
       correctly placed, or it is in fltarr[i], which must also be
       correct because if not, some other element should be in the top
       position, violating the premise that X is the greatest misplaced
       element.  Therefore the comparison scan places at least the item
       X correctly.  (Some other item will be X for the next comparison
       scan.  So this scan must also place at least one more item in its
       correct position, or else the array is completely sorted.)
    */

    int gap, i, not_sorted;

    gap = size / 2;
    while (gap >= 1) {
        do {
            not_sorted = 0;  /* false */
            for (i=0; i<size-gap; i++) {
                if (fltarr[i] > fltarr[i+gap]) {        /* wrong order */
                    float temp;
                    temp = fltarr[i];                   /* swap */
                    fltarr[i] = fltarr[i+gap];
                    fltarr[i+gap] = temp;
                    not_sorted = 1;                     /* true */
                }
            }
        } while (not_sorted);
        gap /= 2;
    }
    /* Array sorted */
}