PROGRAM 5


//  FILE_NAME:  PROGRAM5.CPP (SORTING)     AUTHOR:  ANTHONY F. ORTIZ
//  HEADER FILES.
#include 
#include 
#include 
#include 
#include 
//  OUTFILE.
ofstream FILEOUT;
//  DECLARATION FOR A CLASS CALLED SORTING.  INCLUDES INSERTION, SHELL
//  HEAP, MERGE, AND QUICK SORT ROUTINES.
template 
class SORTING
{
    public:
        //  INPUT THE ARRAY.
        INPUT_ARRAY (ETYPE INTEGER_ARRAY [], int SIZE);
        //  INSERTION SORT.
        INSERTION_SORT (ETYPE INTEGER_ARRAY [], int SIZE);
        //  FIND MINIMUM VALUE OF AN ARRAY.  USED FOR INSERTION
        //  SORT.
        MIN_VALUE (ETYPE INTEGER_ARRAY [], int SIZE);
        //  SHELL SORT.
        SHELL_SORT (ETYPE INTEGER_ARRAY [], int SIZE);
        //  HEAP SORT.
        HEAP_SORT (ETYPE HEAP_ARRAY [], ETYPE INTEGER_ARRAY [], int
         SIZE);
        //  DELETE THE MINIMUM VALUE IN THE HEAP.  USED FOR
        //  HEAP SORT.
        ETYPE DELETE_MIN (ETYPE HEAP_ARRAY [], int & SIZE2);
        //  BUILD THE HEAP.  USED FOR HEAP SORT.
        INSERT (ETYPE HEAP_ARRAY [], ETYPE X, int & SIZE2);
        //  MERGE SORT.
        MERGE_SORT (ETYPE INTEGER_ARRAY [],  int SIZE);
        //  USED WITH MERGE SORT.
        M_SORT (ETYPE INTEGER_ARRAY [], ETYPE TMP_ARRAY [], int LEFT,
         int RIGHT);
        //  USED WITH MERGE SORT.
        MERGE (ETYPE INTEGER_ARRAY [], ETYPE TMP_ARRAY [], int
         LEFT_POS, int RIGHT_POS, int RIGHT_END);
        //  QUICK SORT.
        QUICK_SORT (ETYPE A [], int N);
        //  USED WITH QUICK SORT.
        ETYPE & MEDIAN3 (ETYPE INTEGER_ARRAY [], int LEFT, int RIGHT);
        //  USED WITH QUICK SORT.
        Q_SORT (ETYPE INTEGER_ARRAY [], int LEFT, int RIGHT);
        //  SWAP TWO ELEMENTS.  USED WITH SEVERAL SORTING ROUTINES.
        SWAP (ETYPE A, ETYPE B);
        //  PRINT THE ARRAY.
        PRINT_ARRAY (ETYPE INTEGER_ARRAY [], int SIZE);
};
//  IMPLEMENTATION FOR A CLASS CALLED SORTING.
//  INPUT AN ARRAY OF INTEGERS FROM 0 TO 9999 USING THE RANDOM FUNCTION.
template 
SORTING  :: INPUT_ARRAY (ETYPE INTEGER_ARRAY [], int SIZE)
{
    randomize ();
    for (int I = 0; I < SIZE; I++)
    {
        INTEGER_ARRAY [I] = rand () % 10000;
    }
    return 0;
}
//  INSERTION SORT.
template 
SORTING  :: INSERTION_SORT (ETYPE INTEGER_ARRAY [], int SIZE)
{
    ETYPE TEMP;
    MIN_VALUE (INTEGER_ARRAY, SIZE);
    for (int P = 2; P <= SIZE; P++)
    {
        TEMP = INTEGER_ARRAY [P];
        for (int J = P; TEMP < INTEGER_ARRAY [J - 1]; J--)
        {
            INTEGER_ARRAY [J] = INTEGER_ARRAY [J - 1];
        }
        INTEGER_ARRAY [J] = TEMP;
    }
    return 0;
}
//  FIND THE MINIMUM VALUE OF THE ARRAY AND SWAP IT WILL THE FIRST ELEMENT
//  OF THE ARRAY.  USED WITH INSERTION SORT.
template 
SORTING  :: MIN_VALUE (ETYPE INTEGER_ARRAY [], int SIZE)
{
    ETYPE SMALLEST = INTEGER_ARRAY [0];
    int INDEX = 0;
    ETYPE TEMP;
    for (int I = 0; I <= SIZE; I++)
    {
        if (INTEGER_ARRAY [I] <= SMALLEST)
        {
            SMALLEST = INTEGER_ARRAY [I];
            INDEX = I;
        }
    }
    TEMP = INTEGER_ARRAY [0];
    INTEGER_ARRAY [0] = SMALLEST;
    INTEGER_ARRAY [INDEX] = TEMP;
    return 0;
}
//  SHELL SORT.
template 
SORTING  :: SHELL_SORT (ETYPE INTEGER_ARRAY [], int SIZE)
{
    ETYPE TEMP;
    for (int INCREMENT =  SIZE / 2; INCREMENT > 0; INCREMENT /= 2)
    {
        //  NOT INCREMENT + 1, INCREMENT.
        for (int I = INCREMENT; I <= SIZE; I++)
        {
            TEMP = INTEGER_ARRAY [I];
            //  NOT J > INCREMENT, J >= INCREMENT.
            for (int J = I; J >= INCREMENT; J -= INCREMENT)
            {
                if (TEMP < INTEGER_ARRAY [J - INCREMENT])
                {
                    INTEGER_ARRAY [J] =
                    INTEGER_ARRAY [J - INCREMENT];
                }
                else
                {
                    break;
                }
            }
            INTEGER_ARRAY [J] = TEMP;
        }
    }
    return 0;
}
//  HEAP SORT ROUTINE.
template 
SORTING  :: HEAP_SORT (ETYPE HEAP_ARRAY [], ETYPE INTEGER_ARRAY [],
                              int SIZE)
{
    HEAP_ARRAY [0] = -1;
    int SIZE2 = 0;
    for (int I = 1; I < SIZE; I++) //  BUILD HEAP.
    {
        INSERT (HEAP_ARRAY, HEAP_ARRAY [I], SIZE2);
    }
    for (I = 1; I < SIZE ; I++)   //  GET MINIMUM VALUE OF HEAP.
    {
        INTEGER_ARRAY [I] = DELETE_MIN (HEAP_ARRAY, SIZE2);
    }
    return 0;
}
//  BUILD THE HEAP.  USED WITH HEAP SORT.
template 
SORTING  ::
INSERT (ETYPE HEAP_ARRAY [], ETYPE X, int & SIZE2)
{
    unsigned int I;
    I = ++SIZE2;
    while (HEAP_ARRAY [I / 2] > X)
    {
        HEAP_ARRAY [I] = HEAP_ARRAY [I / 2];
        I /= 2;
    }
    HEAP_ARRAY [I] = X;
    return 0;
}
//  DELETE THE MINIMUM VALUE FROM THE HEAP.  USED WITH HEAP SORT.
template 
ETYPE
SORTING  ::
DELETE_MIN (ETYPE HEAP_ARRAY [], int &SIZE2)
{
    unsigned int CHILD;
    ETYPE MIN_ELEMENT, LAST_ELEMENT;
    MIN_ELEMENT = HEAP_ARRAY [1];
    LAST_ELEMENT = HEAP_ARRAY [SIZE2--];
    for (int I = 1; I * 2 <= SIZE2; I = CHILD)
    {
        //  FIND SMALLER CHILD.
        CHILD = I * 2;
        if (CHILD != SIZE2)
            if (HEAP_ARRAY [CHILD + 1] < HEAP_ARRAY [CHILD])
                CHILD++;
        //  PERCOLATE ONE LEVEL.
        if (LAST_ELEMENT > HEAP_ARRAY [CHILD])
            HEAP_ARRAY [I] = HEAP_ARRAY [CHILD];
        else
            break;
    }
    HEAP_ARRAY [I] = LAST_ELEMENT;
    return MIN_ELEMENT;
}
//  MERGE SORT.
template 
SORTING  :: MERGE_SORT (ETYPE INTEGER_ARRAY [], int SIZE)
{
    ETYPE * TMP_ARRAY = new ETYPE [SIZE];
    unsigned int NEW_N = SIZE; //  NON-CONSTANT, FOR M-SORT.
    if (TMP_ARRAY != 0)
    {
        //  NOT 1, 0.
        M_SORT (INTEGER_ARRAY, TMP_ARRAY, 0, NEW_N);
        delete [] TMP_ARRAY;
    }
    else
    {
        cout << "ERROR, NO SPACE FOR TMP ARRAY.";
    }
    return 0;
}
//  USED BY MERGE SORT ROUTINE.
template 
SORTING  :: M_SORT (ETYPE INTEGER_ARRAY [], ETYPE TMP_ARRAY [], int
 LEFT, int RIGHT)
{
    if (LEFT < RIGHT)
    {
        int CENTER = (LEFT + RIGHT) / 2;
        M_SORT (INTEGER_ARRAY, TMP_ARRAY, LEFT, CENTER);
        M_SORT (INTEGER_ARRAY, TMP_ARRAY, CENTER + 1, RIGHT);
        MERGE (INTEGER_ARRAY, TMP_ARRAY, LEFT, CENTER + 1, RIGHT);
    }
    return 0;
}
//  USED BY MERGE SORT ROUTINE.
//  LEFT_POS = START OF LEFT HALF.
//  RIGHT_POS = START OF RIGHT HALF.
template 
SORTING  :: MERGE (ETYPE INTEGER_ARRAY [], ETYPE TMP_ARRAY [], int
 LEFT_POS, int RIGHT_POS, int RIGHT_END)
{
    int LEFT_END = RIGHT_POS - 1;
    int TMP_POS = LEFT_POS;
    int NUM_ELEMENTS = RIGHT_END - LEFT_POS + 1;
    //  MAIN LOOP.
    while (LEFT_POS <= LEFT_END && RIGHT_POS <= RIGHT_END)
    {
        if (INTEGER_ARRAY [LEFT_POS] <= INTEGER_ARRAY [RIGHT_POS])
        {
            TMP_ARRAY [TMP_POS++] = INTEGER_ARRAY [LEFT_POS++];
        }
        else
        {
            TMP_ARRAY [TMP_POS++] = INTEGER_ARRAY [RIGHT_POS++];
        }
    }
    while (LEFT_POS <= LEFT_END)    //  COPY REST OF FIRST HALF.
    {
        TMP_ARRAY [TMP_POS++] = INTEGER_ARRAY [LEFT_POS++];
    }
    while (RIGHT_POS <= RIGHT_END)  //  COPY REST OF SECOND HALF.
    {
        TMP_ARRAY [TMP_POS++] = INTEGER_ARRAY [RIGHT_POS++];
    }
    //  COPY TMP_ARRAY BACK.
    for (int I = 1; I <= NUM_ELEMENTS; I++, RIGHT_END--)
    {
        INTEGER_ARRAY [RIGHT_END] = TMP_ARRAY [RIGHT_END];
    }           \
    return 0;
}
//  QUICK SORT.
template 
SORTING  :: QUICK_SORT (ETYPE INTEGER_ARRAY [], int SIZE)
{
    //  NOT 1, 0.
    int ONE = 0;
    Q_SORT (INTEGER_ARRAY, ONE, SIZE);
    INSERTION_SORT (INTEGER_ARRAY, SIZE);
    return 0;
}
//  USED BY QUICK SORT ROUTINE.
template 
ETYPE &
SORTING  :: MEDIAN3 (ETYPE INTEGER_ARRAY [], int LEFT, int RIGHT)
{
    int CENTER = (LEFT + RIGHT) / 2;
    if (INTEGER_ARRAY [LEFT] > INTEGER_ARRAY [CENTER])
    {
        SWAP (INTEGER_ARRAY [LEFT], INTEGER_ARRAY [CENTER]);
    }
    if (INTEGER_ARRAY [LEFT] > INTEGER_ARRAY [RIGHT])
    {
        SWAP (INTEGER_ARRAY [LEFT], INTEGER_ARRAY [RIGHT]);
    }
    if (INTEGER_ARRAY [CENTER] > INTEGER_ARRAY [RIGHT])
    {
        SWAP (INTEGER_ARRAY [CENTER], INTEGER_ARRAY [RIGHT]);
    }
    //  INVARIANT: A [LEFT] <= A [CENTER] <= A [RIGHT]
    //  NOW HIDE AND RETURN PIVOT.
    SWAP (INTEGER_ARRAY [CENTER], INTEGER_ARRAY [RIGHT - 1]);
    return INTEGER_ARRAY [RIGHT - 1];
}
//  USED BY QUICK SORT ROUTINE.
template 
SORTING  :: Q_SORT (ETYPE INTEGER_ARRAY [], int LEFT, int RIGHT)
{
    //  CUTOFF NOT DECLARED, SHOULD BE DECLARED.
    //  CUTOFF NOT INITIALIZED, SHOULD BE INITIALIZED.
    //  BOOK RECOMMENDS 20 FOR CUTOFF.
    int CUTOFF = 20;
    if (LEFT + CUTOFF <= RIGHT)
    {
        ETYPE PIVOT = MEDIAN3 (INTEGER_ARRAY, LEFT, RIGHT);
        int I = LEFT;
        int J = RIGHT - 1;
        for ( ;;)
        {
            while (INTEGER_ARRAY [++I] < PIVOT);
            while (INTEGER_ARRAY [--J] > PIVOT);
            if (I < J)
            {
                SWAP (INTEGER_ARRAY [I], INTEGER_ARRAY [J]);
            }
            else
            {
                break;
            }
        }
        SWAP (INTEGER_ARRAY [I], INTEGER_ARRAY [RIGHT - 1]);
          //  RESTORE PIVOT.
        Q_SORT (INTEGER_ARRAY, LEFT, I - 1);
        Q_SORT (INTEGER_ARRAY, I + 1, RIGHT);
    }
    return 0;
}
//  USED BY QUICK SORT ROUTINE.
template 
SORTING  :: SWAP (ETYPE A, ETYPE B)
{
    ETYPE TEMP = A;
    A = B;
    B = TEMP;
    return 0;
}
//  PRINT THE UNSORTED OR SORTED ARRAY.
template 
SORTING  :: PRINT_ARRAY (ETYPE INTEGER_ARRAY [], int SIZE)
{
    int COUNT = 0;
    for (int I = 0; I < SIZE; I++)
    {
        FILEOUT << setw (8) << INTEGER_ARRAY [I];
        COUNT = COUNT + 1;
        if (COUNT % 10 == 0)
        {
            FILEOUT << "\n";
        }
    }
    return 0;
}

//  INPUT 5 NUMBERS, SORT THEM USING INSERTION SORT, AND PRINT THEM.
int main ()
{
    SORTING  SORT;
    int INT_ARRAY [5];
    int SIZE = 5;
    FILEOUT.open ("SORT.OUT", ios :: out);
    SORT.INPUT_ARRAY (INT_ARRAY, SIZE);
    FILEOUT << "BEFORE SORT\n";
    SORT.PRINT_ARRAY (INT_ARRAY, SIZE);
    SORT.INSERTION_SORT (INT_ARRAY, SIZE);
    FILEOUT << "\nAFTER SORT\n";
    SORT.PRINT_ARRAY (INT_ARRAY, SIZE);
    FILEOUT.close ();
    return 0;
}

//  OUTFILE:  SORT.OUT

BEFORE SORT
    6599    6245    7964    1232    4156
AFTER SORT
     170    1232    4156    6245    6599




BACK TO CS3240 PAGE.