diff options
| author | Alan Mishchenko <alanmi@berkeley.edu> | 2012-02-19 13:19:35 -0800 |
|---|---|---|
| committer | Alan Mishchenko <alanmi@berkeley.edu> | 2012-02-19 13:19:35 -0800 |
| commit | c2b2e99284727cc0b1c8122b267746cf598846ab (patch) | |
| tree | 78f7e5e30b3174eff68ff8667f083ff29353189e /src/misc | |
| parent | 596bbbe6dc3f8311a5166269d651d50ec6b2dff8 (diff) | |
| download | abc-c2b2e99284727cc0b1c8122b267746cf598846ab.tar.gz abc-c2b2e99284727cc0b1c8122b267746cf598846ab.tar.bz2 abc-c2b2e99284727cc0b1c8122b267746cf598846ab.zip | |
Added QuickSort based on 3-way partitioning.
Diffstat (limited to 'src/misc')
| -rw-r--r-- | src/misc/util/abc_global.h | 10 | ||||
| -rw-r--r-- | src/misc/util/utilSort.c | 20 |
2 files changed, 15 insertions, 15 deletions
diff --git a/src/misc/util/abc_global.h b/src/misc/util/abc_global.h index 031dda33..38a27fe7 100644 --- a/src/misc/util/abc_global.h +++ b/src/misc/util/abc_global.h @@ -327,11 +327,11 @@ static inline int Abc_PrimeCudd( unsigned int p ) // sorting extern void Abc_MergeSort( int * pInput, int nSize ); extern int * Abc_MergeSortCost( int * pCosts, int nSize ); -extern void Abc_QuickSort1( word * pData, int nSize, int fDecrement ); -extern void Abc_QuickSort2( word * pData, int nSize, int fDecrement ); -extern void Abc_QuickSort3( word * pData, int nSize, int fDecrement ); -extern void Abc_QuickSortCostData( int * pCosts, int nSize, int fDecrement, word * pData, int * pResult ); -extern int * Abc_QuickSortCost( int * pCosts, int nSize, int fDecrement ); +extern void Abc_QuickSort1( word * pData, int nSize, int fDecrease ); +extern void Abc_QuickSort2( word * pData, int nSize, int fDecrease ); +extern void Abc_QuickSort3( word * pData, int nSize, int fDecrease ); +extern void Abc_QuickSortCostData( int * pCosts, int nSize, int fDecrease, word * pData, int * pResult ); +extern int * Abc_QuickSortCost( int * pCosts, int nSize, int fDecrease ); ABC_NAMESPACE_HEADER_END diff --git a/src/misc/util/utilSort.c b/src/misc/util/utilSort.c index 1cfe8a00..380a8885 100644 --- a/src/misc/util/utilSort.c +++ b/src/misc/util/utilSort.c @@ -473,10 +473,10 @@ int Abc_QuickSort1CompareDec( word * p1, word * p2 ) return 1; return 0; } -void Abc_QuickSort1( word * pData, int nSize, int fDecrement ) +void Abc_QuickSort1( word * pData, int nSize, int fDecrease ) { int i, fVerify = 0; - if ( fDecrement ) + if ( fDecrease ) { qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareDec ); if ( fVerify ) @@ -658,10 +658,10 @@ void Abc_QuickSort3Dec_rec( word * pData, int l, int r ) Abc_QuickSort3Dec_rec( pData, i, r ); } -void Abc_QuickSort2( word * pData, int nSize, int fDecrement ) +void Abc_QuickSort2( word * pData, int nSize, int fDecrease ) { int i, fVerify = 0; - if ( fDecrement ) + if ( fDecrease ) { Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 ); if ( fVerify ) @@ -676,10 +676,10 @@ void Abc_QuickSort2( word * pData, int nSize, int fDecrement ) assert( (unsigned)pData[i-1] <= (unsigned)pData[i] ); } } -void Abc_QuickSort3( word * pData, int nSize, int fDecrement ) +void Abc_QuickSort3( word * pData, int nSize, int fDecrease ) { int i, fVerify = 0; - if ( fDecrement ) + if ( fDecrease ) { Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 ); if ( fVerify ) @@ -706,20 +706,20 @@ void Abc_QuickSort3( word * pData, int nSize, int fDecrement ) SeeAlso [] ***********************************************************************/ -void Abc_QuickSortCostData( int * pCosts, int nSize, int fDecrement, word * pData, int * pResult ) +void Abc_QuickSortCostData( int * pCosts, int nSize, int fDecrease, word * pData, int * pResult ) { int i; for ( i = 0; i < nSize; i++ ) pData[i] = ((word)i << 32) | pCosts[i]; - Abc_QuickSort3( pData, nSize, fDecrement ); + Abc_QuickSort3( pData, nSize, fDecrease ); for ( i = 0; i < nSize; i++ ) pResult[i] = (int)(pData[i] >> 32); } -int * Abc_QuickSortCost( int * pCosts, int nSize, int fDecrement ) +int * Abc_QuickSortCost( int * pCosts, int nSize, int fDecrease ) { word * pData = ABC_ALLOC( word, nSize ); int * pResult = ABC_ALLOC( int, nSize ); - Abc_QuickSortCostData( pCosts, nSize, fDecrement, pData, pResult ); + Abc_QuickSortCostData( pCosts, nSize, fDecrease, pData, pResult ); ABC_FREE( pData ); return pResult; } |