Subversion Repositories programming

Rev

Rev 77 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 77 Rev 82
Line 1... Line 1...
1 
/* Written by: Ira Snyder
 1 
/* Written by: Ira Snyder
2 
 * Started on: 05-20-2005
 2 
 * Started on: 05-20-2005
3 
 * Due Date: 06-01-2005
 3 
 * Due Date: 06-10-2005
4 
 * CS331 Project #2
 4 
 * CS331 Project #2
5 
 *
 - 
 
6 
 * Changelog Follows:
 - 
 
7 
 *
 - 
 
8 
 */
 5 
 */
9 
 
 6 
 
10 
#include <stdio.h>
 7 
#include <stdio.h>
11 
#include <stdlib.h>
 8 
#include <stdlib.h>
12 
#include <time.h>
 9 
#include <time.h>
Line 41... Line 38...
41
38
42 
    for (size=50; size<=3000; size+=50)
 39 
    for (size=50; size<=3000; size+=50)
43 
    {
 40 
    {
44 
        if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
 41 
        if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
45 
        {
 42 
        {
46 
            printf ("Ran out of memory at size=%d\n", size);
 43 
            printf ("Ran out of memory at size=%lu\n", size);
47 
            exit(1);
 44 
            exit (1);
48 
        }
 45 
        }
49 
 
 46 
 
50 
        /* fill the array with random values */
 47 
        /* fill the array with random values */
51 
        randomfill (array, size);
 48 
        randomfill (array, size);
52 
 
 49 
 
Line 61... Line 58...
61 
            else if (i==3)
 58 
            else if (i==3)
62 
                kth_pos=3*size/4;
 59 
                kth_pos=3*size/4;
63 
            else
 60 
            else
64 
                kth_pos=size-1;
 61 
                kth_pos=size-1;
65 
            /* header */
 62 
            /* header */
66 
            printf ("Running with size=%d (%.3fMB) kth_pos=%d...\n",
63 
            printf ("Running with size=%lu (%.3fMB) kth_pos=%lu...\n",
67 
                    size, (size*4.0)/(1024*1024), kth_pos);
 64 
                    size, (size*4.0)/(1024*1024), kth_pos);
68
65
69 
            /* run method1 */
 66 
            /* run method1 */
70 
            startclock();
 67 
            startclock();
71 
            printf ("%dth smallest (method1): %d -- ", kth_pos,
68 
            printf ("%luth smallest (method1): %d -- ", kth_pos,
72 
                    kth_smallest_method1 (array, size, kth_pos));
 69 
                    kth_smallest_method1 (array, size, kth_pos));
73 
            stopclock();
 70 
            stopclock();
74 
            printtimetaken("Method1");
 71 
            printtimetaken("Method1");
75 
 
 72 
 
76 
            /* run method2 */
 73 
            /* run method2 */
77 
            startclock();
 74 
            startclock();
78 
            printf ("%dth smallest (method2): %d -- ", kth_pos,
75 
            printf ("%luth smallest (method2): %d -- ", kth_pos,
79 
                    kth_smallest_method2 (array, size, kth_pos));
 76 
                    kth_smallest_method2 (array, size, kth_pos));
80 
            stopclock();
 77 
            stopclock();
81 
            printtimetaken("Method2");
 78 
            printtimetaken("Method2");
82 
 
 79 
 
- 
 
 80 
            /* run method3 */
- 
 
 81 
            startclock();
- 
 
 82 
            printf ("%luth smallest (method3): %d -- ", kth_pos,
- 
 
 83 
                    kth_smallest_method3 (array, size, kth_pos));
- 
 
 84 
            stopclock();
- 
 
 85 
            printtimetaken("Method3");
- 
 
 86 
 
83 
            printf ("\n\n");
 87 
            printf ("\n\n");
84 
        }
 88 
        }
85
89
86 
        free (array);
 90 
        free (array);
87 
        array = NULL;
 91 
        array = NULL;
Line 124... Line 128...
124 
{
 128 
{
125 
    unsigned long ai, bi, ci, i;
 129 
    unsigned long ai, bi, ci, i;
126 
    int *C;
 130 
    int *C;
127 
    unsigned long csize = asize+bsize;
 131 
    unsigned long csize = asize+bsize;
128 
 
 132 
 
129 
    C = (int*) malloc (csize * sizeof(int));
 133 
    if ( (C = (int*) malloc (csize * sizeof(int))) == NULL)
130
- 
 
131 
    if (C == NULL)
 - 
 
132 
    {
 134 
    {
133 
        printf("Out of memory... Exiting\n");
 135 
        printf ("Out of memory... Exiting\n");
134 
        exit(1);
 136 
        exit (1);
135 
    }
 137 
    }
136
138
137 
    ai = 0;
 139 
    ai = 0;
138 
    bi = 0;
 140 
    bi = 0;
139 
    ci = 0;
 141 
    ci = 0;
Line 179... Line 181...
179 
 */
 181 
 */
180 
void printarray (int array[], unsigned long size)
 182 
void printarray (int array[], unsigned long size)
181 
{
 183 
{
182 
    unsigned long i;
 184 
    unsigned long i;
183
185
184 
    printf("Printing %d elements\n", size);
 186 
    printf("Printing %lu elements\n", size);
185
187
186 
    for (i=0; i<size; i++)
 188 
    for (i=0; i<size; i++)
187 
        printf("%d ", array[i]);
 189 
        printf("%d ", array[i]);
188 
 
 190 
 
189 
    printf("\n");
 191 
    printf("\n");
Line 255... Line 257...
255 
 
 257 
 
256 
    for (i=0; i<size; i++)
 258 
    for (i=0; i<size; i++)
257 
        dst[i] = src[i];
 259 
        dst[i] = src[i];
258 
}
 260 
}
259 
 
 261 
 
- 
 
 262 
void copyarray_partial (int src[], int dst[], unsigned long src_left,
- 
 
 263 
        unsigned long src_right)
- 
 
 264 
{
- 
 
 265 
    unsigned long i, j;
- 
 
 266 
 
- 
 
 267 
    for (i=src_left, j=0; i<=src_right; i++, j++)
- 
 
 268 
        dst[j] = src[i];
- 
 
 269 
}
- 
 
 270 
 
260 
/* Find the kth smallest element in the array (starting from zero)
 271 
/* Find the kth smallest element in the array (starting from zero)
261 
 *
 272 
 *
262 
 * This uses the method of sorting the list, then picking
 273 
 * This uses the method of sorting the list, then picking
263 
 * the correct element
 274 
 * the correct element
264 
 */
 275 
 */
265 
int kth_smallest_method1 (int src_array[], unsigned long size, unsigned long position)
 276 
int kth_smallest_method1 (int src_array[], unsigned long size,
- 
 
 277 
        unsigned long position)
266 
{
 278 
{
267 
    //int array[size];
 - 
 
268 
    int *array;
 279 
    int *array;
269 
    int retval;
 280 
    int retval;
270 
 
 281 
 
271 
    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
 282 
    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
272 
    {
 283 
    {
273 
        printf ("Out of memory at size=%d\n", size);
 284 
        printf ("Out of memory at size=%lu\n", size);
274 
        exit(1);
 285 
        exit(1);
275 
    }
 286 
    }
276 
 
 287 
 
277 
    copyarray (src_array, array, size);
 288 
    copyarray (src_array, array, size);
278
289
Line 289... Line 300...
289 
 * This uses the method of calling partiton() from quicksort, and
 300 
 * This uses the method of calling partiton() from quicksort, and
290 
 * throwing out data that is unneeded
 301 
 * throwing out data that is unneeded
291 
 */
 302 
 */
292 
int kth_smallest_method2 (int src_array[], unsigned long size, unsigned long position)
 303 
int kth_smallest_method2 (int src_array[], unsigned long size, unsigned long position)
293 
{
 304 
{
294 
    //int array[size];
 - 
 
295 
    int *array;
 305 
    int *array;
296 
    int retval;
 306 
    int retval;
297 
    unsigned long left = 0;
 307 
    unsigned long left = 0;
298 
    unsigned long right = size-1;
 308 
    unsigned long right = size-1;
299 
    unsigned long pivotpos;
 309 
    unsigned long pivotpos;
300
310
301 
    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
 311 
    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
302 
    {
 312 
    {
303 
        printf ("Out of memory at size=%d\n", size);
 313 
        printf ("Out of memory at size=%lu\n", size);
304 
        exit(1);
 314 
        exit (1);
305 
    }
 315 
    }
306
316
307 
    copyarray (src_array, array, size);
 317 
    copyarray (src_array, array, size);
308 
 
 318 
 
309 
    do
 319 
    do
Line 312... Line 322...
312 
        pivotpos = partition (array, left, right);
 322 
        pivotpos = partition (array, left, right);
313 
 
 323 
 
314 
        if (pivotpos < position)
 324 
        if (pivotpos < position)
315 
            left = pivotpos + 1;
 325 
            left = pivotpos + 1;
316 
        else /* pivotpos >= position) */
 326 
        else /* pivotpos >= position) */
317 
            right = pivotpos-1;
 327 
            right = pivotpos - 1;
318 
    }
 328 
    }
319 
    while (pivotpos != position);
 329 
    while (pivotpos != position);
320 
 
 330 
 
321 
    retval = array[position];
 331 
    retval = array[position];
322 
    free (array);
 332 
    free (array);
323 
    array = NULL;
 333 
    array = NULL;
324 
    return retval;
 334 
    return retval;
325 
}
 335 
}
326 
 
 336 
 
- 
 
 337 
int kth_smallest_method3 (int src_array[], unsigned long size, unsigned long position)
- 
 
 338 
{
- 
 
 339 
    int *array;
- 
 
 340 
    int *temparray;
- 
 
 341 
    int retval;
- 
 
 342 
    unsigned long left = 0;
- 
 
 343 
    unsigned long right = size-1;
- 
 
 344 
    unsigned long pivotpos, newpos;
- 
 
 345 
 
- 
 
 346 
    if ( (array = (int*) malloc (size*sizeof(int))) == NULL)
- 
 
 347 
    {
- 
 
 348 
        printf ("Out of memory at size=%lu\n", size);
- 
 
 349 
        exit (1);
- 
 
 350 
    }
- 
 
 351 
 
- 
 
 352 
    copyarray (src_array, array, size);
- 
 
 353 
 
- 
 
 354 
    swap (&array[position], &array[left]);
- 
 
 355 
    pivotpos = partition (array, left, right);
- 
 
 356 
 
- 
 
 357 
    /* base case */
- 
 
 358 
    if (pivotpos == position)
- 
 
 359 
    {
- 
 
 360 
        retval = array[position];
- 
 
 361 
        free (array);
- 
 
 362 
        array = NULL;
- 
 
 363 
        return retval;
- 
 
 364 
    }
- 
 
 365
- 
 
 366 
    /* throw away left side */
- 
 
 367 
    if (pivotpos < position)
- 
 
 368 
    {
- 
 
 369 
        left = pivotpos + 1;
- 
 
 370 
        newpos = position - left;
- 
 
 371 
    }
- 
 
 372 
    else /* pivotpos >= position) */ /* throw away right side */
- 
 
 373 
    {
- 
 
 374 
        right = pivotpos - 1;
- 
 
 375 
        newpos = position;
- 
 
 376 
    }
- 
 
 377 
 
- 
 
 378 
    if ( (temparray = (int*) malloc (size*sizeof(int))) == NULL)
- 
 
 379 
    {
- 
 
 380 
        printf ("Out of memory at size=%lu\n", size);
- 
 
 381 
        exit (1);
- 
 
 382 
    }
- 
 
 383 
 
- 
 
 384 
    copyarray_partial (array, temparray, left, right);
- 
 
 385 
 
- 
 
 386 
    retval = kth_smallest_method3 (temparray, right-left+1, newpos);
- 
 
 387 
 
- 
 
 388 
    free (temparray);
- 
 
 389 
    temparray = NULL;
- 
 
 390 
    free (array);
- 
 
 391 
    array = NULL;
- 
 
 392
- 
 
 393 
    return retval;
- 
 
 394 
}
- 
 
 395