Sort.cpp File Reference

00027 {
00028   n--;  // n-1 optimization
00029 
00030   // Bubble up i'th record
00031   for( register   int i = 0; i < n; i++ )
00032     for( register int j = n; j > i; j-- )
00033       if ( array[j] < array[j-1] )
00034       {
00035         swap( array, j, j-1 );
00036       }
00037 }

00145 {
00146   MaxHeap* heap = new MaxHeap( array, Size, Size );   // Build the maxheap
00147 
00148   for(int i = 0; i < Size; i++)     // Now sort by removing 
00149   {
00150     heap->removemax();               // The max value placed at end of heap
00151   }
00152   
00153   delete heap;
00154 }

00060 {
00061   for( register int i = incr; i < n; i += incr )
00062     for( register int j = i; 
00063           ( j >= incr ) && ( array[j] < array[j-incr] ); 
00064           j -= incr )
00065     {
00066       swap( array, j, j-incr );
00067     }
00068 }

00014 {
00015   // Insert i'th record on the top sorted part of the array
00016   for( register  int i = 1; i < n; i++ ) 
00017     for( register int j = i; 
00018           (j > 0) && ( array[j] < array[j-1] ); 
00019           j--  )
00020     {
00021       swap( array, j, j-1 );
00022     }
00023 }

00094 {
00095   register int i, j, k;
00096   register int mid = (left+right) / 2;
00097 
00098   if (left == right) return;
00099 
00100   if ( (mid-left) < MSTHRESHOLD ) 
00101   {
00102     SelectionSort( &array[left], mid-left);
00103   } 
00104   else 
00105   {
00106     MergeSort( array, temp, left, mid );   // MergeSort first half
00107   }
00108 
00109   if ( (right-mid-1) < MSTHRESHOLD ) 
00110   {
00111     SelectionSort( &array[mid+1], right-mid-1 );
00112   } 
00113   else 
00114   {
00115     MergeSort(array, temp, mid+1, right);  // MergeSort second half
00116   }
00117 
00118   // Do the merge operation.  First, copy 2 halves to temp.
00119 
00120   for( i = mid; i >= left; i--) 
00121   {
00122     temp[i] = array[i];
00123   }
00124 
00125   for( j = 1; j <= right-mid; j++) 
00126   {
00127     temp[ right - j + 1 ] = array[ j + mid ];
00128   }
00129 
00130   // Merge sublists back to array
00131   for( i = left, j = right, k = left; k <= right; k++) 
00132   {
00133      if ( temp[ i ] < temp[ j ] ) 
00134      {
00135        array[ k ] = temp[ i++ ];
00136      } 
00137      else 
00138      {
00139        array[ k ] = temp[ j-- ];
00140      }
00141   } 
00142 }

00083 {
00084   Elem* temp = new Elem[ Size ];
00085   MergeSort(array, temp, 0, Size-1);
00086 
00087   if ( temp != NULL ) 
00088   {
00089        delete[] temp;
00090   }
00091 }

00157 {
00158   // Count[i] stores number of records in bin[i]
00159 
00160   Elem* count = new Elem[ Size ];
00161   Elem* A     = array;
00162   Elem* B     = new Elem[ Size ];
00163 
00164   register long n    = Size;
00165   register int  k    = 16 / BITS;
00166   register int  r    = POW2[ BITS ];
00167 
00168   register int  i    = 0;
00169   register int  j    = 0;
00170   register int  rtok = 1;
00171 
00172   for( i = 0, rtok = 1; i < k; i++, rtok *= r)    // For k digits
00173   {
00174     for( j = 0; j < r; j++)                       // Initialize count
00175     {
00176        count[ j ] = 0;
00177     }
00178 
00179     // Count the number of records for each bin on this pass
00180     for( j = 0; j < n; j++ ) 
00181     {
00182        count[ ( A[j] / rtok ) % r ]++;
00183     }
00184 
00185     // Index B: count[j] will be index for last slot of bin j.
00186     for( j = 1; j < r; j++ ) 
00187     {
00188        count[ j ] = count[ j - 1 ] + count[ j ];
00189     }
00190 
00191     // Put records into bins working from bottom of each bin.
00192     // Since bins fill from bottom, j counts downwards
00193     for( j = n-1; j >= 0; j-- ) 
00194      {
00195        B[ --count[ ( A[j] / rtok ) % r ] ] = A[j];
00196     }
00197 
00198     for( j = 0; j < n; j++ )    // Copy B back to A
00199     {
00200        A[ j ] = B[ j ];         
00201     }
00202   }
00203 
00204   if ( B != NULL ) 
00205   {
00206       delete[] B;
00207   }
00208 
00209   if ( count != NULL ) 
00210   {
00211       delete[] count;
00212   }
00213 }

00041 {
00042   n--;  // n-1 optimization
00043 
00044   // Select i'th record
00045   for( register int i = 0; i < n; i++ ) 
00046   {
00047     register int lowindex = i;           // Remember its index
00048     for(int j = n; j > i; j--)          // Find the least value
00049       if ( array[j] < array[lowindex] )
00050       {
00051          lowindex = j;                   // Put it in place
00052       }
00053 
00054     swap( array, i, lowindex );
00055   }
00056 }

00072 {
00073   for(   register int i = n / 2; i > 2; i /= 2 )   // For each increment
00074     for( register int j = 0;     j < i; j++ )      // Sort each sublist
00075     {
00076       InsertionSort( &array[j], n-j, i);
00077     }
00078 
00079   InsertionSort( array, n );
00080 }

Defines
#define	MSTHRESHOLD 0
Functions
void	InsertionSort (Elem *array, int n)
void	BubbleSort (Elem *array, int n)
void	SelectionSort (Elem *array, int n)
void	InsertionSort (Elem *array, int n, int incr)
void	ShellSort (Elem *array, int n)
void	MergeSort (Elem *array, int Size)
void	MergeSort (Elem array, Elem temp, int left, int right)
void	HeapSort (Elem *array, int Size)
void	RadixSort (Elem *array, long Size)

C:/temp/src/j2k/DataType/Sort/Sort.cpp File Reference

Defines

Functions

Define Documentation

Function Documentation