main.cpp

//
//  main.cpp
//  Assgnment7-shellSort
//
//  Created by Zac Holland on 5/25/16.
//  Copyright © 2016 Diericx. All rights reserved.
//

#include <iostream>
#include "FHvector.h"

// Comparison of vector-insertion, shell and STL sort
#include <iostream>
using namespace std;
#include <time.h>
#include <cmath>
#include <algorithm>
#include <vector>

// shellSort #1 -- using shell's outer loop
template <typename Comparable>
void shellSortX(FHvector<Comparable> &a, Comparable gapArray[], int gapArraySize)
{
   int k, i, pos, gap;
   Comparable tmp;
   
   for (i = gapArraySize-1;  i >= 0;  i --) {
      gap = gapArray[i];
      for(pos = gap ; pos < a.size(); pos++ )
      {
         tmp = a[pos];
         for(k = pos; k >= gap && tmp < a[k - gap]; k -= gap )
            a[k] = a[k - gap];
         a[k] = tmp;
      }
   }
}

void calculateImpliedGaps(int gapArraySize) {
   vector<int> array;
   int calc = gapArraySize;
   cout << "{ ";
   while (calc > 1) {
      calc = calc/2;
      array.push_back(calc);
   }
   for (int i = array.size(); i >= 0; i--) {
      cout << array[i] << ", ";
   }
   cout << "}; ";
}

void calculateDoubleGap(int gapArray[],  int &gapSize, int valueArraySize) {
   int i = 1;
   int calc;
   gapArray[0] = i;
   gapArray[1] = 2;
   while ( (calc = gapArray[i-1] * 2) < valueArraySize) {
      gapArray[i] = calc;
      i++;
   }
   gapSize = i;
}

// --------------- main ---------------
#define ARRAY_SIZE 200000

int main()
{
   
   calculateImpliedGaps(ARRAY_SIZE);

   int k;
   clock_t startTime, stopTime;
   int arrayOfInts[ARRAY_SIZE];
   FHvector<int> fhVectorOfInts, fhVectorOfInts2, fhVectorOfInts3, fhVectorOfInts4;
   vector<int> stlVectorOfInts;
   
   int impliedGapArray[] = { 0, 1, 3, 6, 12, 24, 48, 97, 195, 390, 781, 1562, 3125, 6250, 12500, 25000, 50000, 100000, };
   int impliedGapArraySize = sizeof(impliedGapArray) / sizeof(impliedGapArray[0]);
   
   int shellGapArray[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
      2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,
      1048576};
   int shellGapArraySize = sizeof(shellGapArray) / sizeof(shellGapArray[0]);
   
   int sedgewickGapArray[] = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
      8929, 16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689,
      4188161, 9427969, 16764929, 37730305, 67084289, 150958081, 268386305};
   int sedgewickGapArraySize = sizeof(sedgewickGapArray) / sizeof(sedgewickGapArray[0]);
   
   int papernovGapArray[] = {1, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025,
      2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577};
   int papernovGapArraySize = sizeof(papernovGapArray) / sizeof(papernovGapArray[0]);
   
   int hibbardGapArray[] = {1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047,
   4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575};
   int hibbardGapArraySize = sizeof(hibbardGapArray) / sizeof(hibbardGapArray[0]);
   
   // build an array and two vector for comparing sorts
   for (k = 0; k < ARRAY_SIZE; k++)
   {
      arrayOfInts[k] = rand()%ARRAY_SIZE;
      fhVectorOfInts.push_back(arrayOfInts[k]);
      fhVectorOfInts2.push_back(arrayOfInts[k]);
      fhVectorOfInts3.push_back(arrayOfInts[k]);
      fhVectorOfInts4.push_back(arrayOfInts[k]);
      stlVectorOfInts.push_back(arrayOfInts[k]);
   }
   
   cout << endl << endl << "ShellSort using Implied Gap Array...";
   startTime = clock();  // ------------------ start
   
   // sort using insertionSort (in FHsort.h)
   shellSortX(fhVectorOfInts2, sedgewickGapArray, impliedGapArraySize);
   
   stopTime = clock();  // ---------------------- stop
   cout << "\nFH Insertion Elapsed Time: "
   << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC
   << " seconds." << endl << endl;
   
   cout << "ShellSort using Sedgewick Gap Array...";
   startTime = clock();  // ------------------ start
   
   // sort using insertionSort (in FHsort.h)
   shellSortX(fhVectorOfInts2, sedgewickGapArray, sedgewickGapArraySize);
   
   stopTime = clock();  // ---------------------- stop
   cout << "\nFH Insertion Elapsed Time: "
   << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC
   << " seconds." << endl << endl;
   
   
   cout << "ShellSort using Double Gap Array...";
   startTime = clock();  // ------------------ start
   
   // sort using insertionSort (in FHsort.h)
   shellSortX(fhVectorOfInts, shellGapArray, shellGapArraySize);
   
   stopTime = clock();  // ---------------------- stop
   cout << "\nFH Insertion Elapsed Time: "
   << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC
   << " seconds." << endl << endl;
   
   
   cout << "ShellSort using Papernov Gap Array...";
   startTime = clock();  // ------------------ start
   
   // sort using insertionSort (in FHsort.h)
   shellSortX(fhVectorOfInts3, papernovGapArray, papernovGapArraySize);
   
   stopTime = clock();  // ---------------------- stop
   cout << "\nFH Insertion Elapsed Time: "
   << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC
   << " seconds." << endl << endl;
   
   
   cout << "ShellSort using Hibbard Gap Array...";
   startTime = clock();  // ------------------ start
   
   // sort using insertionSort (in FHsort.h)
   shellSortX(fhVectorOfInts4, hibbardGapArray, hibbardGapArraySize);
   
   stopTime = clock();  // ---------------------- stop
   cout << "\nFH Insertion Elapsed Time: "
   << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC
   << " seconds." << endl << endl;
   
   return 0;
}

/*

 Times:
 
 size        |  implied  |  Sedgewick  |  Double Gap (explicit)  |  Papernov  |  Hibbard  |
 -----------------------------------------------------------------------------------
 10,000       0.003631    0.00134       0.00938                   0.004747     0.004619
 50,000       0.022429    0.008731      0.101266                  0.029893     0.030655
 75,000       0.036569    0.012513      0.175571                  0.051622     0.049604
 100,000      0.047835    0.019639      0.269857                  0.070923     0.070632
 150,000      0.088994    0.028922      0.422643                  0.10697      0.112186
 200,000      0.111615    0.039636      0.603412                  0.153927     0.155155
 
 1) Why does Shell's gap sequence implied by shellSort1() give a different timing result than 
    the explicit array described above and passed to shellSortX()?
      - The gap sequence in shellSort1 is in a sense catered to the array size that is given. 
         Rather than just starting at 1 and doubleing each itteration, it starts at the array
         size and divides by two until it reaches one. This gives us results that are more 
         relevant to our current array size.
 2) Which is faster and why?
      - the implied gap sequence is a lot faster because the gaps are directly related to the 
         current array. If an object needs to move, rather than just moving it "some
         large number" down the array, it will move it ArraySize/n down the array. This makes
         each movement more accurate and this makes it sort much quicker.
 
 ----Output at Arraysize = 200000----
 
 { 0, 1, 3, 6, 12, 24, 48, 97, 195, 390, 781, 1562, 3125, 6250, 12500, 25000, 50000, 100000, };
 
 ShellSort using Implied Gap Array...
 FH Insertion Elapsed Time: 0.110693 seconds.
 
 ShellSort using Sedgewick Gap Array...
 FH Insertion Elapsed Time: 0.038743 seconds.
 
 ShellSort using Double Gap Array...
 FH Insertion Elapsed Time: 0.615931 seconds.
 
 ShellSort using Papernov Gap Array...
 FH Insertion Elapsed Time: 0.155052 seconds.
 
 ShellSort using Hibbard Gap Array...
 FH Insertion Elapsed Time: 0.14891 seconds.
 
 Program ended with exit code: 0
*/