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

 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** create_matrix (unsigned long rows, unsigned long cols);
+void free_matrix (int **matrix, unsigned long rows, unsigned long cols);
 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);
     unsigned long size, kth_pos;
     int* array;
     int i;
-    for (size=50; size<=3000; size+=50)
+    for (size=1000000; size<=10000000; size+=1000000)
+    {
-        if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
-        {
-            printf ("Ran out of memory at size=%lu\n", size);
-            exit (1);
+        array = create_array (size);
-        }
         /* fill the array with random values */
         randomfill (array, size);
         for (i=0; i<5; i++)
             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;
+        free (array); array = NULL;
+    }
     return 0;
+}
+{
     unsigned long ai, bi, ci, i;
     int *C;
     unsigned long csize = asize+bsize;
-    if ( (C = (int*) malloc (csize * sizeof(int))) == NULL)
-    {
-        printf ("Out of memory... Exiting\n");
-        exit (1);
+    C = create_array (csize);
-    }
     ai = 0;
     bi = 0;
     ci = 0;
     while ((ai < asize) && (bi < bsize))
         unsigned long position)
+{
     int *array;
     int retval;
-    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
-    {
-        printf ("Out of memory at size=%lu\n", size);
+    array = create_array (size);
-        exit(1);
-    }
     copyarray (src_array, array, size);
     mergesort (array, size);
     retval = array[position];
-    free (array);
+    free (array); array = NULL;
-    array = NULL;
     return retval;
+}
 /* Find the kth smallest element in the array (starting from zero)
+ *
     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=%lu\n", size);
-        exit (1);
+    array = create_array (size);
-    }
     copyarray (src_array, array, size);
     do
+    {
         swap (&array[position], &array[left]);
             right = pivotpos - 1;
+    }
     while (pivotpos != position);
     retval = array[position];
-    free (array);
+    free (array); array = NULL;
-    array = NULL;
     return retval;
+}
 int kth_smallest_method3 (int src_array[], unsigned long size, unsigned long position)
+{
     int retval;
     unsigned long left = 0;
     unsigned long right = size-1;
     unsigned long pivotpos, newpos;
-    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
-    {
-        printf ("Out of memory at size=%lu\n", size);
-        exit (1);
+    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;
+        free (array); array = NULL;
         return retval;
+    }
     /* throw away left side */
     if (pivotpos < position)
+    {
         right = pivotpos - 1;
         newpos = position;
+    }
-    if ( (temparray = (int*) malloc (size*sizeof(int))) == NULL)
+    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 **matrix;
+    int *medianarray;
+    int *temparray = NULL;
+    int group_size = 3;
+    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)
+    {
-        printf ("Out of memory at size=%lu\n", size);
+        mergesort (array, size);
+        retval = array[position];
+        free (array); array = NULL;
-        exit (1);
+        return retval;
+    }
+    /* create the matrix as described in class */
+    matrix = create_matrix (num_groups, group_size);
+    for (i=0; i<num_groups; i++)
+    {
-    copyarray_partial (array, temparray, left, right);
+        copyarray_partial (array, matrix[i], left, right);
+        mergesort (matrix[i], group_size);
+        left = right + 1;
+        right = left + group_size - 1;
+    }
+    /* get the array of medians */
+    medianarray = create_array (num_groups);
+    for (i=0; i<num_groups; i++)
+        medianarray[i] = matrix[i][group_size/2];
+    /* find the median of medians */
-    retval = kth_smallest_method3 (temparray, right-left+1, newpos);
+    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]);
-    free (temparray);
+            break;
+        }
+    }
+    /* find pivotpos using partition() */
+    pivotpos = partition (array, 0, size-1);
+    if (position == pivotpos)
+    {
-    temparray = NULL;
+        free (array); array = NULL;
+        free_matrix (matrix, num_groups, group_size);
+        free (medianarray); medianarray = NULL;
+        return retval;
+    }
+    else if (position < pivotpos)
+    {
+        temparray = create_array (pivotpos);
+        copyarray_partial (array, temparray, 0, pivotpos-1);
+        retval = kth_smallest_method4 (temparray, pivotpos, position);
-    free (array);
+        free (array); array = NULL;
+        free_matrix (matrix, num_groups, group_size);
+        free (medianarray); medianarray = NULL;
+        free (temparray); temparray = NULL;
+        return retval;
+    }
+    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 = NULL;
+        free (array); array = NULL;
+        free_matrix (matrix, num_groups, group_size);
+        free (medianarray); medianarray = NULL;
+        free (temparray); temparray = NULL;
+        return retval;
+    }
+    /* shouldn't need any of this */
+    free_matrix (matrix, num_groups, group_size);
+    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;
+}
+int** create_matrix (unsigned long rows, unsigned long cols)
+{
+    int **array;
+    int i;
+    if ( (array = (int**) malloc (rows*sizeof(int*))) == NULL)
+    {
+        printf ("Out of memory creating matrix of size=%lux%lu\n", rows, cols);
+        printf ("Exiting...");
+        exit (1);
+    }
+    for (i=0; i<rows; i++)
+    {
+        if ( (array[i] = (int*) malloc (cols*sizeof(int))) == NULL)
+        {
+            printf ("Out of memory creating matrix of size=%lux%lu\n", rows, cols);
+            printf ("Exiting...");
+            exit (1);
+        }
+    }
+    return array;
+}
+void free_matrix (int **matrix, unsigned long rows, unsigned long cols)
+{
+    int i;
+    for (i=0; i<rows; i++)
+    {
+        free (matrix[i]);
+        matrix[i] = NULL;
+    }
+    free (matrix);
+    matrix = NULL;
+}

Subversion Repositories programming

(root)/cs331/proj2/Project2.c @ 83 – Rev 82 → 83