/********************************************************************************************
shell.cpp
	Jim Millard
	for CO311

    Shell Sort: Modified BubbleSort that goes a bit quicker...

********************************************************************************************/
#include <iostream>
#include <string>

#include "sorttool.h"

using namespace std;

void ShellSort(int [], const int size, const int used);

void main()
    {
    const int MaxSize = 1000;
    int Array[MaxSize];

    int toSort;
    cout << "How many numbers to sort (up to " << MaxSize << "): ";
    cin >> toSort;

    FillWithRand(Array, MaxSize, toSort); //setup the array with X numbers

    cout << "Unsorted:" << endl;
    ParseAndPrint(Array, MaxSize, toSort); //show the unsorted array

    ShellSort(Array, MaxSize, toSort); //sort the first X elements of the array

    cout << "Sorted:" << endl;
    ParseAndPrint(Array, MaxSize, toSort); //show the (hopefully) sorted array

    }

void ShellSort(int Array[], const int maxsize, const int count)
    {
    bool DoneSorting = false;
    int delta = count/2;
    while (!DoneSorting)
        {
        DoneSorting = true;
        for (int current = 0; (current < count-delta) && (current < maxsize-delta); current++)
            if (Array[current] > Array[current+delta])
                {
                DoneSorting = false;
                Swap(Array[current],Array[current+delta]);
                }
        if (DoneSorting && (delta > 1))
            {
            DoneSorting = false;
            delta /= 2;
            }
        }
    return;
    }