Section 5 - Confirmation

3A.5.1 Testing the Sort

We already saw that the bubble sort (a very slow sort!) seemed to be Θ(N2), but let's write a program to track this a little more closely. We'll double the array size each time and time the sort. Our analysis indicates that the times should quadruple. Note that we are dynamically allocating memory for the array. Also, I'm using an array rather than a vector, because I want a very fast underlying data structure to get the best possible estimate for our algorithm.

// Example of timing a simple sort algorithm
#include <iostream>
using namespace std;
#include "Foothill_Sort.h"
#include <time.h>

// --------------- main ---------------
int main()
{
   int k, arraySize;
   clock_t startTime, stopTime;
   double elapsedTime = 0;
   int *arrayOfInts = NULL;

   for (arraySize = 100; elapsedTime < 60; arraySize*=2)
   {
      // allocate array and stuff will values
      arrayOfInts = new int[arraySize];
      for (k = 0; k < arraySize; k++)
         arrayOfInts[k] = rand()%arraySize;

      startTime = clock();    // start timing ---------------

      // sort using a home made bubble sort (in Foothill_Sort.h)
      arraySort(arrayOfInts, arraySize);

      stopTime = clock();      // stop timing ------------------------
      elapsedTime = (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC;
      cout << "\nN: " << arraySize << " Sort Time: " 
         << elapsedTime  << " seconds." << endl;

      // release memory
      delete[] arrayOfInts;
   }
   return 0; 
}

/* ----------------- RUN --------------------------


N: 100 Sort Time: 0 seconds.

N: 200 Sort Time: 0 seconds.

N: 400 Sort Time: 0 seconds.

N: 800 Sort Time: 0 seconds.

N: 1600 Sort Time: 0 seconds.

N: 3200 Sort Time: 0 seconds.

N: 6400 Sort Time: 0.047 seconds.

N: 12800 Sort Time: 0.187 seconds.

N: 25600 Sort Time: 0.811 seconds.

N: 51200 Sort Time: 3.354 seconds.

N: 102400 Sort Time: 13.69 seconds.

N: 204800 Sort Time: 55.014 seconds.

N: 409600 Sort Time: 219.774 seconds.
Press any key to continue . . .
----------------------------------------------- */

You can graph this or just look at it. For small arrays, it seems linear, but as N grows, you'll see that it certainly acts quadratic, not linear, cubic or anything else. Look at N = 12800 vs. 25600: .187 × 4 = .748 vs. the actual .811. Look at N = 25600 vs. 51200: .811 × 4 = 3.244 vs. the actual 3.354. Finally, check out N = 51200 vs. 102400: 3.354× 4 = 13.416 vs. the actual 13.69. You can't get much better agreement than that. Try it on your system and see what you get. If you do, remember that the program continues until the algorithm takes more than 60 seconds, then breaks. That means it may take more than couple minutes to run the program when you add all the non-breaking passes.

Here is another run, this time on an older unix-based system:

N: 100 Sort Time: 5.2e-05 seconds.


N: 200 Sort Time: 0.000197 seconds.


N: 400 Sort Time: 0.000775 seconds.


N: 800 Sort Time: 0.003232 seconds.


N: 1600 Sort Time: 0.012601 seconds.


N: 3200 Sort Time: 0.05008 seconds.


N: 6400 Sort Time: 0.200337 seconds.


N: 12800 Sort Time: 0.79884 seconds.


N: 25600 Sort Time: 3.19512 seconds.


N: 51200 Sort Time: 12.7987 seconds.


N: 102400 Sort Time: 51.1529 seconds.


N: 204800 Sort Time: 204.5 seconds.

The numbers are different, but on each sort result, we get about 4× the previous duration, consistent with a quadratic running time (because when you double N, as we are doing on each sort, you expect the elapsed time to increase by a factor of 2×2 = 4).

3A.5.2 Testing the Insertion

Let's test the insertion using both the N (array size) and M (number of insertions) as input. We'll double N and triple M each time. Since we have analyzed this in a previous section and found this to be a Θ(NM), we expect a 6-fold running increase each loop pass.

#include <iostream>
using namespace std;
#include "Foothill_Sort.h"
#include <time.h>

// --------------- main ---------------
int main()
{
   int k, arraySize, numInsertions, writePosition;
   clock_t startTime, stopTime;
   double elapsedTime = 0;
   int *arrayOfInts = NULL;
   const int NUM_POSITIONS = 5;
   int somePositions[NUM_POSITIONS] = {3, 67, 20, 15, 59  };

   for (arraySize = 100, numInsertions = 50; elapsedTime < 60; arraySize*=2, numInsertions*=3)
   {
      // allocate array and stuff will values
      arrayOfInts = new int[arraySize + 1];
      for (k = 0; k < arraySize; k++)
         arrayOfInts[k] = rand()%arraySize;

      startTime = clock();    // start timing ---------------
      
      // we will do numInsertions
      for (int attempt = 0; attempt < numInsertions; attempt++)
      {
         writePosition = somePositions[ attempt % NUM_POSITIONS ];

         // move everything up one 
         for (int k = arraySize; k > writePosition; k--)
            arrayOfInts[k] = arrayOfInts[k-1];

         // now put a new number into the free position
         arrayOfInts[writePosition] = 51;
      }

      stopTime = clock();      // stop timing ------------------------
      elapsedTime = (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC;
      cout << "\nN: " << arraySize << " Insertion Time: " 
         << elapsedTime  << " seconds." << endl;

      // release memory
      delete[] arrayOfInts;
   }
   return 0; 
}

/* ----------------- RUN --------------------------

N: 100 Insertion Time: 0 seconds.

N: 200 Insertion Time: 0 seconds.

N: 400 Insertion Time: 0 seconds.

N: 800 Insertion Time: 0 seconds.

N: 1600 Insertion Time: 0 seconds.

N: 3200 Insertion Time: 0.031 seconds.

N: 6400 Insertion Time: 0.125 seconds.

N: 12800 Insertion Time: 0.78 seconds.

N: 25600 Insertion Time: 4.664 seconds.

N: 51200 Insertion Time: 27.955 seconds.

N: 102400 Insertion Time: 167.952 seconds.
Press any key to continue . . .

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

You can clearly see the ×6 increases, especially as N becomes large.