phQuicksort.cpp

Go to the documentation of this file.

/* ---------------------------------------------------------------------------
    Phission : 
        Realtime Vision Processing System
    
    Copyright (C) 2003-2006 Philip D.S. Thoren (pthoren@cs.uml.edu)
    University of Massachusetts at Lowell,
    Laboratory for Artificial Intelligence and Robotics
    
    This file is part of Phission.

    Phission is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    Phission is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with Phission; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 ---------------------------------------------------------------------------*/
#ifdef HAVE_CONFIG_H
    #include <phissionconfig.h>
#endif

#include <phStandard.h>

#include <phQuicksort.h>

#include <phError.h>
#include <phMemory.h>
#include <phPrint.h>

#ifdef __cplusplus
extern "C" {
#endif

/* ---------------------------------------------------------------------- */
int32_t ph_quicksort_partition(const void       *arr,
                               const int32_t     low,
                               const int32_t     high,
                               const uint32_t    size,
                               uint8_t          *tempptr,
                               ph_qs_compare_fn  compare
                              )
{
    uint32_t      i     = 0;
    uint32_t      lim   = (high - low) + 1;
    uint32_t      store = low;
    const int32_t pivot = (random() % (high - low)) + low;

    uint8_t *curptr    = ((uint8_t *)arr) + low  * size;
    uint8_t *pivotptr  = ((uint8_t *)arr) + pivot* size;
    uint8_t *highptr   = ((uint8_t *)arr) + high * size;
    uint8_t *storeptr  = curptr;

    /* If we're down to a parition of size 2, then we only need to compare
     * two numbers and don't need to execute the entire body of this
     * function */
    if (lim == 2)
    {
        if (compare(curptr,highptr) > 0)
            ph_qsMemswap(curptr,highptr,tempptr,size);
    
        return high;
    }

    /* Put the pivot value at the end of the partition */
    ph_qsMemswap(highptr,pivotptr,tempptr,size);

    /* Loop through all the elements */
    for (i = 0; i < lim - 1; i++ )
    {
        /* if i < pivot */
        /* compare returns 0:same, -1:less-than 1:greater-than */
        if (compare(curptr,highptr) <= 0)
        {
            /* Swap the current value and the one in the store */
            ph_qsMemswap(curptr,storeptr,tempptr,size);
            
            /* Increment the store variables */
            store++;
            storeptr += size;
        }
        curptr += size;
    }

    /* Bring the pivot value into the correct place within the parition */
    ph_qsMemswap(highptr,storeptr,tempptr,size);

    /* Everything above the pivot index is greater in value than the
     * pivot and everything below the pivot index is less than or equal to
     * the pivot value */

    return store;
}

/* ---------------------------------------------------------------------- */
void ph_quicksort_recursive( const void         *arr, 
                             const int32_t       low, 
                             const int32_t       high,
                             const uint32_t      size,
                             uint8_t            *tempptr,
                             ph_qs_compare_fn    compare )
{
    if (low < high)
    {
        int32_t mid = ph_quicksort_partition(arr,low,high,size,tempptr,compare);
        
        ph_quicksort_recursive(arr, low,    mid-1,size,tempptr,compare);
        ph_quicksort_recursive(arr, mid+1,  high, size,tempptr,compare);
    }
}
 
/* ---------------------------------------------------------------------- */
typedef struct ph_qs_stack_t
{
    struct ph_qs_stack_t   *next;
    int32_t                 low;
    int32_t                 high;
} ph_qs_stack_type;
    
/* ---------------------------------------------------------------------- */
void ph_quicksort_iterative( const void         *arr, 
                             const int32_t       low, 
                             const int32_t       high,
                             const uint32_t      size,
                             uint8_t            *tempptr,
                             ph_qs_compare_fn    compare )
{
    phFUNCTION("ph_quicksort_iterative")
    int32_t l = 0;
    int32_t h = 0;
    int32_t mid = 0;
    ph_qs_stack_type *stack_element = NULL;
    ph_qs_stack_type *stack = (ph_qs_stack_type *)phMalloc(sizeof(ph_qs_stack_type));
    phCHECK_PTR(stack,"phMalloc",
                "phMalloc failed to allocated stack element");

    /* Push the first */
    stack->next = NULL;
    stack->low  = low;
    stack->high = high;

    while (stack != NULL)
    {
        /* Pop */
        stack_element = stack;
        stack = stack->next;
        l = stack_element->low;
        h = stack_element->high;
        phFree(stack_element);
        
        if (l < h)
        {
            /* Partition the array */
            mid = ph_quicksort_partition(arr,l,h,size,tempptr,compare);
        
            /* Push */
            if (l < mid-1) /* Try to avoid as many allocations as possible */
            {   
                stack_element = (ph_qs_stack_type *)malloc(sizeof(ph_qs_stack_type));
                phCHECK_PTR(stack_element,"phMalloc",
                            "phMalloc failed to allocated stack element");
                stack_element->next = stack;
                stack_element->low  = l;
                stack_element->high = mid-1;
                stack = stack_element;
            }

            /* Push */
            if (mid+1 < h) /* Try to avoid as many allocations as possible */
            {
                stack_element = (ph_qs_stack_type *)malloc(sizeof(ph_qs_stack_type));
                phCHECK_PTR(stack_element,"phMalloc",
                            "phMalloc failed to allocated stack element");
                stack_element->next = stack;
                stack_element->low  = mid+1;
                stack_element->high = h;
                stack = stack_element;
            }
        }
    }

error:
    return;
}
                      
/* ---------------------------------------------------------------------- */
int32_t ph_qs_compare_uint32_t(const void *_one, const void *_two)
{
    uint32_t one            = *((uint32_t *)_one);
    uint32_t two            = *((uint32_t *)_two);

    /* Greater than : 1 */
    if (one > two)
    {
        /* printf( "%u > %u\n",one,two); */
        return 1;
    }
    
    /* Less than : -1 */
    if (one < two)
    {
        /* printf( "%u < %u\n",one,two); */
        return -1;
    }
        
    /* Equal : 0 */
    /* printf( "%u == %u\n",one,two); */
    return phSUCCESS;
}

/* ---------------------------------------------------------------------- */
int32_t ph_qs_sort_uint32_t( const uint32_t nelements, 
                             uint32_t      *array,
                             const uint32_t method )
{
    if (nelements == 0) return phSUCCESS;
    
    /* We use the temp for an intermediate swap */
    uint8_t *temp = (uint8_t *)malloc(sizeof(uint32_t));
   
    if (temp == NULL) return phFAIL;
   
    if (method)
    {
        ph_quicksort_iterative( array, 
                                0, 
                                nelements-1,
                                sizeof(uint32_t),
                                temp,
                                ph_qs_compare_uint32_t );
    }
    else
    {
        ph_quicksort_recursive( array, 
                                0, 
                                nelements-1,
                                sizeof(uint32_t),
                                temp,
                                ph_qs_compare_uint32_t );
    } 

    phFree(temp);

    return phSUCCESS;
}

/* ---------------------------------------------------------------------- */
int32_t ph_qs_randomfill_uint32_t( const uint32_t  nelements, 
                                   uint32_t       *array,
                                   const uint32_t  maxval     )
{
    uint32_t i = 0;
    
    for ( i = 0; i < nelements; i++ )
        array[i] = ((uint32_t)random()) % maxval;

    return phSUCCESS;
}

/* ---------------------------------------------------------------------- */
/* Print the uint32_t array */
int32_t ph_qs_print_uint32_t(const uint32_t nelements, 
                             const uint32_t *array )
{
    uint32_t i = 0;
    
    printf("array[ ");
    
    for ( i = 0; i < nelements; i++ )
        printf("%4u%s",array[i],(i == (nelements-1)) ? " ];\n" : ", ");

    return phSUCCESS;
}

/* ---------------------------------------------------------------------- */
/* Verify the uint32_t array is sorted */
int32_t ph_qs_verify_uint32_t(const uint32_t nelements, 
                              const uint32_t *array )
{
    uint32_t i = 0;

    for (i = 0; i < nelements - 1; i++ )
        if (array[i] > array[i+1])
            return phFAIL;
    
    return phSUCCESS;
}

#ifdef __cplusplus
}
#endif

Copyright (C) 2002 - 2007

Philip D.S. Thoren ( pthoren@users.sourceforge.net ) University Of Massachusetts at Lowell Robotics Lab

---