Subversion Repositories programming

/* Written by: Ira Snyder

 * Started on: 05-20-2005

 * Due Date: 06-10-2005

 * CS331 Project #2

 */

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void mergesort (int array[], unsigned long size);

void mergesort_rec (int A[], unsigned long min, unsigned long max);

void merge (int A[], unsigned long asize, int B[], unsigned long bsize);

void swap (int *left, int *right);

void printarray (int array[], unsigned long size);

void randomfill (int array[], unsigned long size);

int partition (int array[], unsigned long left, unsigned long right);

void copyarray (int src[], int dst[], unsigned long size);

void copyarray_partial (int src[], int dst[], unsigned long src_left,

        unsigned long src_right);

int* create_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);

void startclock (void);

void stopclock (void);

void printtimetaken (char *funcname);

/* global timeval for timing the function calls */

struct timeval start_time, end_time, lapsed;

int main (void)

{

    /* create new random seed */

    srand((unsigned)time(NULL));

    unsigned long size, kth_pos;

    int* array;

    int i;

    for (size=1000000; size<=10000000; 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");

            printf ("\n\n");

        }

        free (array); array = NULL;

    }

    return 0;

}

/* Mergesort an array

 * Sets up the correct parameters and hands off the work to

 * mergesort_rec()

 * 

 * Complexity: O(n*lgn)

 */

void mergesort (int array[], unsigned long size)

{

    mergesort_rec (array, 0, size-1);

}

/* The actual mergesort call */

void mergesort_rec (int A[], unsigned long min, unsigned long max)

{

    unsigned long mid = (min+max)/2;

    unsigned long lowerCount = mid - min + 1;

    unsigned long upperCount = max - mid;

    if (max == min)

        return;

    mergesort_rec (A, min, mid);

    mergesort_rec (A, mid+1, max);

    merge (A+min, lowerCount, A+mid+1, upperCount);

}

/* merge two arrays together

 *

 * Complexity: O(n)

 */

void merge(int A[], unsigned long asize, int B[], unsigned long bsize)

{

    unsigned long ai, bi, ci, i;

    int *C;

    unsigned long csize = asize+bsize;

    C = create_array (csize);

    ai = 0;

    bi = 0;

    ci = 0;

    while ((ai < asize) && (bi < bsize)) 

    {

        if (A[ai] <= B[bi])

        {

            C[ci] = A[ai];

            ci++; ai++;

        }

        else

        {

            C[ci] = B[bi];

            ci++; bi++;

        }

    }

    if (ai >= asize)

        for (i = ci; i < csize; i++, bi++)

            C[i] = B[bi];

        else if (bi >= bsize)

            for (i = ci; i < csize; i++, ai++)

                C[i] = A[ai];

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

            A[i] = C[i];

    free (C);

}

/* swap two values */

void swap (int *left, int *right)

{

    int temp;

    temp = *left;

    *left = *right;

    *right = temp;

}

/* print out the contents of the array

 * used for debugging mainly

 */

void printarray (int array[], unsigned long size)

{

    unsigned long i;

    printf("Printing %lu elements\n", size);

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

        printf("%d ", array[i]);

    printf("\n");

}

/* 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;

}

/* partition from quicksort

 * this partitions an array around the pivot value,

 * which is found in array[left].

 *

 * All values less than the pivot are on the left

 * All values more than the pivot are on the right

 *

 * Complexity: O(n)

 */

int partition (int array[], unsigned long left, unsigned long right)

{

    unsigned long i, last, pivot;

    pivot = array[left];

    last = left;

    for (i=left+1; i<=right; i++)

        if (array[i] < pivot)

        {

           last++;

           swap (&array[last], &array[i]);

        }

    swap (&array[left], &array[last]);

    return last;

}

/* start the clock (for timing) */

void startclock (void)

{

    gettimeofday(&start_time, NULL);

}

/* stop the clock (for timing) */

void stopclock (void)

{

    gettimeofday(&end_time, NULL);

}

/* print the time taken, in milliseconds = seconds / 1000 */

void printtimetaken (char *funcname)

{

    double total_usecs = (end_time.tv_sec-start_time.tv_sec) * 1000000.0

                       + (end_time.tv_usec-start_time.tv_usec);

    printf("%s : %.3lf milliseconds\n", funcname, total_usecs/1000.0);

}

/* copy the src[] to dst[] */

void copyarray (int src[], int dst[], unsigned long size)

{

    unsigned long i;

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

        dst[i] = src[i];

}

void copyarray_partial (int src[], int dst[], unsigned long src_left, 

        unsigned long src_right)

{

    unsigned long i, j;

    for (i=src_left, j=0; i<=src_right; i++, j++)

        dst[j] = src[i];

}

/* 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];

    free (array); array = NULL;

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

    free (array); array = NULL;

    return retval;

}

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

        free (array); array = NULL;

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

    free (temparray); temparray = NULL;

    free (array); array = NULL;

    return retval;

}

int kth_smallest_method4 (int src_array[], unsigned long size, unsigned long position)

{

    int *array;

    int *medianarray;

    int *temparray = NULL;

    int group_size = 11;

    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)

    {

        mergesort (array, size);

        retval = array[position];

        free (array); array = NULL;

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

        mergesort (temparray, group_size);

        medianarray[i] = temparray[group_size/2];

        left = right + 1;

        right = left + group_size - 1;

    }

    free (temparray); temparray = NULL;

    /* 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));

    }

    free (array); array = NULL;

    free (medianarray); medianarray = NULL;

    if (temparray != NULL)

    {

        free (temparray); temparray = NULL;

    }

    return retval;

}

int* create_array (unsigned long size)

{

    int *array;

    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)

    {

        printf ("Out of memory allocating array of size=%lu\n", size);

        printf ("Exiting...");

        exit (1);

    }

    return array;

}