Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

quicksort.cpp

Go to the documentation of this file.
00001 
00002 /* ---------------------------------------------------------------------- */
00003 /* Includes */
00004 #include <stdint.h>
00005 #include <stdio.h>
00006 #include <stdlib.h>
00007 #include <sys/time.h>
00008 #include <string.h> /* for memcpy */
00009 
00010 /* ---------------------------------------------------------------------- */
00011 /* Globals */
00012 uint32_t ph_glbl_swaps      = 0;
00013 uint32_t ph_glbl_compares   = 0;
00014 
00015 /* ---------------------------------------------------------------------- */
00016 /* Defines */
00017 
00018 /* ---------------------------------------------------------------------- */
00019 /* Types */
00020 typedef int32_t (*ph_qs_compare_fn)(const void *_one, const void *_two);
00021 
00022 /* ---------------------------------------------------------------------- */
00023 /* Prototypes */
00024 int32_t ph_quicksort_partition(const void       *arr,
00025                                const int32_t     low,
00026                                const int32_t     high,
00027                                const uint32_t    size,
00028                                uint8_t          *tempptr,
00029                                ph_qs_compare_fn  compare );
00030                                             
00031 void ph_quicksort_recursive( const void         *arr, 
00032                              const int32_t       low, 
00033                              const int32_t       high,
00034                              const uint32_t      size,
00035                              uint8_t            *tempptr,
00036                              ph_qs_compare_fn    compare );
00037                                 
00038 void ph_quicksort_iterative( const void         *arr, 
00039                              const int32_t       low, 
00040                              const int32_t       high,
00041                              const uint32_t      size,
00042                              uint8_t            *tempptr,
00043                              ph_qs_compare_fn    compare );
00044                                     
00045 /* ---------------------------------------------------------------------- */
00046 int32_t ph_qs_sort_uint32_t( const uint32_t nelements, 
00047                              uint32_t *array,
00048                              const uint32_t method );
00049 
00050 int32_t ph_qs_compare_uint32_t(const void *_one, const void *_two);
00051 
00052 int32_t ph_qs_randomfill_uint32_t(  const uint32_t  nelements,
00053                                     uint32_t       *array,
00054                                     const uint32_t  maxval     );
00055 
00056 int32_t ph_qs_print_uint32_t( const uint32_t  nelements, 
00057                               const uint32_t *array );
00058 
00059 int32_t ph_qs_verify_uint32_t( const uint32_t nelements, 
00060                                const uint32_t *array );
00061 
00062 /* ---------------------------------------------------------------------- */
00063 #define ph_qsMemswap( ptrone, ptrtwo, tempptr, size )  \
00064     do {                                            \
00065         memcpy(tempptr,ptrone,size);                \
00066         memcpy(ptrone,ptrtwo,size);                 \
00067         memcpy(ptrtwo,tempptr,size);                \
00068         ph_glbl_swaps++;                            \
00069     } while (0);
00070 
00071 /* ---------------------------------------------------------------------- */
00072 int32_t ph_quicksort_partition(const void       *arr,
00073                                const int32_t     low,
00074                                const int32_t     high,
00075                                const uint32_t    size,
00076                                uint8_t          *tempptr,
00077                                ph_qs_compare_fn  compare
00078                               )
00079 {
00080     uint32_t      i     = 0;
00081     uint32_t      lim   = (high - low) + 1;
00082     uint32_t      store = low;
00083     //const int32_t pivot = (random() % (high - low)) + low;
00084     const int32_t pivot = (high + low) / 2;
00085 
00086     uint8_t *curptr    = ((uint8_t *)arr) + low  * size;
00087     uint8_t *pivotptr  = ((uint8_t *)arr) + pivot* size;
00088     uint8_t *highptr   = ((uint8_t *)arr) + high * size;
00089     uint8_t *storeptr  = curptr;
00090 
00091     /* If we're down to a parition of size 2, then we only need to compare
00092      * two numbers and don't need to execute the entire body of this
00093      * function */
00094     if (lim == 2)
00095     {
00096         if (compare(curptr,highptr) > 0)
00097             ph_qsMemswap(curptr,highptr,tempptr,size);
00098     
00099         return high;
00100     }
00101 
00102     /* Put the pivot value at the end of the partition */
00103     ph_qsMemswap(highptr,pivotptr,tempptr,size);
00104 
00105     /* Loop through all the elements */
00106     for (i = 0; i < lim - 1; i++ )
00107     {
00108         /* if i < pivot */
00109         /* compare returns 0:same, -1:less-than 1:greater-than */
00110         if (compare(curptr,highptr) <= 0)
00111         {
00112             /* Swap the current value and the one in the store */
00113             ph_qsMemswap(curptr,storeptr,tempptr,size);
00114             
00115             /* Increment the store variables */
00116             store++;
00117             storeptr += size;
00118         }
00119         curptr += size;
00120     }
00121 
00122     /* Bring the pivot value into the correct place within the parition */
00123     ph_qsMemswap(highptr,storeptr,tempptr,size);
00124 
00125     /* Everything above the pivot index is greater in value than the
00126      * pivot and everything below the pivot index is less than or equal to
00127      * the pivot value */
00128 
00129     return store;
00130 }
00131 
00132 /* ---------------------------------------------------------------------- */
00133 void ph_quicksort_recursive( const void     *arr, 
00134                              const int32_t   low, 
00135                              const int32_t   high,
00136                              const uint32_t  size,
00137                              uint8_t        *tempptr,
00138                              ph_qs_compare_fn   compare )
00139 {
00140     if (low < high)
00141     {
00142         int32_t mid = ph_quicksort_partition(arr,low,high,size,tempptr,compare);
00143         
00144         ph_quicksort_recursive(arr, low,    mid-1,size,tempptr,compare);
00145         ph_quicksort_recursive(arr, mid+1,  high, size,tempptr,compare);
00146     }
00147 }
00148 
00149 /* ---------------------------------------------------------------------- */
00150 typedef struct ph_qs_stack_t
00151 {
00152     struct ph_qs_stack_t   *next;
00153     int32_t                 low;
00154     int32_t                 high;
00155 } ph_qs_stack_type;
00156      
00157 /* ---------------------------------------------------------------------- */
00158 void ph_quicksort_iterative( const void     *arr, 
00159                              const int32_t   low, 
00160                              const int32_t   high,
00161                              const uint32_t  size,
00162                              uint8_t        *tempptr,
00163                              ph_qs_compare_fn   compare )
00164 {
00165     int32_t l = 0;
00166     int32_t h = 0;
00167     int32_t mid = 0;
00168     ph_qs_stack_type *stack_element = NULL;
00169     ph_qs_stack_type *stack = (ph_qs_stack_type *)malloc(sizeof(ph_qs_stack_type));
00170     if (stack == NULL)
00171     {
00172         printf("ERROR: failed to allocate space for the stack element\n");
00173         return;
00174     }
00175 
00176     /* Push the first */
00177     stack->next = NULL;
00178     stack->low  = low;
00179     stack->high = high;
00180 
00181     while (stack != NULL)
00182     {
00183         /* Pop */
00184         stack_element = stack;
00185         stack = stack->next;
00186         l = stack_element->low;
00187         h = stack_element->high;
00188         free(stack_element);
00189         
00190         if (l < h)
00191         {
00192             /* Partition the array */
00193             mid = ph_quicksort_partition(arr,l,h,size,tempptr,compare);
00194         
00195             /* Push */
00196             if (l < mid-1)
00197             {
00198                 stack_element = (ph_qs_stack_type *)malloc(sizeof(ph_qs_stack_type));
00199                 if (stack_element == NULL)
00200                 {
00201                     printf("ERROR: failed to allocate space for the stack element\n");
00202                     return;
00203                 }
00204                 stack_element->next = stack;
00205                 stack_element->low  = l;
00206                 stack_element->high = mid-1;
00207                 stack = stack_element;
00208             }        
00209             /* Push */
00210             if (mid+1 < h)
00211             {
00212                 stack_element = (ph_qs_stack_type *)malloc(sizeof(ph_qs_stack_type));
00213                 if (stack_element == NULL)
00214                 {
00215                     printf("ERROR: failed to allocate space for the stack element\n");
00216                     return;
00217                 }
00218                 stack_element->next = stack;
00219                 stack_element->low  = mid+1;
00220                 stack_element->high = h;
00221                 stack = stack_element;
00222             }
00223         }
00224     }
00225 }
00226                       
00227 /* ---------------------------------------------------------------------- */
00228 int32_t ph_qs_compare_uint32_t(const void *_one, const void *_two)
00229 {
00230     uint32_t one            = *((uint32_t *)_one);
00231     uint32_t two            = *((uint32_t *)_two);
00232 
00233     ph_glbl_compares++;    
00234     /* Greater than : 1 */
00235     if (one > two)
00236     {
00237         /* printf( "%u > %u\n",one,two); */
00238         return 1;
00239     }
00240     
00241     ph_glbl_compares++;    
00242     /* Less than : -1 */
00243     if (one < two)
00244     {
00245         /* printf( "%u < %u\n",one,two); */
00246         return -1;
00247     }
00248         
00249     /* Equal : 0 */
00250     /* printf( "%u == %u\n",one,two); */
00251     return 0;
00252 }
00253 
00254 /* ---------------------------------------------------------------------- */
00255 int32_t ph_qs_sort_uint32_t( const uint32_t nelements, 
00256                              uint32_t      *array,
00257                              const uint32_t method)
00258 {
00259     if (nelements == 0) return 0;
00260     
00261     /* We use the temp for an intermediate swap */
00262     uint8_t *temp = (uint8_t *)malloc(sizeof(uint32_t));
00263    
00264     if (temp == NULL) return -1;
00265     
00266     if (method)
00267     {
00268         ph_quicksort_iterative( array, 
00269                                 0, 
00270                                 nelements-1,
00271                                 sizeof(uint32_t),
00272                                 temp,
00273                                 ph_qs_compare_uint32_t );
00274     }
00275     else
00276     {
00277         ph_quicksort_recursive( array, 
00278                                 0, 
00279                                 nelements-1,
00280                                 sizeof(uint32_t),
00281                                 temp,
00282                                 ph_qs_compare_uint32_t );
00283     }
00284 
00285     free(temp);
00286 
00287     return 0;
00288 }
00289 
00290 /* ---------------------------------------------------------------------- */
00291 int32_t ph_qs_randomfill_uint32_t( const uint32_t  nelements, 
00292                                    uint32_t       *array,
00293                                    const uint32_t  maxval     )
00294 {
00295     uint32_t i = 0;
00296     
00297     for ( i = 0; i < nelements; i++ )
00298         array[i] = ((uint32_t)random()) % maxval;
00299 
00300     return 0;
00301 }
00302 
00303 /* ---------------------------------------------------------------------- */
00304 /* Print the uint32_t array */
00305 int32_t ph_qs_print_uint32_t( const uint32_t nelements, 
00306                               const uint32_t *array )
00307 {
00308     uint32_t i = 0;
00309     
00310     printf("array[ ");
00311     
00312     for ( i = 0; i < nelements; i++ )
00313         printf("%4u%s",array[i],(i == (nelements-1)) ? " ];\n" : ", ");
00314 
00315     return 0;
00316 }
00317 
00318 /* ---------------------------------------------------------------------- */
00319 /* Verify the uint32_t array is sorted */
00320 int32_t ph_qs_verify_uint32_t( const uint32_t nelements, 
00321                                const uint32_t *array )
00322 {
00323     uint32_t i = 0;
00324 
00325     for (i = 0; i < nelements - 1; i++ )
00326         if (array[i] > array[i+1])
00327             return -1;
00328     
00329     return 0;
00330 }
00331 
00332 /* ---------------------------------------------------------------------- */
00333 /* compare the arrays */
00334 int32_t ph_qs_compare_arrays_uint32_t( const uint32_t nelements,
00335                                        const uint32_t *array1,
00336                                        const uint32_t *array2 )
00337 {
00338     uint32_t i = 0;
00339 
00340     for (i = 0; i < nelements - 1; i++ )
00341         if (array1[i] != array2[i])
00342         {
00343             printf("array1[%d]:%u != array2[%d]:%u\n",
00344                     i,array1[i],i,array2[i]);
00345             return -1;
00346         }
00347     
00348     return 0;
00349 }
00350 
00351 /* ---------------------------------------------------------------------- */
00352 int main (int argc, char *argv[] )
00353 {
00354     uint32_t        i           = 0;
00355     uint32_t        rc          = 0;
00356     const uint32_t  nloops      = 1000;
00357     const uint32_t  nelements   = 1203;
00358     uint32_t       *array       = (uint32_t *)calloc(nelements,sizeof(uint32_t));
00359     uint32_t       *copyarray   = (uint32_t *)calloc(nelements,sizeof(uint32_t));
00360     
00361     if (array == NULL)
00362     {
00363         printf("Error: uint32_t array allocation failed.\n");
00364         return -1;
00365     }
00366 
00367     /* Seed the random number generator */
00368     srandom(time(NULL));
00369 
00370     for (i = 0; i < nloops; i++ )
00371     {
00372         /* Create a new randomized array and print it */
00373         /* set the maximum value of the uint32_t array elements in the
00374          * last argument to the randomizing function */
00375         rc = ph_qs_randomfill_uint32_t( nelements, array, 11256 );
00376         //rc = ph_qs_print_uint32_t( nelements, array );
00377 
00378         /* Make a copy of the array */
00379         memcpy(copyarray,array,sizeof(uint32_t)*nelements);
00380 
00381         /* 1.) Test the recursive quicksort */
00382 
00383         /* reset the statistics */
00384         ph_glbl_swaps   = 0;
00385         ph_glbl_compares= 0;
00386 
00387         /* Sort the array and print it */
00388         rc = ph_qs_sort_uint32_t( nelements, array, 0);
00389         //rc = ph_qs_print_uint32_t( nelements, array );
00390 
00391         /* Print the statistics */
00392         printf("recursive - nelements:%u swaps:%u compares:%u\n",
00393                nelements,ph_glbl_swaps,ph_glbl_compares);
00394         
00395         rc = ph_qs_verify_uint32_t( nelements, array );
00396         if (rc == -1)
00397         {
00398             printf("ERROR: Recursive sort failed!!!\n");
00399             ph_qs_print_uint32_t( nelements, array );
00400             return -1;
00401         }
00402 
00403         /* 2.) Test the iterative quicksort */
00404 
00405         /* reset the statistics */
00406         ph_glbl_swaps   = 0;
00407         ph_glbl_compares= 0;
00408 
00409         /* Sort the array and print it */
00410         rc = ph_qs_sort_uint32_t( nelements, copyarray, 1 );
00411         //rc = ph_qs_print_uint32_t( nelements, array );
00412 
00413         /* Print the statistics */
00414         printf("iterative - nelements:%u swaps:%u compares:%u\n",
00415                nelements,ph_glbl_swaps,ph_glbl_compares);
00416         
00417         rc = ph_qs_verify_uint32_t( nelements, copyarray );
00418         if (rc == -1)
00419         {
00420             printf("ERROR: Iterative sort failed!!!\n");
00421             ph_qs_print_uint32_t( nelements, copyarray );
00422             return -1;
00423         }
00424 
00425         if (ph_qs_compare_arrays_uint32_t(nelements, array, copyarray ) == 0)
00426         {
00427             printf("Recursive and Iterative arrays are the same\n");
00428         }
00429         else
00430         {
00431             printf("Recursive and Iterative arrays are different\n");
00432         }
00433     }
00434     
00435     return 0;
00436 }
00437 
00438 
00439 




Copyright (C) 2002 - 2007 Philip D.S. Thoren ( pthoren@users.sourceforge.net )
University Of Massachusetts at Lowell
Robotics Lab
SourceForge.net Logo

Generated on Sat Jun 16 02:44:07 2007 for phission by  doxygen 1.4.4