Subversion Repositories programming

Rev

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

Rev 86 Rev 87
Line 31... Line 31...
31 
 
 31 
 
32 
    unsigned long size, kth_pos;
 32 
    unsigned long size, kth_pos;
33 
    int *array;
 33 
    int *array;
34 
    int i;
 34 
    int i;
35
35
36 
    for (size=1000000; size<=2000000; size+=1000000)
 36 
    for (size=1000000; size<=1000000; size+=1000000)
37 
    {
 37 
    {
38 
        array = create_array (size);
 38 
        array = create_array (size);
39 
 
 39 
 
40 
        /* fill the array with random values */
 40 
        /* fill the array with random values */
41 
        randomfill (array, size);
 41 
        randomfill (array, size);
Line 83... Line 83...
83 
            printf ("%luth smallest (method4): %d -- ", kth_pos,
83 
            printf ("%luth smallest (method4): %d -- ", kth_pos,
84 
                    kth_smallest_method4 (array, size, kth_pos));
 84 
                    kth_smallest_method4 (array, size, kth_pos));
85 
            stopclock();
 85 
            stopclock();
86 
            printtimetaken("Method4");
 86 
            printtimetaken("Method4");
87
87
- 
 
 88 
            /* some blank lines for spacing */
88 
            printf ("\n\n");
 89 
            printf ("\n\n");
89 
        }
 90 
        }
90
91
91 
        array = free_array (array);
 92 
        array = free_array (array);
92 
    }
 93 
    }
93 
 
 94 
 
94 
    return 0;
 95 
    return 0;
95 
}
 96 
}
96 
 
 97 
 
97 
/* fill the array with random numbers in
 98 
/* fill the array with random numbers in
98 
 * the range 0-32767
 99 
 * the range 0-32767 */
99 
 */
 - 
 
100 
void randomfill (int array[], unsigned long size)
 100 
void randomfill (int array[], unsigned long size)
101 
{
 101 
{
102 
    unsigned long i;
 102 
    unsigned long i;
103
103
104 
    for (i=0; i<size; i++)
 104 
    for (i=0; i<size; i++)
Line 106... Line 106...
106 
}
 106 
}
107 
 
 107 
 
108 
/* Find the kth smallest element in the array (starting from zero)
 108 
/* Find the kth smallest element in the array (starting from zero)
109 
 *
 109 
 *
110 
 * This uses the method of sorting the list, then picking
 110 
 * This uses the method of sorting the list, then picking
111 
 * the correct element
 111 
 * the correct element */
112 
 */
 - 
 
113 
int kth_smallest_method1 (int src_array[], unsigned long size,
112 
int kth_smallest_method1 (int src_array[], unsigned long size,
114 
        unsigned long position)
 113 
        unsigned long position)
115 
{
 114 
{
116 
    int *array;
 115 
    int *array;
117 
    int retval;
 116 
    int retval;
Line 128... Line 127...
128 
}
 127 
}
129 
 
 128 
 
130 
/* Find the kth smallest element in the array (starting from zero)
 129 
/* Find the kth smallest element in the array (starting from zero)
131 
 *
 130 
 *
132 
 * This uses the method of calling partiton() from quicksort, and
 131 
 * This uses the method of calling partiton() from quicksort, and
133 
 * throwing out data that is unneeded
 132 
 * throwing out data that is unneeded */
134 
 */
 - 
 
135 
int kth_smallest_method2 (int src_array[], unsigned long size, unsigned long position)
 133 
int kth_smallest_method2 (int src_array[], unsigned long size, unsigned long position)
136 
{
 134 
{
137 
    int *array;
 135 
    int *array;
138 
    int retval;
 136 
    int retval;
139 
    unsigned long left = 0;
 137 
    unsigned long left = 0;
Line 159... Line 157...
159 
    array = free_array (array);
 157 
    array = free_array (array);
160
158
161 
    return retval;
 159 
    return retval;
162 
}
 160 
}
163 
 
 161 
 
- 
 
 162 
/* Find the kth smallest element in the array (starting from zero)
- 
 
 163 
 *
- 
 
 164 
 * This uses the method of calling partiton() from quicksort, and
- 
 
 165 
 * throwing out data that is unneeded
- 
 
 166 
 *
- 
 
 167 
 * NOTE: This is a recursive version of the algorithm above (kth_smallest_method2) */
164 
int kth_smallest_method3 (int src_array[], unsigned long size, unsigned long position)
 168 
int kth_smallest_method3 (int src_array[], unsigned long size, unsigned long position)
165 
{
 169 
{
166 
    int *array;
 170 
    int *array;
167 
    int *temparray;
 171 
    int *temparray;
168 
    int retval;
 172 
    int retval;
Line 206... Line 210...
206 
    array = free_array (array);
 210 
    array = free_array (array);
207
211
208 
    return retval;
 212 
    return retval;
209 
}
 213 
}
210 
 
 214 
 
- 
 
 215 
/* Find the kth smallest element in the array (starting from zero)
- 
 
 216 
 *
- 
 
 217 
 * This method uses both partition() from quicksort, as well as using
- 
 
 218 
 * the "median of medians" rule to throw away as much data as possible */
211 
int kth_smallest_method4 (int src_array[], unsigned long size, unsigned long position)
 219 
int kth_smallest_method4 (int src_array[], unsigned long size, unsigned long position)
212 
{
 220 
{
213 
    int *array;
 221 
    int *array;
214 
    int *medianarray;
 222 
    int *medianarray;
215 
    int *temparray = NULL;
 223 
    int *temparray = NULL;
216 
    int group_size = 11;
 224 
    int group_size = 11; /* choose any odd number, 11 works well in my tests */
217 
    int i, left=0, right=group_size-1;
 225 
    int i, left=0, right=group_size-1;
218 
    int num_groups = size/group_size;
 226 
    int num_groups = size/group_size;
219 
    int retval;
 227 
    int retval;
220 
    int pivotpos;
 228 
    int pivotpos;
221 
 
 229