🚀 go-pugleaf

#include <stdio.h>
#include <math.h>

//#include "CACMrandom.h"
float CACMrandom(void);

enum boolean {FALSE, TRUE};

class ARRAY {
  private:
    int *array;
    int size;

  public: //protected:
    void Randomize(void);
    boolean Ordered(void);
    void Dump(void);

    void StraightInsertionSort(void);
    void StraightBinaryInsertionSort(void);
    void StraightSelectionSort(void);
    void BubbleSort(void);
    void ShakerSort(void);
    void ShellSort(void);
    void HeapSort(void); void Heapify(int i, int j);
    void QuickSort(void); void QSort(int left, int right);
    void MergeSort(void); void Msort(int i, int j); void Merge(int i, int m, int j);
    void MergeExchangeSort(void);

    typedef void (ARRAY::* sortSig)(void) ;
    ARRAY(sortSig mySort, int size=128) {array = new int[size]; sort = mySort; };
    void SelectSort(void) {
        if      (0  <= size && size <= 50  ) sort = &ARRAY::StraightInsertionSort; 
        else if (51 <= size && size <= 5000) sort = &ARRAY::ShellSort; 
        else                                 sort = &ARRAY::QuickSort; 
    };
    void CheckAllSorts(void);

  public:
    sortSig sort;

    ARRAY(int size=128) {
        ARRAY::size = size;
        array = new int[size];
        SelectSort();
    };
};


void
ARRAY::Randomize(void) {
    int i;
    for (i=0; i<size; i++)
        array[i] = i;
    for (i=0; i<size; i++) {
        long x = long(CACMrandom() * float(size));
        long y = long(CACMrandom() * float(size));
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}

boolean
ARRAY::Ordered(void) {
    int i;
    for (i=0; i<size; i++) 
        if (array[i] != i) return FALSE;
    return TRUE;
}

void
ARRAY::Dump(void) {
    int i;
    for (i=0; i<size; i++) {
        printf("array[%2d] is %2d. \n", i, array[i]);
    } 
}

void 
ARRAY::CheckAllSorts(void) {
    static sortSig AllSorts[] = {
        &ARRAY::StraightInsertionSort,
        &ARRAY::StraightBinaryInsertionSort
    };
    int i;

    for (i=0; i<2; i++) {
        Randomize();
        AllSorts[i]();
    }
}

// .25N**2 comparisons and .25N**2moves
void
ARRAY::StraightInsertionSort(void) {
    int i, j, temp, insert;
    for (i=1; i<size; i++) {
        temp = array[i];
        insert = i;
        for (j=i-1; j>=0 && temp < array[j]; j--) {
            array[j+1] = array[j];
            insert--;
        }
        array[insert] = temp;
    }
}

// N*log2(N) comparisons and .25n**2moves
void 
ARRAY::StraightBinaryInsertionSort(void) {
    int i, j, temp, l, r, m;
    for (i=1; i<size; i++) {
        temp = array[i];
        l = 0;
        r = i-1;
        while (l <= r) {
            m = (l + r)/2;
            if (temp < array[m]) r = m - 1;
            else                 l = m + 1;
        }
        for (j=i-1; j>=l; j--)
            array[j+1] = array[j];
        array[l] = temp;
    }
}

void 
ARRAY::StraightSelectionSort(void) {
    int i, j, k;
    for (i=0; i<size-1; i++) {
        k = i;
        for (j=i+1; j<size; j++) {
            if (array[j] < array[k])
                k = j;
        }
        if (k != i) {
            int temp = array[k];
            array[k] = array[i];
            array[i] = temp;
        }
    }   
}

void 
ARRAY::BubbleSort(void) {
    int i, j;
    for (i=1; i<size-1; i++)
        for (j=size-1; j>=i; j--)
            if (array[j-1] > array[j]) {
                int temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
            }
}

void 
ARRAY::ShakerSort(void) {
    int j, k, l, r;
    l = 1;
    r = k = size - 1;
    do {
        for (j=r; j>=l; j--) {
            if (array[j-1] > array[j]) {
                int temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
                k = j;
            }
        }
        l = k + 1;
        for (j=l; j<=r; j++) {
            if (array[j-1] > array[j]) {
                int temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
                k = j;
            }
        }
        r = k - 1;
    } while (l<=r);
}

// N**1.3 or ~ N(log2(N))**2
void 
ARRAY::ShellSort(void) {  // insertion sort by diminishing intervals
    int i, j, k, interval, temp, insert, intervalNum;
    for (intervalNum=int(log(double(size))/log(2.0)); intervalNum>=1; intervalNum--) {
        interval = int(pow(2.0, double(intervalNum))) - 1;
        for (i=0; i<=interval-1; i++) {
            for (j=i+interval; j<=size-1; j+=interval) {
                temp = array[j];
                insert = j;
                for (k=j-interval; k>=0 && array[k] > temp; k-=interval) {
                    array[k+interval] = array[k];
                    insert = k;
                }
                array[insert] = temp;
            }
        }
    }
}

// N*log2(N) : average and worst case
void 
ARRAY::Heapify(int i, int j) { // heap => array[root] > array[either son]
    int leftSon, rightSon, k;
    leftSon = i*2 + 1;
    rightSon = i*2 +2;
    if (leftSon <= j) {
        if (rightSon <= j) {
            if (array[leftSon] > array[rightSon]) k = leftSon;
            else                                  k = rightSon;
        } else                                    k = leftSon;
        if (array[k] > array[i]) {
            int temp = array[i];
            array[i] = array[k];
            array[k] = temp;
            Heapify(k, j);
        }
    }
}

void 
ARRAY::HeapSort(void) {
    int i;
    for (i=size-1; i>=0; i--) 
        Heapify(i, size-1);
    for (i=size-1; i>=1; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        Heapify(0, i-1);
    }
}

// N*log2(N) : average ; N**2 : worst case (already ordered)
void 
ARRAY::QSort(int left, int right) {
    int i, j, x;
    i = left;
    j = right;
    x = array[ (left+right)/2 ];
    do {
        while (array[i] < x) i++;
        while (x < array[j]) j--;
        if (i <= j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    } while (i <= j);
    if (left < j) 
        QSort(left, j);
    if (i < right) 
        QSort(i, right);
}

void 
ARRAY::QuickSort(void) {
    QSort(0, size-1);
}

// needs an axillary array of size N 
// N*log2(N) : average and worst case
int *AUXarray;

void 
ARRAY::Merge(int i, int m, int j) {
    int k, index1, index2, n;
    k = i;
    index1 = i;
    index2 = m + 1;
    while ((index1 <= m) && (index2 <= j)) {
        if (array[index1] < array[index2])
            AUXarray[k++] = array[index1++];
        else 
            AUXarray[k++] = array[index2++];
    }
    if (index1 <= m)
        while (index1 <= m)
            AUXarray[k++] = array[index1++];
    else if (index2 <= j)
        while (index2 <= j)
            AUXarray[k++] = array[index2++];

    for (k=i; k<=j; k++)
        array[k] = AUXarray[k];
}

void 
ARRAY::Msort(int i, int j) {
    int m;
    if (i != j) {
        m = (i + j)/2;
        Msort(i, m);
        Msort(m+1, j);
        Merge(i, m, j);
    }
} 

void 
ARRAY::MergeSort(void) {
    AUXarray = new int[size];
    Msort(0, size-1);
}

    
void 
ARRAY::MergeExchangeSort() { // Batcher's parallel sort
    int t, t0, p, q, r, d, i ;

    for (t = t0 = int(ceil(log(double(size))/log(2.0))); t>0; t--) {
        p=int(pow(2.0, double(t-1)));
        q = int(pow(2.0, double(t0-1)));
        r = 0;
        d = p;
        while (1) {
            for (i=0; i < size - d; i++) { 
                if ((i & p) == r) { // each selected i can "campare and exchange" in parallel
                    if (array[i] > array[i+d]) {
                        int temp = array[i];
                        array[i] = array[i+d];
                        array[i+d] = temp;
                    } 
                }
            }
            if (p == q) break;
            d = q - p;
            q = q / 2;
            r = p;
        }
    }
}


int
main()
{
    ARRAY ARRAYobject(16);
    ARRAYobject.Randomize();
    ARRAYobject.Dump();
    ARRAYobject.MergeExchangeSort();
    if (ARRAYobject.Ordered())
        printf("Array is ordered.\n");
    else {
        printf("Array is not ordered.\n");
        ARRAYobject.Dump();
    }
}

-- 
bwest@cs.utexas.edu
============================================================================
STANDARD DISCLAIMER: No one is responsible. 
My Astral-Projection did this, if you get my drift.