abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
utilSort.c File Reference
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "abc_global.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START void Abc_SortMerge (int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
 DECLARATIONS ///. More...
 
void Abc_Sort_rec (int *pInBeg, int *pInEnd, int *pOutBeg)
 
void Abc_MergeSort (int *pInput, int nSize)
 
void Abc_MergeSortCostMerge (int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
 
void Abc_MergeSortCost_rec (int *pInBeg, int *pInEnd, int *pOutBeg)
 
int * Abc_MergeSortCost (int *pCosts, int nSize)
 
int Abc_SortNumCompare (int *pNum1, int *pNum2)
 
void Abc_SortTest ()
 
int Abc_QuickSort1CompareInc (word *p1, word *p2)
 
int Abc_QuickSort1CompareDec (word *p1, word *p2)
 
void Abc_QuickSort1 (word *pData, int nSize, int fDecrease)
 
static void Abc_SelectSortInc (word *pData, int nSize)
 
static void Abc_SelectSortDec (word *pData, int nSize)
 
void Abc_QuickSort2Inc_rec (word *pData, int l, int r)
 
void Abc_QuickSort2Dec_rec (word *pData, int l, int r)
 
void Abc_QuickSort3Inc_rec (word *pData, int l, int r)
 
void Abc_QuickSort3Dec_rec (word *pData, int l, int r)
 
void Abc_QuickSort2 (word *pData, int nSize, int fDecrease)
 
void Abc_QuickSort3 (word *pData, int nSize, int fDecrease)
 
void Abc_QuickSortCostData (int *pCosts, int nSize, int fDecrease, word *pData, int *pResult)
 
int * Abc_QuickSortCost (int *pCosts, int nSize, int fDecrease)
 
void Abc_QuickSortTest ()
 

Function Documentation

void Abc_MergeSort ( int *  pInput,
int  nSize 
)

Function*************************************************************

Synopsis [Returns the sorted array of integers.]

Description [This procedure is about 10% faster than qsort().]

SideEffects []

SeeAlso []

Definition at line 129 of file utilSort.c.

130 {
131  int * pOutput;
132  if ( nSize < 2 )
133  return;
134  pOutput = (int *) malloc( sizeof(int) * nSize );
135  Abc_Sort_rec( pInput, pInput + nSize, pOutput );
136  free( pOutput );
137 }
malloc
char * malloc()
free
VOID_HACK free()
Abc_Sort_rec
void Abc_Sort_rec(int *pInBeg, int *pInEnd, int *pOutBeg)
Definition: utilSort.c:80
int* Abc_MergeSortCost ( int *  pCosts,
int  nSize 
)

Function*************************************************************

Synopsis [Sorting procedure.]

Description [Returns permutation for the non-decreasing order of costs.]

SideEffects []

SeeAlso []

Definition at line 238 of file utilSort.c.

239 {
240  int i, * pResult, * pInput, * pOutput;
241  pResult = (int *) calloc( sizeof(int), nSize );
242  if ( nSize < 2 )
243  return pResult;
244  pInput = (int *) malloc( sizeof(int) * 2 * nSize );
245  pOutput = (int *) malloc( sizeof(int) * 2 * nSize );
246  for ( i = 0; i < nSize; i++ )
247  pInput[2*i] = i, pInput[2*i+1] = pCosts[i];
248  Abc_MergeSortCost_rec( pInput, pInput + 2*nSize, pOutput );
249  for ( i = 0; i < nSize; i++ )
250  pResult[i] = pInput[2*i];
251  free( pOutput );
252  free( pInput );
253  return pResult;
254 }
malloc
char * malloc()
free
VOID_HACK free()
Abc_MergeSortCost_rec
void Abc_MergeSortCost_rec(int *pInBeg, int *pInEnd, int *pOutBeg)
Definition: utilSort.c:183
calloc
char * calloc()
void Abc_MergeSortCost_rec ( int *  pInBeg,
int *  pInEnd,
int *  pOutBeg 
)

Function*************************************************************

Synopsis [Recursive sorting.]

Description []

SideEffects []

SeeAlso []

Definition at line 183 of file utilSort.c.

184 {
185  int nSize = (pInEnd - pInBeg)/2;
186  assert( nSize > 0 );
187  if ( nSize == 1 )
188  return;
189  if ( nSize == 2 )
190  {
191  if ( pInBeg[1] > pInBeg[3] )
192  {
193  pInBeg[1] ^= pInBeg[3];
194  pInBeg[3] ^= pInBeg[1];
195  pInBeg[1] ^= pInBeg[3];
196  pInBeg[0] ^= pInBeg[2];
197  pInBeg[2] ^= pInBeg[0];
198  pInBeg[0] ^= pInBeg[2];
199  }
200  }
201  else if ( nSize < 8 )
202  {
203  int temp, i, j, best_i;
204  for ( i = 0; i < nSize-1; i++ )
205  {
206  best_i = i;
207  for ( j = i+1; j < nSize; j++ )
208  if ( pInBeg[2*j+1] < pInBeg[2*best_i+1] )
209  best_i = j;
210  temp = pInBeg[2*i];
211  pInBeg[2*i] = pInBeg[2*best_i];
212  pInBeg[2*best_i] = temp;
213  temp = pInBeg[2*i+1];
214  pInBeg[2*i+1] = pInBeg[2*best_i+1];
215  pInBeg[2*best_i+1] = temp;
216  }
217  }
218  else
219  {
220  Abc_MergeSortCost_rec( pInBeg, pInBeg + 2*(nSize/2), pOutBeg );
221  Abc_MergeSortCost_rec( pInBeg + 2*(nSize/2), pInEnd, pOutBeg + 2*(nSize/2) );
222  Abc_MergeSortCostMerge( pInBeg, pInBeg + 2*(nSize/2), pInBeg + 2*(nSize/2), pInEnd, pOutBeg );
223  memcpy( pInBeg, pOutBeg, sizeof(int) * 2 * nSize );
224  }
225 }
Abc_MergeSortCost_rec
void Abc_MergeSortCost_rec(int *pInBeg, int *pInEnd, int *pOutBeg)
Definition: utilSort.c:183
Abc_MergeSortCostMerge
void Abc_MergeSortCostMerge(int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
Definition: utilSort.c:152
memcpy
char * memcpy()
assert
#define assert(ex)
Definition: util_old.h:213
void Abc_MergeSortCostMerge ( int *  p1Beg,
int *  p1End,
int *  p2Beg,
int *  p2End,
int *  pOut 
)

Function*************************************************************

Synopsis [Merging two lists of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 152 of file utilSort.c.

153 {
154  int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
155  int * pOutBeg = pOut;
156  while ( p1Beg < p1End && p2Beg < p2End )
157  {
158  if ( p1Beg[1] == p2Beg[1] )
159  *pOut++ = *p1Beg++, *pOut++ = *p1Beg++, *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
160  else if ( p1Beg[1] < p2Beg[1] )
161  *pOut++ = *p1Beg++, *pOut++ = *p1Beg++;
162  else // if ( p1Beg[1] > p2Beg[1] )
163  *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
164  }
165  while ( p1Beg < p1End )
166  *pOut++ = *p1Beg++, *pOut++ = *p1Beg++;
167  while ( p2Beg < p2End )
168  *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
169  assert( pOut - pOutBeg == nEntries );
170 }
assert
#define assert(ex)
Definition: util_old.h:213
void Abc_QuickSort1 ( word *  pData,
int  nSize,
int  fDecrease 
)

Definition at line 477 of file utilSort.c.

478 {
479  int i, fVerify = 0;
480  if ( fDecrease )
481  {
482  qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareDec );
483  if ( fVerify )
484  for ( i = 1; i < nSize; i++ )
485  assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
486  }
487  else
488  {
489  qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareInc );
490  if ( fVerify )
491  for ( i = 1; i < nSize; i++ )
492  assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
493  }
494 }
Abc_QuickSort1CompareInc
int Abc_QuickSort1CompareInc(word *p1, word *p2)
Definition: utilSort.c:461
Abc_QuickSort1CompareDec
int Abc_QuickSort1CompareDec(word *p1, word *p2)
Definition: utilSort.c:469
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
assert
#define assert(ex)
Definition: util_old.h:213
int Abc_QuickSort1CompareDec ( word *  p1,
word *  p2 
)

Definition at line 469 of file utilSort.c.

470 {
471  if ( (unsigned)(*p1) > (unsigned)(*p2) )
472  return -1;
473  if ( (unsigned)(*p1) < (unsigned)(*p2) )
474  return 1;
475  return 0;
476 }
int Abc_QuickSort1CompareInc ( word *  p1,
word *  p2 
)

Function*************************************************************

Synopsis [QuickSort algorithm as implemented by qsort().]

Description []

SideEffects []

SeeAlso []

Definition at line 461 of file utilSort.c.

462 {
463  if ( (unsigned)(*p1) < (unsigned)(*p2) )
464  return -1;
465  if ( (unsigned)(*p1) > (unsigned)(*p2) )
466  return 1;
467  return 0;
468 }
void Abc_QuickSort2 ( word *  pData,
int  nSize,
int  fDecrease 
)

Definition at line 662 of file utilSort.c.

663 {
664  int i, fVerify = 0;
665  if ( fDecrease )
666  {
667  Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
668  if ( fVerify )
669  for ( i = 1; i < nSize; i++ )
670  assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
671  }
672  else
673  {
674  Abc_QuickSort2Inc_rec( pData, 0, nSize - 1 );
675  if ( fVerify )
676  for ( i = 1; i < nSize; i++ )
677  assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
678  }
679 }
Abc_QuickSort2Inc_rec
void Abc_QuickSort2Inc_rec(word *pData, int l, int r)
Definition: utilSort.c:538
Abc_QuickSort2Dec_rec
void Abc_QuickSort2Dec_rec(word *pData, int l, int r)
Definition: utilSort.c:564
assert
#define assert(ex)
Definition: util_old.h:213
void Abc_QuickSort2Dec_rec ( word *  pData,
int  l,
int  r 
)

Definition at line 564 of file utilSort.c.

565 {
566  word v = pData[r];
567  int i = l-1, j = r;
568  if ( l >= r )
569  return;
570  assert( l < r );
571  if ( r - l < 10 )
572  {
573  Abc_SelectSortDec( pData + l, r - l + 1 );
574  return;
575  }
576  while ( 1 )
577  {
578  while ( (unsigned)pData[++i] > (unsigned)v );
579  while ( (unsigned)v > (unsigned)pData[--j] )
580  if ( j == l )
581  break;
582  if ( i >= j )
583  break;
584  ABC_SWAP( word, pData[i], pData[j] );
585  }
586  ABC_SWAP( word, pData[i], pData[r] );
587  Abc_QuickSort2Dec_rec( pData, l, i-1 );
588  Abc_QuickSort2Dec_rec( pData, i+1, r );
589 }
Abc_SelectSortDec
static void Abc_SelectSortDec(word *pData, int nSize)
Definition: utilSort.c:525
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
Abc_QuickSort2Dec_rec
void Abc_QuickSort2Dec_rec(word *pData, int l, int r)
Definition: utilSort.c:564
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
assert
#define assert(ex)
Definition: util_old.h:213
void Abc_QuickSort2Inc_rec ( word *  pData,
int  l,
int  r 
)

Definition at line 538 of file utilSort.c.

539 {
540  word v = pData[r];
541  int i = l-1, j = r;
542  if ( l >= r )
543  return;
544  assert( l < r );
545  if ( r - l < 10 )
546  {
547  Abc_SelectSortInc( pData + l, r - l + 1 );
548  return;
549  }
550  while ( 1 )
551  {
552  while ( (unsigned)pData[++i] < (unsigned)v );
553  while ( (unsigned)v < (unsigned)pData[--j] )
554  if ( j == l )
555  break;
556  if ( i >= j )
557  break;
558  ABC_SWAP( word, pData[i], pData[j] );
559  }
560  ABC_SWAP( word, pData[i], pData[r] );
561  Abc_QuickSort2Inc_rec( pData, l, i-1 );
562  Abc_QuickSort2Inc_rec( pData, i+1, r );
563 }
Abc_QuickSort2Inc_rec
void Abc_QuickSort2Inc_rec(word *pData, int l, int r)
Definition: utilSort.c:538
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
Abc_SelectSortInc
static void Abc_SelectSortInc(word *pData, int nSize)
Definition: utilSort.c:513
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
assert
#define assert(ex)
Definition: util_old.h:213
void Abc_QuickSort3 ( word *  pData,
int  nSize,
int  fDecrease 
)

Definition at line 680 of file utilSort.c.

681 {
682  int i, fVerify = 1;
683  if ( fDecrease )
684  {
685  Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
686  if ( fVerify )
687  for ( i = 1; i < nSize; i++ )
688  assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
689  }
690  else
691  {
692  Abc_QuickSort2Inc_rec( pData, 0, nSize - 1 );
693  if ( fVerify )
694  for ( i = 1; i < nSize; i++ )
695  assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
696  }
697 }
Abc_QuickSort2Inc_rec
void Abc_QuickSort2Inc_rec(word *pData, int l, int r)
Definition: utilSort.c:538
Abc_QuickSort2Dec_rec
void Abc_QuickSort2Dec_rec(word *pData, int l, int r)
Definition: utilSort.c:564
assert
#define assert(ex)
Definition: util_old.h:213
void Abc_QuickSort3Dec_rec ( word *  pData,
int  l,
int  r 
)

Definition at line 626 of file utilSort.c.

627 {
628  word v = pData[r];
629  int k, i = l-1, j = r, p = l-1, q = r;
630  if ( l >= r )
631  return;
632  assert( l < r );
633  if ( r - l < 10 )
634  {
635  Abc_SelectSortDec( pData + l, r - l + 1 );
636  return;
637  }
638  while ( 1 )
639  {
640  while ( (unsigned)pData[++i] > (unsigned)v );
641  while ( (unsigned)v > (unsigned)pData[--j] )
642  if ( j == l )
643  break;
644  if ( i >= j )
645  break;
646  ABC_SWAP( word, pData[i], pData[j] );
647  if ( (unsigned)pData[i] == (unsigned)v )
648  { p++; ABC_SWAP( word, pData[p], pData[i] ); }
649  if ( (unsigned)v == (unsigned)pData[j] )
650  { q--; ABC_SWAP( word, pData[j], pData[q] ); }
651  }
652  ABC_SWAP( word, pData[i], pData[r] );
653  j = i-1; i = i+1;
654  for ( k = l; k < p; k++, j-- )
655  ABC_SWAP( word, pData[k], pData[j] );
656  for ( k = r-1; k > q; k--, i++ )
657  ABC_SWAP( word, pData[i], pData[k] );
658  Abc_QuickSort3Dec_rec( pData, l, j );
659  Abc_QuickSort3Dec_rec( pData, i, r );
660 }
Abc_SelectSortDec
static void Abc_SelectSortDec(word *pData, int nSize)
Definition: utilSort.c:525
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Abc_QuickSort3Dec_rec
void Abc_QuickSort3Dec_rec(word *pData, int l, int r)
Definition: utilSort.c:626
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
assert
#define assert(ex)
Definition: util_old.h:213
void Abc_QuickSort3Inc_rec ( word *  pData,
int  l,
int  r 
)

Definition at line 591 of file utilSort.c.

592 {
593  word v = pData[r];
594  int k, i = l-1, j = r, p = l-1, q = r;
595  if ( l >= r )
596  return;
597  assert( l < r );
598  if ( r - l < 10 )
599  {
600  Abc_SelectSortInc( pData + l, r - l + 1 );
601  return;
602  }
603  while ( 1 )
604  {
605  while ( (unsigned)pData[++i] < (unsigned)v );
606  while ( (unsigned)v < (unsigned)pData[--j] )
607  if ( j == l )
608  break;
609  if ( i >= j )
610  break;
611  ABC_SWAP( word, pData[i], pData[j] );
612  if ( (unsigned)pData[i] == (unsigned)v )
613  { p++; ABC_SWAP( word, pData[p], pData[i] ); }
614  if ( (unsigned)v == (unsigned)pData[j] )
615  { q--; ABC_SWAP( word, pData[j], pData[q] ); }
616  }
617  ABC_SWAP( word, pData[i], pData[r] );
618  j = i-1; i = i+1;
619  for ( k = l; k < p; k++, j-- )
620  ABC_SWAP( word, pData[k], pData[j] );
621  for ( k = r-1; k > q; k--, i++ )
622  ABC_SWAP( word, pData[i], pData[k] );
623  Abc_QuickSort3Inc_rec( pData, l, j );
624  Abc_QuickSort3Inc_rec( pData, i, r );
625 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
Abc_SelectSortInc
static void Abc_SelectSortInc(word *pData, int nSize)
Definition: utilSort.c:513
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
Abc_QuickSort3Inc_rec
void Abc_QuickSort3Inc_rec(word *pData, int l, int r)
Definition: utilSort.c:591
assert
#define assert(ex)
Definition: util_old.h:213
int* Abc_QuickSortCost ( int *  pCosts,
int  nSize,
int  fDecrease 
)

Definition at line 719 of file utilSort.c.

720 {
721  word * pData = ABC_ALLOC( word, nSize );
722  int * pResult = ABC_ALLOC( int, nSize );
723  Abc_QuickSortCostData( pCosts, nSize, fDecrease, pData, pResult );
724  ABC_FREE( pData );
725  return pResult;
726 }
Abc_QuickSortCostData
void Abc_QuickSortCostData(int *pCosts, int nSize, int fDecrease, word *pData, int *pResult)
Definition: utilSort.c:710
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
void Abc_QuickSortCostData ( int *  pCosts,
int  nSize,
int  fDecrease,
word *  pData,
int *  pResult 
)

Function*************************************************************

Synopsis [Wrapper around QuickSort to sort entries based on cost.]

Description []

SideEffects []

SeeAlso []

Definition at line 710 of file utilSort.c.

711 {
712  int i;
713  for ( i = 0; i < nSize; i++ )
714  pData[i] = ((word)i << 32) | pCosts[i];
715  Abc_QuickSort3( pData, nSize, fDecrease );
716  for ( i = 0; i < nSize; i++ )
717  pResult[i] = (int)(pData[i] >> 32);
718 }
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
Abc_QuickSort3
void Abc_QuickSort3(word *pData, int nSize, int fDecrease)
Definition: utilSort.c:680
void Abc_QuickSortTest ( )

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 742 of file utilSort.c.

743 {
744  int nSize = 1000000;
745  int fVerbose = 0;
746  word * pData1, * pData2;
747  int i;
748  abctime clk = Abc_Clock();
749  // generate numbers
750  pData1 = ABC_ALLOC( word, nSize );
751  pData2 = ABC_ALLOC( word, nSize );
752  srand( 1111 );
753  for ( i = 0; i < nSize; i++ )
754  pData2[i] = pData1[i] = ((word)i << 32) | rand();
755  Abc_PrintTime( 1, "Prepare ", Abc_Clock() - clk );
756  // perform sorting
757  clk = Abc_Clock();
758  Abc_QuickSort3( pData1, nSize, 1 );
759  Abc_PrintTime( 1, "Sort new", Abc_Clock() - clk );
760  // print the result
761  if ( fVerbose )
762  {
763  for ( i = 0; i < nSize; i++ )
764  printf( "(%d,%d) ", (int)(pData1[i] >> 32), (int)pData1[i] );
765  printf( "\n" );
766  }
767  // create new numbers
768  clk = Abc_Clock();
769  Abc_QuickSort1( pData2, nSize, 1 );
770  Abc_PrintTime( 1, "Sort old", Abc_Clock() - clk );
771  // print the result
772  if ( fVerbose )
773  {
774  for ( i = 0; i < nSize; i++ )
775  printf( "(%d,%d) ", (int)(pData2[i] >> 32), (int)pData2[i] );
776  printf( "\n" );
777  }
778  ABC_FREE( pData1 );
779  ABC_FREE( pData2 );
780 }
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Abc_PrintTime
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Abc_QuickSort3
void Abc_QuickSort3(word *pData, int nSize, int fDecrease)
Definition: utilSort.c:680
Abc_QuickSort1
void Abc_QuickSort1(word *pData, int nSize, int fDecrease)
Definition: utilSort.c:477
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
static void Abc_SelectSortDec ( word *  pData,
int  nSize 
)
inlinestatic

Definition at line 525 of file utilSort.c.

526 {
527  int i, j, best_i;
528  for ( i = 0; i < nSize-1; i++ )
529  {
530  best_i = i;
531  for ( j = i+1; j < nSize; j++ )
532  if ( (unsigned)pData[j] > (unsigned)pData[best_i] )
533  best_i = j;
534  ABC_SWAP( word, pData[i], pData[best_i] );
535  }
536 }
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
static void Abc_SelectSortInc ( word *  pData,
int  nSize 
)
inlinestatic

Function*************************************************************

Synopsis [QuickSort algorithm based on 2/3-way partitioning.]

Description [This code is based on the online presentation "QuickSort is Optimal" by Robert Sedgewick and Jon Bentley. http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

The first 32-bits of the input data contain values to be compared. The last 32-bits contain the user's data. When sorting is finished, the 64-bit words are ordered in the increasing order of their value ]

SideEffects []

SeeAlso []

Definition at line 513 of file utilSort.c.

514 {
515  int i, j, best_i;
516  for ( i = 0; i < nSize-1; i++ )
517  {
518  best_i = i;
519  for ( j = i+1; j < nSize; j++ )
520  if ( (unsigned)pData[j] < (unsigned)pData[best_i] )
521  best_i = j;
522  ABC_SWAP( word, pData[i], pData[best_i] );
523  }
524 }
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
void Abc_Sort_rec ( int *  pInBeg,
int *  pInEnd,
int *  pOutBeg 
)

Function*************************************************************

Synopsis [Recursive sorting.]

Description []

SideEffects []

SeeAlso []

Definition at line 80 of file utilSort.c.

81 {
82  int nSize = pInEnd - pInBeg;
83  assert( nSize > 0 );
84  if ( nSize == 1 )
85  return;
86  if ( nSize == 2 )
87  {
88  if ( pInBeg[0] > pInBeg[1] )
89  {
90  pInBeg[0] ^= pInBeg[1];
91  pInBeg[1] ^= pInBeg[0];
92  pInBeg[0] ^= pInBeg[1];
93  }
94  }
95  else if ( nSize < 8 )
96  {
97  int temp, i, j, best_i;
98  for ( i = 0; i < nSize-1; i++ )
99  {
100  best_i = i;
101  for ( j = i+1; j < nSize; j++ )
102  if ( pInBeg[j] < pInBeg[best_i] )
103  best_i = j;
104  temp = pInBeg[i];
105  pInBeg[i] = pInBeg[best_i];
106  pInBeg[best_i] = temp;
107  }
108  }
109  else
110  {
111  Abc_Sort_rec( pInBeg, pInBeg + nSize/2, pOutBeg );
112  Abc_Sort_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2 );
113  Abc_SortMerge( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg );
114  memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
115  }
116 }
Abc_Sort_rec
void Abc_Sort_rec(int *pInBeg, int *pInEnd, int *pOutBeg)
Definition: utilSort.c:80
memcpy
char * memcpy()
Abc_SortMerge
ABC_NAMESPACE_IMPL_START void Abc_SortMerge(int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
DECLARATIONS ///.
Definition: utilSort.c:49
assert
#define assert(ex)
Definition: util_old.h:213
ABC_NAMESPACE_IMPL_START void Abc_SortMerge ( int *  p1Beg,
int *  p1End,
int *  p2Beg,
int *  p2End,
int *  pOut 
)

DECLARATIONS ///.

CFile****************************************************************

FileName [utilSort.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Merge sort with user-specified cost.]

Synopsis [Merge sort with user-specified cost.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Feburary 13, 2011.]

Revision [

Id:
utilSort.c,v 1.00 2011/02/11 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Merging two lists of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 49 of file utilSort.c.

50 {
51  int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
52  int * pOutBeg = pOut;
53  while ( p1Beg < p1End && p2Beg < p2End )
54  {
55  if ( *p1Beg == *p2Beg )
56  *pOut++ = *p1Beg++, *pOut++ = *p2Beg++;
57  else if ( *p1Beg < *p2Beg )
58  *pOut++ = *p1Beg++;
59  else // if ( *p1Beg > *p2Beg )
60  *pOut++ = *p2Beg++;
61  }
62  while ( p1Beg < p1End )
63  *pOut++ = *p1Beg++;
64  while ( p2Beg < p2End )
65  *pOut++ = *p2Beg++;
66  assert( pOut - pOutBeg == nEntries );
67 }
assert
#define assert(ex)
Definition: util_old.h:213
int Abc_SortNumCompare ( int *  pNum1,
int *  pNum2 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 382 of file utilSort.c.

383 {
384  return *pNum1 - *pNum2;
385 }
void Abc_SortTest ( )

Function*************************************************************

Synopsis [Testing the sorting procedure.]

Description []

SideEffects []

SeeAlso []

Definition at line 398 of file utilSort.c.

399 {
400  int fUseNew = 0;
401  int i, nSize = 50000000;
402  int * pArray = (int *)malloc( sizeof(int) * nSize );
403  int * pPerm;
404  abctime clk;
405  // generate numbers
406  srand( 1000 );
407  for ( i = 0; i < nSize; i++ )
408  pArray[i] = rand();
409 
410  // try sorting
411  if ( fUseNew )
412  {
413  int fUseCost = 1;
414  if ( fUseCost )
415  {
416  clk = Abc_Clock();
417  pPerm = Abc_MergeSortCost( pArray, nSize );
418  Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
419  // check
420  for ( i = 1; i < nSize; i++ )
421  assert( pArray[pPerm[i-1]] <= pArray[pPerm[i]] );
422  free( pPerm );
423  }
424  else
425  {
426  clk = Abc_Clock();
427  Abc_MergeSort( pArray, nSize );
428  Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
429  // check
430  for ( i = 1; i < nSize; i++ )
431  assert( pArray[i-1] <= pArray[i] );
432  }
433  }
434  else
435  {
436  clk = Abc_Clock();
437  qsort( (void *)pArray, nSize, sizeof(int), (int (*)(const void *, const void *)) Abc_SortNumCompare );
438  Abc_PrintTime( 1, "Old sort", Abc_Clock() - clk );
439  // check
440  for ( i = 1; i < nSize; i++ )
441  assert( pArray[i-1] <= pArray[i] );
442  }
443 
444  free( pArray );
445 }
malloc
char * malloc()
free
VOID_HACK free()
Abc_MergeSort
void Abc_MergeSort(int *pInput, int nSize)
Definition: utilSort.c:129
Abc_SortNumCompare
int Abc_SortNumCompare(int *pNum1, int *pNum2)
Definition: utilSort.c:382
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Abc_PrintTime
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
Abc_MergeSortCost
int * Abc_MergeSortCost(int *pCosts, int nSize)
Definition: utilSort.c:238
pPerm
static int pPerm[13719]
Definition: rwrTemp.c:32
assert
#define assert(ex)
Definition: util_old.h:213
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278