Enhancing the CombSort Algorithm

By

Namir Clement Shammas

Several years ago, I read an article by Richard Box and Stephen Lacey entitled "A Fast, Easy Sort" (BYTE, April 1991) that presented a sorting method called CombSort that significantly improved the notoriously slow Bubble sort. CombSort sped up sorting by initially comparing array elements that are not immediate neighbors. Of course, this approach is not new since the well-known Shell method employs the same strategy. When I first learned about CombSort I regarded it as a clever and effective simplification of the Shell method itself. Like the Shell method, the CombSort makes several passes at the array elements. Each pass compares elements that are located at an offset index value (also called the gap). With each pass, the value of that offset becomes smaller. Eventually, the CombSort method (and also the Shell method) compares neighboring array elements. By comparing distance elements first, the sort method allows elements to be ordered quicker than the Bubble sort. Figure 1 is pseudo-code for the CombSort method. Box and Lacey had studied the optimum scheme for initializing and updating the offset value.

I started studying the CombSort method and the first aspect of the algorithm I monitored was the offset value. Table 1 (generated using CTestCombSort.cpp) shows the total number of passes versus the number of passes that compare neighboring array elements in CombSort. The CombSort method initializes the offset value with the number of array elements. Each pass calculates a new and smaller offset value, as in Figure 1. I generated Table 1 by sorting arrays of long integers that ranged from 100 elements to 50,000 elements. The table shows that most of the passes in CombSort are engaged in comparing neighboring array elements! The beauty of CombSort is that the first few passes seem to stir, so to speak, the array elements enough to improve CombSort significantly over Bubble sort. My question was "What is the gain if we extend the comparison of non-neighboring elements?"

Before answering this question, let me brief you on the CTestCombSort.cpp source code. CTestCombSort.cpp declares the class CTestCombSort, which tallies the iteration counters. The class declares the following members:

·         The data member m_lCount stores the number of array elements.

·         The data member m_plArr is the pointer to the dynamic array of long integers.

·         A class constructor that initializes the data members.

·         The member function CreateRandArr creates a dynamic array (accessed by the data member m_ plArr) and assigns random numbers to its elements.

·         The member function CombSort implements the CombSort algorithm. This member function has two long-type reference parameters, namely, lTotalIters and lIters. These parameters return the total number of passes and the number of passes with the offset value as 1, respectively.

CTestCombSort.cpp also declares the function main, which creates the object objSort as an instance of class CTestCombSort. The function uses a loop to test the CombSort method for different array sizes, ranging from 100 to 50,000. In each iteration, the function sends the messages CreateRandArr and CombSort to the object objSort to create an array with random values and then sort the array using the CombSort method, respectively. The function main sends output to the console and also to two text files. The testcs.dat text file contains a copy of the console output. The testcsCDD.dat text file contains comma-delimited values that let you insert the data in a Word or Excel file.

Table 1 shows that the offset value used to compare distance array elements quickly reaches 1. To enhance CombSort, I set out to find an approach that resets or restores the value of the offset to a value greater than 1, as long as it is feasible. In creating what I call the Extended CombSort method, I tried a few techniques to appropriately reset the offset value after it reaches 1 the first time. My early attempts were to systematically restore once or twice the offset value to its initial value. Figure 2 is the pseudocode for the Extended CombSort method that I eventually settled on. The new algorithm uses a counter (which I call the reset counter) to monitor the extent to which the method restores the offset value. The algorithm performs the following additional tasks after it ends the loop that compares the array elements:

1. Increments a reset-counter when the inOrder flag is True (that is, when the loop did not swap any element).

2. Restores the offset value using the reset counter when the inOrder flag is false and the offset value is 1.

These two tasks empower the algorithm to accelerate moving array elements to their proper indices that yield a sorted array. CExCombSort.cpp is the test program that compares the Bubble, CombSort, and Extended CombSort methods. I included the Bubble sort for comparison’s sake. The listing declares the class CExCombSort, which encapsulates the following members:

·         The data member m_lCount stores the number of array elements.

·         The data member m_ plArr is the pointer to the dynamic array of long integers.

·         The data member m_lComps stores the number of times array elements are compared.

·         The data member m_lSwaps stores the number of times array elements are swapped.

·         The data member m_lResets stores the number of times the offset value is reset.

·         A class constructor that initializes the data members.

·         The member function CreateRandArr creates a dynamic array (accessed by the data member m_plArr) and assigns random numbers to its elements.

·         The member function CreateAscendArr creates a dynamic ordered array that has values in ascending order.

·         The member function CreateDescendArr creates a dynamic ordered array that has values in descending order.

·         The member functions getSwaps, getComps, and getResets return the values for the number of element swaps, element comparisons, and offset value resets, respectively.

·         The member function BubbleSort implements the Bubble sort method. This member function creates a local copy of the instance’s array elements and then sorts the local array.

·         The member function CombSort implements the CombSort method. This member function creates a local copy of the instance’s array elements and then sorts the local array.

·         The member function ExCombSort implements the Extended CombSort method. This member function creates a local copy of the instance’s array elements and then sorts the local array.

CExCombSort.cpp also declares function main. This function creates the object objSort as an instance of class CExCombSort. The function uses a loop to test arrays of different sizes ranging from 100 to 50,000. In each iteration, the function creates a random array and then sorts a copy of that array using the Bubble sort, CombSort, and Extended CombSort methods. Since we are dealing with arrays storing random numbers, each iteration contains a nested loop that performs these tasks several times to get multiple results. Once testing the random arrays ends, the function then tests sorting ordered arrays (with ascending and descending values) using the three sorting algorithms. Sorting arrays with initially descending values represents a worse-case scenario. The other extreme is supplying the sorting methods with arrays that are already ordered.

The function main sends the output to the console and to various text files. The sort.dat text file contains a copy of the console output. The text file sortCDD.dat contains comma-delimited values for the array size, common log of the array size, the product of the latter two values, and the common log of the number of comparisons and swaps for the three sorting methods used. The last field is the number of offset resets used by the Extended CombSort method. The function also sends comma-delimited data for sorted reverse ordered arrays to file sortDesCDD.dat. This file has comma-delimited fields that are similar to those in file sortCDD.dat.

Table 2 is a sample output for file sortCDD.dat. The advantage of using common logarithm values is the ability to easily examine values that have a very wide range, since you can focus on the order of magnitudes. Studying Table 2 shows that the Extended CombSort has a number of comparisons and swaps that are less by at least an order of magnitude, compared with CombSort, for array size with 2500 elements or more. The gap widens, when the array size increases to 50,000 elements, to almost three orders of magnitude.

I took the data in Table 2 and inserted them in an Excel spreadsheet. I then used the linear regression add-in feature to correlate the common log of array size with the common log values for the comparison and swap counts. Table 3 shows the results that include the correlation coefficient, intercept, and slope for the log-log curve fit. The slope values represent the sort order (used in the big O notation seen in many algorithm books). I did test the correlation between the number of swaps for the various algorithms and N*log(N) but found not significant correlation between them.

Table 3 shows that both the Bubble sort and the CombSort methods have an order of O(N²) for comparing and swapping elements. The Extended CombSort method shows an improved order of O(N^4/3). By resetting the offset value, the Extended CombSort method gains significant advantage.

Table 4 shows regression statistics for the sorting methods working with sorted arrays with initially descending values. While the order of sorting for the Bubble sort remains O(N²), the order for the other two sorting methods has decreased. In the case of the Extended CombSort the order approaches O(N). The number of offset-resets correlates well with the common log of the array size in the following model:

Number Resets = 3 * log10(Array Size) – 1

In summary, you can accelerate the CombSort method by resetting the offset value and allowing the quick traversal of array elements over a wide index range. This enhancement also improves the order of the sort method from O(N²) to O(N^4/3).

Figure 1: Pseudo-code for the CombSort method.

Give an array A[0..N-1]

Set Offset equal to N

Repeat

        Set Offset = (5 * Offset) / 11

        If Offset is 0 then set Offset to be 1

        Set inOrder flag to true

        Loop over A[I] for I in the range 0 to N - Offset

            When A[I] > A[I + Offset] then

                        Swap A[I] and A[I+Offset]

                        Set inOrder flag to false

        End loop

Until Offset is 1 and inOrder flag is true

Figure 2: The pseudo-code for the Extended CombSort method.

Give an array A[0..N-1]

Set Offset equal to N

Set ResetCounter to 0

Repeat

        Set Offset = (5 * Offset) / 11

        If Offset is 0 then set Offset to be 1

        Set inOrder flag to true

        Loop over A[I] for I in the range 0 to N - Offset

             When A[I] > A[I + Offset] then

                         Swap A[I] and A[I+Offset]

                         Set inOrder flag to false

        End loop

        If inOrder flag is true increment ResetCounter

        If inOrder flag is false and Offset is 1 then

        Set Offset equal to N

        Loop ResetCounter number of times

                               Set Offset = (5 * Offset) / 11

                               If Offset is 0 then set Offset to be 1

                   End Loop

Until Offset is 1 and inOrder flag is true

Table 1: Comparing the total number of passes with the number of passes that compare neighboring array elements in CombSort.

Table 2: Tabulated sorting results based on sample output for file sortCDD.dat.

 N,Log(N),N*Log(N),Bubble # Comps,Bubble # Swaps,CombSort #Comps,CombSort # Swaps,ExCombSort #Comps,ExCombSort # Swaps, # Resets
100,2,200,3.69461,3.45317,3.64157,2.8791,3.31911,2.72835,5
100,2,200,3.69461,3.45317,3.64157,2.8791,3.31911,2.72835,5
100,2,200,3.69461,3.45317,3.64157,2.8791,3.31911,2.72835,5
100,2,200,3.69461,3.45317,3.64157,2.8791,3.31911,2.72835,5
100,2,200,3.69461,3.45317,3.64157,2.8791,3.31911,2.72835,5
250,2.39794,599.485,4.49311,4.14987,4.34173,3.51014,3.91249,3.27114,6
250,2.39794,599.485,4.49311,4.14987,4.34173,3.51014,3.91249,3.27114,6
250,2.39794,599.485,4.49311,4.16702,4.31639,3.40483,3.84223,3.197,6
250,2.39794,599.485,4.49311,4.16702,4.31639,3.40483,3.84223,3.197,6
250,2.39794,599.485,4.49311,4.16702,4.31639,3.40483,3.84223,3.197,6
500,2.69897,1349.49,5.09604,4.78371,4.92904,4.03659,4.25188,3.64826,7
500,2.69897,1349.49,5.09604,4.78371,4.92904,4.03659,4.25188,3.64826,7
500,2.69897,1349.49,5.09604,4.78371,4.92904,4.03659,4.25188,3.64826,7
500,2.69897,1349.49,5.09604,4.78371,4.92904,4.03659,4.25188,3.64826,7
500,2.69897,1349.49,5.09604,4.78371,4.92904,4.03659,4.25188,3.64826,7
1000,3,3000,5.69854,5.39531,5.67459,4.56711,4.65015,4.061,8
1000,3,3000,5.69854,5.39531,5.67459,4.56711,4.65015,4.061,8
1000,3,3000,5.69854,5.39531,5.67459,4.56711,4.65015,4.061,8
1000,3,3000,5.69854,5.39531,5.67459,4.56711,4.65015,4.061,8
1000,3,3000,5.69854,5.39531,5.67459,4.56711,4.65015,4.061,8
2500,3.39794,8494.85,6.49468,6.19252,6.49055,5.34902,5.13564,4.58246,9
2500,3.39794,8494.85,6.49468,6.19252,6.49055,5.34902,5.13564,4.58246,9
2500,3.39794,8494.85,6.49468,6.19252,6.49055,5.34902,5.13564,4.58246,9
2500,3.39794,8494.85,6.49468,6.19252,6.49055,5.34902,5.13564,4.58246,9
2500,3.39794,8494.85,6.49468,6.19252,6.49055,5.34902,5.13564,4.58246,9
5000,3.69897,18494.9,7.09682,6.77319,7.06121,5.93596,5.50957,4.98332,10
5000,3.69897,18494.9,7.09682,6.77319,7.06121,5.93596,5.50957,4.98332,10
5000,3.69897,18494.9,7.09682,6.78298,7.05723,5.94829,5.52279,4.98361,10
5000,3.69897,18494.9,7.09682,6.78298,7.05723,5.94829,5.52279,4.98361,10
5000,3.69897,18494.9,7.09682,6.78298,7.05723,5.94829,5.52279,4.98361,10
10000,4,40000,7.69893,7.35461,7.69026,6.52382,5.88398,5.35688,11
10000,4,40000,7.69893,7.35731,7.6965,6.52301,5.85798,5.3588,11
10000,4,40000,7.69893,7.35326,7.66254,6.51487,5.87026,5.35537,11
10000,4,40000,7.69893,7.35468,7.67013,6.51608,5.87805,5.35019,11
10000,4,40000,7.69893,7.35515,7.67895,6.51155,5.8951,5.35329,11
25000,4.39794,109949,8.49483,8.09333,8.52607,7.30949,6.35245,5.83377,12
25000,4.39794,109949,8.49483,8.09263,8.53862,7.31109,6.36686,5.83932,12
25000,4.39794,109949,8.49483,8.09125,8.51013,7.31365,6.36169,5.84034,12
25000,4.39794,109949,8.49483,8.08936,8.55771,7.30352,6.3713,5.83703,12
25000,4.39794,109949,8.49483,8.09055,8.5693,7.3064,6.36102,5.83605,12
50000,4.69897,234949,9.0969,8.60019,9.13736,7.91398,6.93203,6.28393,13
50000,4.69897,234949,9.0969,8.6014,9.12311,7.90857,6.83578,6.26653,13
50000,4.69897,234949,9.0969,8.603,9.11018,7.89677,6.88121,6.25014,13
50000,4.69897,234949,9.0969,8.60267,9.10542,7.91171,6.81307,6.25911,13
50000,4.69897,234949,9.0969,8.60091,9.15622,7.90612,6.90587,6.2937,13
 

Table 3: Regression statistics summary for the sorting methods.

Table 4: Regression statistics summary for the sorting methods working with sorted arrays with initially descending values.

Listing 1. File CTestCombSort.cpp

/*
  Program that monitors the offset value used in the CombSort method.
*/

//---------------------------------------------------------------------------

#pragma hdrstop
#include 
#include 
#include 
#include 

//---------------------------------------------------------------------------

class CTestCombSort
{
  public:
    CTestCombSort();
    void CreateRandArr(long lCount);
    void CombSort(long& lTotalIters, long& lIters);

  protected:
    long m_lCount;
    long* m_plArr;
};

CTestCombSort::CTestCombSort()
{
  m_lCount = 0;
  m_plArr = 0;
}

void CTestCombSort::CreateRandArr(long lCount)
{
  // remove old dynamic array
  if (m_plArr != 0)
    delete [] m_plArr;
  // create new dynamic array
  m_plArr = new long[lCount];
  m_lCount = lCount;
  randomize(); // reseed random number generator
  for (long i = 0; i < m_lCount; i++)
    m_plArr[i] = rand() % 100000;
}

void CTestCombSort::CombSort(long& lTotalIters,
                             long& lIters)
{
  long i, j, lOffset;
  long lSwap;
  bool bInOrder;
  long* plArr;

  // create local array
  plArr = new long[m_lCount];
  // copy instance's array into local array
  for (i = 0; i < m_lCount; i++)
    plArr[i] = m_plArr[i];

  lOffset = m_lCount;
  lTotalIters = 0;
  lIters = 0;
  do {
    lOffset = (5 * lOffset) /11;
    if (lOffset == 0) lOffset = 1;
    lTotalIters++;
    if (lOffset == 1) lIters++;
    bInOrder = true;
    for (i = 0; i < (m_lCount - lOffset); i++) {
      j = i + lOffset;
      if (plArr[i] > plArr[j]) {
        bInOrder = false;
        lSwap = plArr[i];
        plArr[i] = plArr[j];
        plArr[j] = lSwap;
      }
    }
  } while (!(lOffset == 1 && bInOrder));
  delete [] plArr;
}

#pragma argsused
int main(int argc, char* argv[])
{
  CTestCombSort objSort;
  fstream f1("\\testcs.dat", ios::out);
  fstream f2("\\testcsCD.dat", ios::out);
  long lTotalIters, lIters;
  long lSizeArr[] = { 100, 250, 500, 1000, 2500, 5000, 10000,
                      25000, 50000, 0 };

  for (long lSize = 0; lSizeArr[lSize] > 0; lSize++)
  {
    cout << "Size = " << lSizeArr[lSize] << endl;
    f1 << "Size = " << lSizeArr[lSize] << endl;
    f2 << lSizeArr[lSize] << ",";
    objSort.CreateRandArr(lSizeArr[lSize]);

    // perform CombSort
    objSort.CombSort(lTotalIters, lIters);
    cout << "Total Iterations            = "
         << lTotalIters << endl
         << "Iterations with offset of 1 = "
         << lIters << endl;
    f1 << "Total Iterations            = "
         << lTotalIters << endl
         << "Iterations with offset of 1 = "
         << lIters << endl;
    f2 << lTotalIters << "," << lIters << endl;
  }

  char c[2];
  cout << "Press Enter to end the program";
  cin.getline(c, 1);
  cout << "Done!";
  f1.close();
  f2.close();
  return 0;
}

/*
  Source code for testing the Bubble sort, CombSort, and Extended
  CombSort method.

  Developed by Namir C. Shammas November 1, 2001.

*/

#include 
#include 
#include 
#include 
#include 

class CExCombSort
{
  public:
    CExCombSort();
    void CreateRandArr(long lCount);
    void CreateAscendArr(long lCount);
    void CreateDescendArr(long lCount);

    long getSwaps()
      { return m_lSwaps; }
    long getComps()
      { return m_lComps; }
    long getResets()
      { return m_lResets; }

    void BubbleSort();
    void CombSort();
    void ExCombSort();

  protected:
    long m_lCount;
    long* m_plArr;
    long m_lSwaps;
    long m_lComps;
    long m_lResets;
};

CExCombSort::CExCombSort()
{
  m_lCount = 0;
  m_plArr = 0;
  m_lSwaps = 0;
  m_lComps = 0;
  m_lResets = 0;
}

void CExCombSort::CreateRandArr(long lCount)
{
  // remove old dynamic array
  if (m_plArr != 0)
    delete [] m_plArr;
  // create new dynamic array
  m_plArr = new long[lCount];
  m_lCount = lCount;
  randomize(); // reseed random number generator
  for (long i = 0; i < m_lCount; i++)
    m_plArr[i] = rand() % 100000;
}

void CExCombSort::CreateAscendArr(long lCount)
{
  // remove old dynamic array
  if (m_plArr != 0)
    delete [] m_plArr;
  // create new dynamic array
  m_plArr = new long[lCount];
  m_lCount = lCount;
  for (long i = 0; i < m_lCount; i++)
    m_plArr[i] = i;
}

void CExCombSort::CreateDescendArr(long lCount)
{
  // remove old dynamic array
  if (m_plArr != 0)
    delete [] m_plArr;
  // create new dynamic array
  m_plArr = new long[lCount];
  m_lCount = lCount;
  for (long i = 0; i < m_lCount; i++)
    m_plArr[i] = m_lCount - i;
}

void CExCombSort::BubbleSort()
{
  long i, j;
  long lSwap;
  long* plArr;

  // create local array
  plArr = new long[m_lCount];
  // copy instance's array into local array
  for (i = 0; i < m_lCount; i++)
    plArr[i] = m_plArr[i];

  m_lSwaps = 0;
  m_lComps = 0;
  for (long i = 0; i < (m_lCount-1); i++) {
    for (long j = i+1; j < m_lCount; j++) {
      m_lComps++;
      if (plArr[i] > plArr[j]) {
        m_lSwaps++;
        lSwap = plArr[i];
        plArr[i] = plArr[j];
        plArr[j] = lSwap;
      }
    }
  }
  delete [] plArr;
}

void CExCombSort::CombSort()
{
  long i, j, lOffset;
  long lSwap;
  bool bInOrder;
  long* plArr;

  // create local array
  plArr = new long[m_lCount];
  // copy instance's array into local array
  for (i = 0; i < m_lCount; i++)
    plArr[i] = m_plArr[i];

  lOffset = m_lCount;
  m_lSwaps = 0;
  m_lComps = 0;
  do {
    lOffset = (5 * lOffset) /11;
    if (lOffset == 0) lOffset = 1;
    bInOrder = true;
    for (i = 0; i < (m_lCount - lOffset); i++) {
      j = i + lOffset;
      m_lComps++;
      if (plArr[i] > plArr[j]) {
        m_lSwaps++;
        bInOrder = false;
        lSwap = plArr[i];
        plArr[i] = plArr[j];
        plArr[j] = lSwap;
      }
    }
  } while (!(lOffset == 1 && bInOrder));
  delete [] plArr;
}

void CExCombSort::ExCombSort()
{
  long i, j, lOffset;
  long lSwap;
  bool bInOrder;
  long* plArr;

  // create local array
  plArr = new long[m_lCount];
  // copy instance's array into local array
  for (i = 0; i < m_lCount; i++)
    plArr[i] = m_plArr[i];

  lOffset = m_lCount;
  m_lSwaps = 0;
  m_lComps = 0;
  m_lResets = 0;
  do {
    lOffset = (5 * lOffset) / 11;
    if (lOffset == 0) lOffset = 1;
    bInOrder = true;
    for (i = 0; i < (m_lCount - lOffset); i++) {
      j = i + lOffset;
      m_lComps++;
      if (plArr[i] > plArr[j]) {
        m_lSwaps++;
        bInOrder = false;
        lSwap = plArr[i];
        plArr[i] = plArr[j];
        plArr[j] = lSwap;
      }
    }

    // implement algorithm improvements
    if (bInOrder) m_lResets++;

    if (!bInOrder && lOffset == 1)
    {
      lOffset = m_lCount;
      for (long k = 0; k < m_lResets && lOffset > 1; k++) {
        lOffset = (5 * lOffset) / 11;
        if (lOffset == 0) lOffset = 1;
      }
    }
  } while (!(lOffset == 1 && bInOrder));
  delete [] plArr;
}

int main(int argc, char* argv[])
{
  const int MAX_ITER = 5;
  CExCombSort objSort;
  long lSizeArr[] = { 100, 250, 500, 1000, 2500, 5000, 10000,
                      25000, 50000, 0 };
  fstream fout("\\sort.dat", ios::out);
  fstream f1("\\sortCDD.dat", ios::out);
  fstream f2("\\sortDesCDD.dat", ios::out);
  char c[2];

  f1 << "N,Log(N),N*Log(N),Bubble # Comps,Bubble # Swaps,"
     << "CombSort #Comps,CombSort # Swaps,"
     << "ExCombSort #Comps,ExCombSort # Swaps, # Resets" << endl;

  f2 << "N,Log(N),Bubble # Comps,Bubble # Swaps,"
     << "CombSort #Comps,CombSort # Swaps,"
     << "ExCombSort #Comps,ExCombSort # Swaps" << endl;

  for (int nSizeIndex = 0; lSizeArr[nSizeIndex] > 0; nSizeIndex++)
  {
    cout << "Size = " << lSizeArr[nSizeIndex] << endl;
    fout << "Size = " << lSizeArr[nSizeIndex] << endl;

    for (int nIter = 1; nIter <= MAX_ITER; nIter++) {
      cout << "Iteration " << nIter << endl;
      fout << "Iteration " << nIter << endl;
      objSort.CreateRandArr(lSizeArr[nSizeIndex]);

      // start with bubble sort
      objSort.BubbleSort();
      cout << "Bubble Sort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps() << endl;
      fout << "Bubble Sort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps() << endl;
      f1 << lSizeArr[nSizeIndex] << ","
         << log10(lSizeArr[nSizeIndex]) << ","
         << lSizeArr[nSizeIndex] * log10(lSizeArr[nSizeIndex]) << ","
         << log10(objSort.getComps()) << ","
         << log10(objSort.getSwaps()) << ",";

      // perform CombSort
      objSort.CombSort();
      cout << "CombSort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps() << endl;
      fout << "CombSort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps() << endl;
      f1 << log10(objSort.getComps()) << ","
         << log10(objSort.getSwaps()) << ",";

      // perform ExCombSort
      objSort.ExCombSort();
      cout << "ExCombSort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps()
           << " Resets = " << objSort.getResets() << endl;
      fout << "ExCombSort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps()
           << " Resets = " << objSort.getResets() << endl;
      f1 << log10(objSort.getComps()) << ","
         << log10(objSort.getSwaps()) << ","
         << objSort.getResets() << endl;
    }
    cout << "Press Enter to continue";
    cin.getline(c, 1);
    cout << endl;
    fout << endl;
    // now do the special tests
    for (int i = 0; i < 2; i++) {
      switch (i) {
        case 0:
          cout << "Sorting descending array" << endl;
          fout << "Sorting descending array" << endl;
          objSort.CreateDescendArr(lSizeArr[nSizeIndex]);
          f2 << lSizeArr[nSizeIndex] << ","
             << log10(lSizeArr[nSizeIndex]) << ",";
          break;

        case 1:
          cout << "Sorting ascending array" << endl;
          fout << "Sorting ascending array" << endl;
          objSort.CreateAscendArr(lSizeArr[nSizeIndex]);
          break;
      }
      // use bubble sort
      objSort.BubbleSort();
      cout << "Bubble Sort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps() << endl;
      fout << "Bubble Sort " << " Comps = " << objSort.getComps()
         << " Swaps = " << objSort.getSwaps() << endl;
      if (i == 0)
        f2 << log10(objSort.getComps()) << ","
           << log10(objSort.getSwaps()) << ",";

      // perform CombSort
      objSort.CombSort();
      cout << "CombSort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps() << endl;
      fout << "CombSort " << " Comps = " << objSort.getComps()
         << " Swaps = " << objSort.getSwaps() << endl;
      if (i == 0)
        f2 << log10(objSort.getComps()) << ","
           << log10(objSort.getSwaps()) << ",";

      // perform ExCombSort
      objSort.ExCombSort();
      cout << "ExCombSort " << " Comps = " << objSort.getComps()
           << " Swaps = " << objSort.getSwaps()
           << " Resets = " << objSort.getResets() << endl;
      fout << "ExCombSort " << " Comps = " << objSort.getComps()
         << " Swaps = " << objSort.getSwaps()
         << " Resets = " << objSort.getResets() << endl;
      if (i == 0)
        f2 << log10(objSort.getComps()) << ","
           << log10(objSort.getSwaps()) << endl;
    }
    cout << "Press Enter to continue";
    cin.getline(c, 1);
    cout << endl << endl;
    fout << endl << endl;
  }
  fout.close();
  f1.close();
  f2.close();

  cout << "Press Enter to end the program";
  cin.getline(c, 1);
  return 0;
}

BACK

Copyright (c) Namir Shammas. All rights reserved.