diff options
Diffstat (limited to 'src/misc/util/utilSort.c')
-rw-r--r-- | src/misc/util/utilSort.c | 101 |
1 files changed, 101 insertions, 0 deletions
diff --git a/src/misc/util/utilSort.c b/src/misc/util/utilSort.c index 31890503..679017ed 100644 --- a/src/misc/util/utilSort.c +++ b/src/misc/util/utilSort.c @@ -137,6 +137,107 @@ void Abc_MergeSort( int * pInput, int nSize ) } +/**Function************************************************************* + + Synopsis [Merging two lists of entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SortMergeCost2( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost ) +{ + int nEntries = (p1End - p1Beg) + (p2End - p2Beg); + int * pOutBeg = pOut; + while ( p1Beg < p1End && p2Beg < p2End ) + { + if ( pCost[*p1Beg] == pCost[*p2Beg] ) + *pOut++ = *p1Beg++, *pOut++ = *p2Beg++; + else if ( pCost[*p1Beg] < pCost[*p2Beg] ) + *pOut++ = *p1Beg++; + else // if ( pCost[*p1Beg] > pCost[*p2Beg] ) + *pOut++ = *p2Beg++; + } + while ( p1Beg < p1End ) + *pOut++ = *p1Beg++; + while ( p2Beg < p2End ) + *pOut++ = *p2Beg++; + assert( pOut - pOutBeg == nEntries ); +} + +/**Function************************************************************* + + Synopsis [Recursive sorting.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SortCost2_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost ) +{ + int nSize = pInEnd - pInBeg; + assert( nSize > 0 ); + if ( nSize == 1 ) + return; + if ( nSize == 2 ) + { + if ( pCost[pInBeg[0]] > pCost[pInBeg[1]] ) + { + pInBeg[0] ^= pInBeg[1]; + pInBeg[1] ^= pInBeg[0]; + pInBeg[0] ^= pInBeg[1]; + } + } + else if ( nSize < 8 ) + { + int temp, i, j, best_i; + for ( i = 0; i < nSize-1; i++ ) + { + best_i = i; + for ( j = i+1; j < nSize; j++ ) + if ( pCost[pInBeg[j]] < pCost[pInBeg[best_i]] ) + best_i = j; + temp = pInBeg[i]; + pInBeg[i] = pInBeg[best_i]; + pInBeg[best_i] = temp; + } + } + else + { + Abc_SortCost2_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost ); + Abc_SortCost2_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost ); + Abc_SortMergeCost2( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost ); + memcpy( pInBeg, pOutBeg, sizeof(int) * nSize ); + } +} + +/**Function************************************************************* + + Synopsis [Returns the sorted array of integers.] + + Description [This procedure is about 10% faster than qsort().] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost ) +{ + int * pOutput; + if ( nSize < 2 ) + return; + pOutput = (int *) malloc( sizeof(int) * nSize ); + Abc_SortCost2_rec( pInput, pInput + nSize, pOutput, pCost ); + free( pOutput ); +} + /**Function************************************************************* |