Algorithm Alley
by Mingfu Gong


Example 1
gsort1() running time <= gLoop*N/2 + 2*gLoop*N*log(N)/log(N2/N1).

Example 2
gsort2() running time <= (gLoop+2)*N/2 + 2*N*log(N)/log(N2/N1) +
2*(gLoop-1)*N*log(log(N))/log(N2/N1).

Example 3
1/2 < GNDR <= 2/3


Listing One
// adaptive group sort - 1: running time <= gLoop*N/2 + 
//                                     2*gLoop*N*log(N)/log(N2/N1).
long gsort1(long *array, long N, long N1, long N2) {
       long numGroup; // number of groups
       long gLoop = 0; // number of AGS loops
       do { // AGS loop
         numGroups = N ;
         while (numGroups > 1) { // group-sort loop
            // update numGroup
            numGroup = numGroup * N1 / N2;

           for (i = 0; i < N-numGroup; i++) { //bidirectional bubble-sort loop
              cmprSwap2(array[i], array[i+numGroup]);
              cmprSwap2(array[N-1-i-numGroup], array[N-1-i]);
           }
        }
        gLoop++;
      } while (!isSortedArray(array, N));
      return gLoop;
}

Listing Two
//adaptive group sort - 2:  running time <= (gLoop+2)*N/2 + 
//              2*N*log(N)/log(N2/N1) + 2*(gLoop-1)*N*log(log(N))/log(N2/N1).
long gsort2(long *array, long N, long N1, long N2) {
       long maxNumGroup; // maximum group number
       long numGroup; // number of groups
       long divider;  // to calculate numGroup
       long oldDivider; // to calculate numGroup
       long gLoop = 0; // number of AGS loops
       long i;
       // pre-process to reduce number of swaps;
       maxNumGroup = N / 2;
       for ( i = 0; i < maxNumGroup; i++ ) {
           cmprSwap2(array[i], array[N-1-i]);
       }
       maxNumGroup = N;
       while (!isSortedArray(array, N)) { // AGS loop
            gLoop++;
            numGroups = maxNumGroup;
            oldDivider = divider = 1;
            while (numGroups > 1) { // group-sort loop
                // update numGroup
                divider = divider * N2 / N1;
                if (divider == oldDivider) divider++;
                oldDivider = divider;
                numGroup = maxNumGroup / divider;
                if (0 == numGroup) numGroup = 1;
                for (i = 0; i < N - numGroup; i++) { // bidirectional 
                                                     //    bubble-sort loop
                    cmprSwap2(array[i], array[i+numGroup]);
                    cmprSwap2(array[N-1-i-numGroup], array[N-1-i]);
                }
           }
           maxNumGroup = log(N); //reset maxNumGroup;
      }
      return gLoop;
}

Listing Three
//adaptive group sort - 3
long gsort2(long *array, long N, long N1, long N2) {
       long maxNumGroup; // maximum group number
       long numGroup; // number of groups
       long divider;  // to calculate numGroup
       long oldDivider; // to calculate numGroup
       long gLoop = 0; // number of AGS loops
       long i;
       // pre-process to reduce number of swaps;
       maxNumGroup = N / 2;
       for ( i = 0; i < maxNumGroup; i++ ) {
           cmprSwap2(array[i], array[N-1-i]);
       }
       maxNumGroup = N;
       while (!isSortedArray(array, N)) { // AGS loop
            gLoop++;
            numGroups = maxNumGroup;
            oldDivider = divider = 1;
            while (numGroups > 1) { // group-sort loop
                // update numGroup
                divider = divider * N2 / N1;
                if (divider == oldDivider) divider++;
                oldDivider = divider;
                numGroup = maxNumGroup / divider;
                if (0 == numGroup) numGroup = 1;
                if (numGroup < 2*log(N)) { //reset GNDR
                      N1 = 2; N2 = 3;
                }
                for (i = 0; i < N - numGroup; i++) { // bidirectional 
                                                     //    bubble-sort loop
                    cmprSwap2(array[i], array[i+numGroup]);
                    cmprSwap2(array[N-1-i-numGroup], array[N-1-i]);
                }
           }
           maxNumGroup = log(N); //reset maxNumGroup;
      }
      return gLoop;
}


Listing Four
// similar interface as qsort(); Depends on compiler, template normally
//                                    slower than simular C/C++ functions.
template <class T> void gsort(T *array, int arraySize, 
                            int (*ComparisonPointer)(const T*, const T*))
{
    T tmp;
    int maxStep;         // maximum group number
    int step;            // number of groups
    int divider;         // to calculate step
    int oldDivider;      // to calculate step
    int logN;
    int i, j;
    int N1, N2;
    boolean firstSet = TRUE;

    if (NULL == array || 1 >= arraySize ) return;
    if (sizeof(T) >= 8) { //set GNDR by swaping cost.
        N1 = 2; N2 = 3;
    } else {
        N1 = 5; N2 = 9;
    }
    // pre-processing;
    maxStep = arraySize / 2;
    for (i = 0, j = arraySize-1; i < maxStep; i++, j--) {
        if (ComparisonPointer(&array[i], &array[j]) > 0) {
          tmp = array[i];
          array[i] = array[j];
          array[j] = tmp;
        }
    }
    if (2 == arraySize)  return;

    logN = (int) (log((double)arraySize));
    if (logN < 2) logN = 2;

    maxStep = arraySize;
    while (TRUE) { //AGS loop;
        for (i = arraySize - 2; i >= 0; i--) { //isSortedArray();
          if (ComparisonPointer(&array[i], &array[i+1]) > 0) break;
        }
        if (0 >= i) break; // is sorted array;

        step = maxStep;
        oldDivider = divider = 1;
        while (step > 1) { // group-sort loop;
          divider = (divider * N2) / N1;
          if (divider == oldDivider) divider++;
          oldDivider = divider;
          step = maxStep / divider;
          if (firstSet && step <= 2*logN) { // reset GNDR = 2/3
            firstSet = FALSE;
            N1 = 2; N2 = 3;
          }
          if (0 == step) step = 1;
          for (i = 0, j = arraySize-1; i < maxStep; i++, j--)  
                                // bidirection bubble-sort for each group;
            if (ComparisonPointer(&array[i], &array[i+step]) > 0) {
              tmp = array[i];
              array[i] = array[i+step];
              array[i+step] = tmp;
            }
            if (ComparisonPointer(&array[j-step], &array[j]) > 0) {
              tmp = array[j-step];
              array[j-step] = array[j];
              array[j] = tmp;
            }
          }
        }
        maxStep = logN;
    }
}

Listing Five
//################################################################
// Test program for Adaptive Group Sort (AGS) algorithm statistic analysis.
// 05/04/98 M. Gong - initial code.
//################################################################
long gsort2(long *array, long arraySize, long n1, long n2);
long gsort3(long *array, long arraySize, long n1, long n2);
//
static long numCmpr, numSwap;
//
static short cmprSwap2(long &smaller, long &larger);
static short isSortedArray(long *array, long arraySize);
static void biDirectionGroupSort(long *array, long arraySize, long step,
long loops);
//for test
static void initArray(long *array, long N);
static void swap(long &l1, long &l2);
int main(int argc, char **argv);
//
int main(int argc, char **argv)
{
    long minloop, maxloop, avrloop;
    long mincmpr, maxcmpr;
    long minswap, maxswap;
    double avrswap, avrcmpr;
    long gsortLoops;
    double avrf, minf, maxf;
    double loopf;
    double nlogn;
    double logN;
    long n1, n2;
    long seed1, seed2, arraySize, n;
    long *array = NULL;

    if (argc <6) {
            printf("usage: %s arraySize seedStart seedEnd n1 n2\n", argv[0]);
            return FALSE;
    }
    arraySize = atoi(argv[1]);
    seed1 = atoi(argv[2]);
    seed2 = atoi(argv[3]);
    n1 = atoi(argv[4]);
    n2 = atoi(argv[5]);
    logN = log((double)arraySize) / log(2.0);

    if (seed1 > seed2) swap(seed1, seed2);
    printf("****** adaptive group sort: numCmpr = K * N * log2(N); 
                                        numSwap = S * N * log2(N);\n");
    printf(" seed1 = %d; seed2 = %d; N = %d; n1 = %d; n2 = %d; 
              log2(N) = %.3f;\n", seed1, seed2, arraySize, n1, n2, logN);
    minloop = 0x7FFFFFFF; maxloop = 0; avrloop = 0;
    mincmpr = 0x7FFFFFFF; maxcmpr = 0, avrcmpr = 0;
    minswap = 0x7FFFFFFF; maxswap = 0; avrswap = 0;
    array = new long[arraySize];
    if (NULL == array) return FALSE;

    for(n = seed1; n <= seed2; n++) {
            numCmpr = 0; numSwap = 0;
            srand(n);
            initArray(array,arraySize);
            gsortLoops = gsort2((long*)array, arraySize, n1, n2);

            if (minloop > gsortLoops) minloop = gsortLoops;
            if (maxloop < gsortLoops) maxloop = gsortLoops;
            avrloop += gsortLoops;
            if (mincmpr > numCmpr) mincmpr = numCmpr;
            if (maxcmpr < numCmpr) maxcmpr = numCmpr;
            avrcmpr += ((float) numCmpr) / (float)(seed2 - seed1 +1);
            if (minswap > numSwap) minswap = numSwap;
            if (maxswap < numSwap) maxswap = numSwap;
            avrswap += ((float) numSwap) / (float)(seed2 - seed1 +1);
    }
    loopf = (double) (seed2 - seed1 +1);
    nlogn = logN * ((double)arraySize);

    avrf= ((double)avrloop) / loopf;
    printf("\tmin : max : average loop = %d : %d : 
                                     %.3f\n", minloop, maxloop, avrf);
    avrf = avrcmpr / nlogn;
    minf = ((double)mincmpr) / nlogn;
    maxf = ((double)maxcmpr) / nlogn;
    printf("\tmin : max : average K = %.3f : %.3f : 
                                      %.3f\n", minf, maxf, avrf);
    avrf = avrswap / nlogn;
    minf = ((double)minswap) / nlogn;
    maxf = ((double)maxswap) / nlogn;
    printf("\tmin : max : average S = %.3f : %.3f : 
                                      %.3f\n", minf, maxf, avrf);
    delete [] array;
    return TRUE;
}
//
static void initArray(long *array, long N)
{
    long i;
    for (i = 0; i < N; i++) {
            array[i] = (long) rand();
    }
}
//
static void swap(long &l1, long &l2)
{
    long tmp = l1;
    l1 = l2; l2 = tmp;
}
//reset maxStep = logN after the first AGS loop;
long gsort2(long *array, long arraySize, long N1, long N2)
{
    long maxStep; // maximum group number
    long step; // number of groups
    long divider; // to calculate step
    long oldDivider; // to calculate step
    long i;
    long gsortloops = 0;
    long logN;

    if (1 >= arraySize) return 0;
    if (2 == arraySize) {
            cmprSwap2(array[0], array[1]);
            return 0;
    }
    if (N1 > N2) swap(N1, N2);
    else if (N1 == N2) {
            N1 = 2; N2 = 3;
    }
    maxStep = arraySize / 2;
    for (i = 0; i < maxStep; i++) { // pre-processing
            cmprSwap2(array[i], array[arraySize-1-i]);
    }
    logN = (long) (log((double)arraySize));
    maxStep = arraySize;
    while (!isSortedArray(array, arraySize)) { // AGS Loop
        step = maxStep;
        oldDivider = divider = 1;
        while (step > 1) { // group-sort loop
                divider = (divider * N2) / N1;
                if (divider == oldDivider) divider++;
                oldDivider = divider;
                step = maxStep / divider;
                if (0 == step) step = 1;
                biDirectionGroupSort(array, arraySize, step, 0);
        }
        gsortloops++;
        maxStep = logN;
        if (maxStep < 2) maxStep = 2;
    }
    return gsortloops;
}
//reset maxStep = logN after the first AGS loop;
//reset GNDR to 2/3 when step < logN;
long gsort3(long *array, long arraySize, long N1, long N2)
{
    long maxStep; // maximum group number
    long step; // number of groups
    long divider; // to calculate step
    long oldDivider; // to calculate step
    long i;
    long gsortloops = 0;
    long logN;

    if (1 >= arraySize) return 0;
    if (2 == arraySize) {
            cmprSwap2(array[0], array[1]);
            return 0;
    }
    if (N1 > N2) swap(N1, N2);
    else if (N1 == N2) {
            N1 = 2; N2 = 3;
    }
    maxStep = arraySize / 2;
    for (i = 0; i < maxStep; i++) { // pre-processing
            cmprSwap2(array[i], array[arraySize-1-i]);
    }
    logN = (long) (log((double)arraySize));

    maxStep = arraySize;
    while (!isSortedArray(array, arraySize)) { // AGS Loop
            step = maxStep;
            oldDivider = divider = 1;
            while (step > 1) { // group-sort loop
                    divider = (divider * N2) / N1;
                    if (divider == oldDivider) divider++;
                    oldDivider = divider;
                    step = maxStep / divider;
                    if (step <= 2*logN) { // reset GNDR = 2/3
                            N1 = 2; N2 = 3;
                    }
                    if (0 == step) step = 1;
                    biDirectionGroupSort(array, arraySize, step, 0);
            }
            gsortloops++;
            maxStep = logN;
            if (maxStep < 2) maxStep = 2;
    }
    return gsortloops;
}
//bidirection bubble-sort for each group
static void biDirectionGroupSort(long *array, long arraySize, long step,
long loops)
{
    long i;
    long maxIndex, lastIndex;
    lastIndex = arraySize - 1;
    maxIndex = arraySize - step - loops;
    for (i = loops; i < maxIndex; i++) { // bi-directional group sort
            cmprSwap2(array[i], array[i+step]);
            cmprSwap2(array[lastIndex-i-step], array[lastIndex-i]);
    }
}
//return TRUE if swapped
static short cmprSwap2(long &smaller, long &larger)
{
    numCmpr++;
    if (smaller > larger) {
            long tmp = smaller;
            smaller = larger;
            larger = tmp;
            numSwap++;
            return 1;
    }
    return 0;
}
//return TRUE if array is sorted
static short isSortedArray(long *array, long arraySize)
{
    arraySize--;
    for (long i = 0; i < arraySize; i++) {
            if (cmprSwap2(array[i], array[i+1]) > 0) return 0;
    }
    return 1;
}










9