Subversion Repositories programming

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

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

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=50; size<=3000; size+=50)
    {
        if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
        {
            printf ("Ran out of memory at size=%d\n", size);
            exit(1);
        }

        /* 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=%d (%.3fMB) kth_pos=%d...\n", 
                    size, (size*4.0)/(1024*1024), kth_pos);
        
            /* run method1 */
            startclock();
            printf ("%dth smallest (method1): %d -- ", kth_pos, 
                    kth_smallest_method1 (array, size, kth_pos));
            stopclock();
            printtimetaken("Method1");

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

            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 = (int*) malloc (csize * sizeof(int));
   
    if (C == NULL)
    {
        printf("Out of memory... Exiting\n");
        exit(1);
    }
   
    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 %d 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];
}

/* 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[size];
    int *array;
    int retval;

    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
    {
        printf ("Out of memory at size=%d\n", size);
        exit(1);
    }

    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[size];
    int *array;
    int retval;
    unsigned long left = 0;
    unsigned long right = size-1;
    unsigned long pivotpos;
    
    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
    {
        printf ("Out of memory at size=%d\n", size);
        exit(1);
    }
    
    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;
}