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 i;

    for (size=1000000; size<=1000000; size+=1000000)

    {

        array = create_array (size);

        /* fill the array with random values */

        randomfill (array, size);

        for (i=0; i<5; i++)

        {

            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");

        }

        array = free_array (array);

    }

    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;

}