BitonicSort.h File Reference

#include <cstdint>
#include <vector>

Go to the source code of this file.

Enumerations
enum	sort_direction { up, down }

Functions
template<typename T >
void	BitonicMerge (sort_direction aDir, typename std::vector< T >::iterator &aDataStart, typename std::vector< T >::iterator &aDataEnd)
template<typename T >
void	BitonicSort (sort_direction aDir, typename std::vector< T >::iterator &aDataStart, typename std::vector< T >::iterator &aDataEnd)

Enumeration Type Documentation

enum sort_direction

Enumerator
up
down

Definition at line 8 of file BitonicSort.h.

{up, down};

Function Documentation

template<typename T >

void BitonicMerge	(	sort_direction	aDir,
		typename std::vector< T >::iterator &	aDataStart,
		typename std::vector< T >::iterator &	aDataEnd
	)

Definition at line 48 of file BitonicSort.h.

References std::swap(), and up.

{
  uint32_t lSize( aDataEnd - aDataStart );
  if( lSize > 1 ){
    
    uint32_t lPower2(1);
    while (lPower2<lSize) lPower2<<=1;
    
    typename std::vector<T>::iterator lMidpoint( aDataStart + (lPower2>>1) );
    typename std::vector<T>::iterator lFirst( aDataStart );
    typename std::vector<T>::iterator lSecond( lMidpoint );
    
    for( ; lSecond != aDataEnd ; ++lFirst , ++lSecond ){
      if( ( (*lFirst) > (*lSecond) ) == (aDir == up) ) {
    std::swap( *lFirst , *lSecond );
      }
    }
    
    BitonicMerge<T> ( aDir, aDataStart , lMidpoint );
    BitonicMerge<T> ( aDir, lMidpoint , aDataEnd );
  }
}

template<typename T >

void BitonicSort	(	sort_direction	aDir,
		typename std::vector< T >::iterator &	aDataStart,
		typename std::vector< T >::iterator &	aDataEnd
	)

Definition at line 26 of file BitonicSort.h.

References down, and up.

{
  uint32_t lSize( aDataEnd - aDataStart );
  if( lSize > 1 ){
    typename std::vector<T>::iterator lMidpoint( aDataStart+(lSize>>1) );
    if ( aDir == down )
      {
    BitonicSort<T> ( up, aDataStart , lMidpoint );
    BitonicSort<T> ( down, lMidpoint , aDataEnd );
      }else{
      BitonicSort<T> ( down, aDataStart , lMidpoint );
      BitonicSort<T> ( up, lMidpoint , aDataEnd );
    }
    BitonicMerge<T> (aDir, aDataStart , aDataEnd );
  }
}