WebSVN – programming – Diff – /cs331/proj2/Project2.c

  * Started on: 05-20-2005
  * Due Date: 06-10-2005
  * CS331 Project #2
  */
+/* standard headers */
 #include <stdio.h>
 #include <stdlib.h>
 #include <time.h>
-void mergesort (int array[], unsigned long size);
+/* broken-out code for common things */
-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);
+#include "sorts.c"
-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);
+#include "timing.c"
-int* create_array (unsigned long size);
+#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);
-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 *array;
     int i;
-    for (size=1000000; size<=10000000; size+=1000000)
+    for (size=1000000; size<=2000000; size+=1000000)
+    {
         array = create_array (size);
         /* fill the array with random values */
         randomfill (array, size);
                 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 */
             printtimetaken("Method4");
             printf ("\n\n");
+        }
-        free (array); array = NULL;
+        array = free_array (array);
+    }
     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)
+{
     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
  */
     copyarray (src_array, array, size);
     mergesort (array, size);
     retval = array[position];
-    free (array); array = NULL;
+    array = free_array (array);
     return retval;
+}
 /* Find the kth smallest element in the array (starting from zero)
             right = pivotpos - 1;
+    }
     while (pivotpos != position);
     retval = array[position];
-    free (array); array = NULL;
+    array = free_array (array);
     return retval;
+}
 int kth_smallest_method3 (int src_array[], unsigned long size, unsigned long position)
     /* base case */
     if (pivotpos == position)
+    {
         retval = array[position];
-        free (array); array = NULL;
+        array = free_array (array);
         return retval;
+    }
     /* throw away left side */
     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;
+    temparray = free_array (temparray);
-    free (array); array = NULL;
+    array = free_array (array);
     return retval;
+}
 int kth_smallest_method4 (int src_array[], unsigned long size, unsigned long position)
     copyarray (src_array, array, size);
     /* base case */
     if (size <= group_size)
+    {
-        mergesort (array, size);
+        insertsort (array, size);
         retval = array[position];
-        free (array); array = NULL;
+        array = free_array (array);
         return retval;
+    }
     /* get the array of medians */
     temparray = create_array (group_size);
     for (i=0; i<num_groups; i++)
+    {
         copyarray_partial (array, temparray, left, right);
-        mergesort (temparray, group_size);
+        insertsort (temparray, group_size);
         medianarray[i] = temparray[group_size/2];
         left = right + 1;
         right = left + group_size - 1;
+    }
-    free (temparray); temparray = NULL;
+    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) */
         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;
+    array = free_array (array);
-    free (medianarray); medianarray = NULL;
+    medianarray = free_array (medianarray);
     if (temparray != NULL)
+    {
-        free (temparray); temparray = NULL;
+        temparray = free_array (temparray);
+    }
     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;
-}

Subversion Repositories programming

(root)/cs331/proj2/Project2.c @ 86 – Rev 85 → 86