Subversion Repositories programming

/* Written by: Ira Snyder
 * Started on: 05-20-2005
 * Due Date: 06-10-2005
 * CS331 Project #2
 */


/* standard headers */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* broken-out code for common things */
#include "sorts.c"
#include "timing.c"
#include "arrays.c"


/* function prototypes */
void randomfill (int array[], unsigned long size);
int kth_smallest_method1 (int src_array[], unsigned long size, unsigned long position);
int kth_smallest_method2 (int src_array[], unsigned long size, unsigned long position);
int kth_smallest_method3 (int src_array[], unsigned long size, unsigned long position);
int kth_smallest_method4 (int src_array[], unsigned long size, unsigned long position);


int main (void)
{
    /* create new random seed */
    srand((unsigned)time(NULL));

    unsigned long size, kth_pos;
    int *array;
    int stop_looping, i;
    
    size = 10; /* set initial size to 10 */
    stop_looping = 0; /* FALSE */

    while ( !stop_looping )
    {
        /* create and fill an array with random values */
        array = create_array (size);
        randomfill (array, size);

        for (i=0; i<5; i++)
        {
            /* choose the kth position based on the handout */
            if (i==0)
                kth_pos=0;
            else if (i==1)
                kth_pos=size/4;
            else if (i==2)
                kth_pos=size/2;
            else if (i==3)
                kth_pos=3*size/4;
            else
                kth_pos=size-1;

            /* header */
            printf ("Running with size=%lu (%.3fMB) kth_pos=%lu...\n",
                    size, (size*4.0)/(1024*1024), kth_pos);
        
            /* run method1 */
            startclock();
            printf ("%luth smallest (method1): %d -- ", kth_pos, 
                    kth_smallest_method1 (array, size, kth_pos));
            stopclock();
            printtimetaken("Method1");

            /* run method2 */
            startclock();
            printf ("%luth smallest (method2): %d -- ", kth_pos, 
                    kth_smallest_method2 (array, size, kth_pos));
            stopclock();
            printtimetaken("Method2");

            /* run method3 */
            startclock();
            printf ("%luth smallest (method3): %d -- ", kth_pos, 
                    kth_smallest_method3 (array, size, kth_pos));
            stopclock();
            printtimetaken("Method3");
            
            /* run method4 */
            startclock();
            printf ("%luth smallest (method4): %d -- ", kth_pos, 
                    kth_smallest_method4 (array, size, kth_pos));
            stopclock();
            printtimetaken("Method4");
            
            /* some blank lines for spacing */
            printf ("\n\n");
        }
        
        /* free the memory that was allocated for the array */
        array = free_array (array);
        
        /* choose size according to the Project #2 handout */
        if (size < 10)
            size = 10;
        else if (size < 50)
            size = 50;
        else if (size < 100)
            size = 100;
        else if (size < 250)
            size = 250;
        else
            size *= 2;

        /* if we grow above 1 billion elements, stop looping */
        if (size > 1000000000)
            stop_looping = 1; /* TRUE */

    } /* end while loop */

    return 0;
}

/* fill the array with random numbers in
 * the range 0-32767 */
void randomfill (int array[], unsigned long size)
{
    unsigned long i;
        
    for (i=0; i<size; i++)
        array[i] = rand() % 32768;
}

/* Find the kth smallest element in the array (starting from zero)
 *
 * This uses the method of sorting the list, then picking
 * the correct element */
int kth_smallest_method1 (int src_array[], unsigned long size, 
        unsigned long position)
{
    int *array;
    int retval;

    array = create_array (size);
    copyarray (src_array, array, size);
    
    mergesort (array, size);

    retval = array[position];
    array = free_array (array);
    
    return retval;
}

/* Find the kth smallest element in the array (starting from zero)
 *
 * This uses the method of calling partiton() from quicksort, and
 * throwing out data that is unneeded */
int kth_smallest_method2 (int src_array[], unsigned long size, unsigned long position)
{
    int *array;
    int retval;
    unsigned long left = 0;
    unsigned long right = size-1;
    unsigned long pivotpos;
    
    array = create_array (size);
    copyarray (src_array, array, size);

    do
    {
        swap (&array[position], &array[left]);
        pivotpos = partition (array, left, right);

        if (pivotpos < position)
            left = pivotpos + 1;
        else /* pivotpos >= position) */
            right = pivotpos - 1;
    }
    while (pivotpos != position);

    retval = array[position];
    array = free_array (array);
    
    return retval;
}

/* Find the kth smallest element in the array (starting from zero)
 *
 * This uses the method of calling partiton() from quicksort, and
 * throwing out data that is unneeded
 *
 * NOTE: This is a recursive version of the algorithm above (kth_smallest_method2) */
int kth_smallest_method3 (int src_array[], unsigned long size, unsigned long position)
{
    int *array;
    int *temparray;
    int retval;
    unsigned long left = 0;
    unsigned long right = size-1;
    unsigned long pivotpos, newpos;

    array = create_array (size);
    copyarray (src_array, array, size);

    swap (&array[position], &array[left]);
    pivotpos = partition (array, left, right);

    /* base case */
    if (pivotpos == position)
    {
        retval = array[position];
        array = free_array (array);

        return retval;
    }
    
    /* throw away left side */
    if (pivotpos < position)
    {
        left = pivotpos + 1;
        newpos = position - left;
    }
    else /* pivotpos >= position) */ /* throw away right side */
    {
        right = pivotpos - 1;
        newpos = position;
    }

    temparray = create_array (right-left+1);
    copyarray_partial (array, temparray, left, right);

    retval = kth_smallest_method3 (temparray, right-left+1, newpos);

    temparray = free_array (temparray);
    array = free_array (array);
    
    return retval;
}

/* Find the kth smallest element in the array (starting from zero)
 * 
 * This method uses both partition() from quicksort, as well as using
 * the "median of medians" rule to throw away as much data as possible */
int kth_smallest_method4 (int src_array[], unsigned long size, unsigned long position)
{
    int *array;
    int *medianarray;
    int *temparray = NULL;
    int group_size = 11; /* choose any odd number, 11 works well in my tests */
    int i, left=0, right=group_size-1;
    int num_groups = size/group_size;
    int retval;
    int pivotpos;

    array = create_array (size);
    copyarray (src_array, array, size);

    /* base case */
    if (size <= group_size)
    {
        insertsort (array, size);
        retval = array[position];

        array = free_array (array);

        return retval;
    }
    
    /* get the array of medians */
    medianarray = create_array (num_groups);
    temparray = create_array (group_size);
    
    for (i=0; i<num_groups; i++)
    {
        copyarray_partial (array, temparray, left, right);
        insertsort (temparray, group_size);
        medianarray[i] = temparray[group_size/2];
        left = right + 1;
        right = left + group_size - 1;
    }

    temparray = free_array (temparray);
    
    /* find the median of medians */
    retval = kth_smallest_method4 (medianarray, num_groups, num_groups/2);

    /* move the mm to the 0th position in the array (for partition) */
    for (i=0; i<size; i++)
    {
        if (array[i] == retval)
        {
            swap (&array[i], &array[0]);
            break;
        }
    }

    /* find pivotpos using partition() */
    pivotpos = partition (array, 0, size-1);

    if (position == pivotpos)
    { /* no-op */ }
    else if (position < pivotpos)
    {
        temparray = create_array (pivotpos);
        copyarray_partial (array, temparray, 0, pivotpos-1);
        retval = kth_smallest_method4 (temparray, pivotpos, position);
    }
    else
    {
        temparray = create_array (size-(pivotpos+1));
        copyarray_partial (array, temparray, pivotpos+1, size-1);
        retval = kth_smallest_method4 (temparray, size-(pivotpos+1), position-(pivotpos+1));
    }
    
    array = free_array (array);
    medianarray = free_array (medianarray);
    if (temparray != NULL)
    {
        temparray = free_array (temparray);
    }

    return retval;
}