Search  

---

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

#include "Const.hpp"
#include "MaxHeap.hpp"

Go to the source code of this file.

Compounds
struct	QEntry
Defines
#define	__J2K__Sort_HPP__
#define	BITS   6
Functions
void	InsertionSort (Elem *array, int n)
void	BubbleSort (Elem *array, int n)
void	SelectionSort (Elem *array, int n)
void	ShellSort (Elem *array, int n)
void	InsertionSort (Elem *array, int n, int incr)
void	MergeSort (Elem *array, int Size)
void	HeapSort (Elem *array, int Size)
void	RadixSort (Elem *array, long Size)
void	QuickSort (Elem *array, int Size)
void	BrightQSort (Elem *array, ulong Size)
void	OldQuickSort (Elem *array, ulong Size)
void	MergeSort (Elem *array, Elem *temp, int left, int right)
void	swap (Elem *A, int i, int j)
Variables
long	POW2 [17]

---

Define Documentation

#define BITS   6

Definition at line 16 of file Sort.hpp.

#define __J2K__Sort_HPP__

Definition at line 6 of file Sort.hpp.

---

Function Documentation

void BrightQSort (  Elem *    array, ulong    Size )

Definition at line 99 of file OldQsort.cpp. { ULONG* ptr = new ULONG[20]; int l = 0; int r = 0; register int i = 0; ULONG k = 0; int Trigger; Elem T; int Test = 20; int Test34 = Test * 3 / 4; // 75% Ratio to be declare sorted int n = Size / Test; int n2 = (int)floor(n / 2); for( i = 1; i <= Test; i++ ) { ptr[i] = (ulong)floor( n * i ); } for( i = 2; i <= Test; i++ ) { T = array[ ptr[i] ] - array[ ptr[i - 1] - n2 ]; if ( T < 0 ) { l++; } else { r++; } printf( "[%d, %d, %d]", T, l, r ); } printf( "[%d, %d, %d]", T, l, r ); Trigger = r - l; printf( "%d", Trigger ); if ( Trigger > Test34 ) { printf( "INC" ); InsertionSort( array, Size ); return; } if ( Trigger < (-1 * Test34) ) { printf("DEC"); // Reverse the array for( k = 1; k <= ( Size / 2 + 1 ); k++ ) { swap( array, k, Size - k + 1 ); } for( k = 1; k <= Size; k++ ) { printf("%d", array[k] ); } InsertionSort( array, Size ); return; } printf( "RND" ); OldQuickSort( array, Size ); } // End of BrightQSort()

void BubbleSort (  Elem *    array, int    n )

Definition at line 26 of file Sort.cpp. { n--; // n-1 optimization // Bubble up i'th record for( register int i = 0; i < n; i++ ) for( register int j = n; j > i; j-- ) if ( array[j] < array[j-1] ) { swap( array, j, j-1 ); } }

void HeapSort (  Elem *    array, int    Size )

Definition at line 144 of file Sort.cpp. { MaxHeap* heap = new MaxHeap( array, Size, Size ); // Build the maxheap for(int i = 0; i < Size; i++) // Now sort by removing { heap->removemax(); // The max value placed at end of heap } delete heap; }

void InsertionSort (  Elem *    array, int    n, int    incr )

Definition at line 59 of file Sort.cpp. Referenced by BrightQSort(), QuickSort(), and ShellSort(). { for( register int i = incr; i < n; i += incr ) for( register int j = i; ( j >= incr ) && ( array[j] < array[j-incr] ); j -= incr ) { swap( array, j, j-incr ); } }

void InsertionSort (  Elem *    array, int    n )

void MergeSort (  Elem *    array, Elem *    temp, int    left, int    right )

Definition at line 93 of file Sort.cpp. Referenced by MergeSort(). { register int i, j, k; register int mid = (left+right) / 2; if (left == right) return; if ( (mid-left) < MSTHRESHOLD ) { SelectionSort( &array[left], mid-left); } else { MergeSort( array, temp, left, mid ); // MergeSort first half } if ( (right-mid-1) < MSTHRESHOLD ) { SelectionSort( &array[mid+1], right-mid-1 ); } else { MergeSort(array, temp, mid+1, right); // MergeSort second half } // Do the merge operation. First, copy 2 halves to temp. for( i = mid; i >= left; i--) { temp[i] = array[i]; } for( j = 1; j <= right-mid; j++) { temp[ right - j + 1 ] = array[ j + mid ]; } // Merge sublists back to array for( i = left, j = right, k = left; k <= right; k++) { if ( temp[ i ] < temp[ j ] ) { array[ k ] = temp[ i++ ]; } else { array[ k ] = temp[ j-- ]; } } }

void MergeSort (  Elem *    array, int    Size )

void OldQuickSort (  Elem *    array, ulong    Size )

Definition at line 16 of file OldQsort.cpp. Referenced by BrightQSort(). { struct QEntry QStack[100]; // Use to store variables for recursivity long Top = 0; // Top & Bottom ptr long Bottom = 0; long a = 0; // Inner Left & Right working ptr long b = Size-1; Elem z; // Temp location for swapping stuff QStack[0].Left = a; // Define the absolute left ptr QStack[0].Right = b; // Define the absolute right ptr long x = 1; // Normal Middle ptr while ( x > 0 ) { x--; a = QStack[x].Left; // Store Left and Right Stack value b = QStack[x].Right; z = array[a]; // Give me some z value Top = a; // Fix Top and Bottom range Bottom = b + 1; QSBottom: // Address #1 -- Let's play with Bottom ! Bottom--; if ( Bottom == Top ) goto QSz; // If there is no middle than fix z if ( z <= array[Bottom] ) // If z is smaller than bottom-- and retry { goto QSBottom; } else { array[Top] = array[Bottom]; } QSTop: // Address #2 -- Let's play with Top ! Top++; if ( Bottom == Top) goto QSz; // If there is no middle than fix z if ( z >= array[ Top ] ) // If z is bigger than top++ and retry { goto QSTop; } else { array[ Bottom ] = array[ Top ]; goto QSBottom; } QSz: // Address #3 -- Let's fix z and continue. array[Top] = z; if ( (b - Top) >= 2 ) { QStack[x].Left = Top + 1; QStack[x].Right = b; x++; } if ( (Bottom - a) >= 2 ) { QStack[x].Left = a; QStack[x].Right = Bottom - 1; x++; } } }

void QuickSort (  Elem *    array, int    Size )

Definition at line 11 of file Qsort4.cpp. { int i = 0; int j = Size - 1; int listsize = Size; struct QEntry Stack[100]; int top = 0; int pivot; int pivotindex, l, r; Stack[top].Left = i; Stack[top].Right = j; while ( top >= 0 ) { // Pop Stack i = Stack[top].Left; j = Stack[top--].Right; // Findpivot pivotindex = (i+j)/2; pivot = array[pivotindex]; swap( array, pivotindex, j ); // Stick pivot at end // Partition l = i-1; r = j; do { while ( array[++l] < pivot ); while (r && array[--r] > pivot ); swap(array, l, r); } while (l < r); swap(array, l, r); // Undo final swap swap(array, l, j); // Put pivot value in place // Load up Stack if ( (l-i) > QSTHRESHOLD ) // Left partition { Stack[++top].Left = i; Stack[ top].Right = l-1; } if ( (j-l) > QSTHRESHOLD ) // Right partition { Stack[++top].Left = l+1; Stack[ top].Right = j; } } InsertionSort( array, listsize ); // Final Insertion Sort }

void RadixSort (  Elem *    array, long    Size )

Definition at line 156 of file Sort.cpp. { // Count[i] stores number of records in bin[i] Elem* count = new Elem[ Size ]; Elem* A = array; Elem* B = new Elem[ Size ]; register long n = Size; register int k = 16 / BITS; register int r = POW2[ BITS ]; register int i = 0; register int j = 0; register int rtok = 1; for( i = 0, rtok = 1; i < k; i++, rtok *= r) // For k digits { for( j = 0; j < r; j++) // Initialize count { count[ j ] = 0; } // Count the number of records for each bin on this pass for( j = 0; j < n; j++ ) { count[ ( A[j] / rtok ) % r ]++; } // Index B: count[j] will be index for last slot of bin j. for( j = 1; j < r; j++ ) { count[ j ] = count[ j - 1 ] + count[ j ]; } // Put records into bins working from bottom of each bin. // Since bins fill from bottom, j counts downwards for( j = n-1; j >= 0; j-- ) { B[ --count[ ( A[j] / rtok ) % r ] ] = A[j]; } for( j = 0; j < n; j++ ) // Copy B back to A { A[ j ] = B[ j ]; } } if ( B != NULL ) { delete[] B; } if ( count != NULL ) { delete[] count; } }

void SelectionSort (  Elem *    array, int    n )

Definition at line 40 of file Sort.cpp. Referenced by MergeSort(). { n--; // n-1 optimization // Select i'th record for( register int i = 0; i < n; i++ ) { register int lowindex = i; // Remember its index for(int j = n; j > i; j--) // Find the least value if ( array[j] < array[lowindex] ) { lowindex = j; // Put it in place } swap( array, i, lowindex ); } }

void ShellSort (  Elem *    array, int    n )

Definition at line 71 of file Sort.cpp. { for( register int i = n / 2; i > 2; i /= 2 ) // For each increment for( register int j = 0; j < i; j++ ) // Sort each sublist { InsertionSort( &array[j], n-j, i); } InsertionSort( array, n ); }

void swap (  Elem *    A, int    i, int    j )  [inline]

Definition at line 40 of file Sort.hpp. Referenced by BrightQSort(), BubbleSort(), InsertionSort(), smatrix::PivotMap(), QuickSort(), SelectionSort(), smatrix::Transpose(), MaxHeap::insert(), MaxHeap::remove(), MaxHeap::removemax(), and MaxHeap::siftdown(). { Elem temp = A[i]; A[i] = A[j]; A[j] = temp; }

---

Variable Documentation

long POW2[17] [static]

Initial value: { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536 } Definition at line 11 of file Sort.hpp.

---