Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


#ActualAlundra

Posted 23 April 2013 - 08:36 PM

Hi,

QuickSort is a sort algorithm who is used a lot.

I use a callback to compare both data :

Int32 (*Compare) ( const T&, const T& )

The complete function is :

QuickSort( const std::size_t First, const std::size_t Last, Int32 (*Compare) ( const T&, const T& ) )
{
  // Check for valid parameters.
  if( ( First >= Last ) || ( m_nData <= 1 ) )
    return;
  
  // Initialize position.
  std::size_t t = First;
  std::size_t p = First;
  std::size_t q = Last;
  
  // Partition.
  while( true )
  {
    while( Compare( m_Data[ p ], m_Data[ t ] ) > 0 )
      ++p;
    
    while( Compare( m_Data[ q ], m_Data[ t ] ) < 0 )
      --q;
    
    if( p > q )
      break;
    
    if( p < q )
    {
      const T Temp = m_Data[ p ];
      m_Data[ p ] = m_Data[ q ];
      m_Data[ q ] = Temp;
      
      if( p == t )
        t = q;
      
      if( q == t )
        t = p;
    }
    
    ++p;
    --q;
  }
  
  // Recursion.
  QuickSort( First, q, Compare );
  QuickSort( p, Last, Compare );
}

An exemple of compare callback is :

Int32 ArrayCompare( const UInt32& a, const UInt32& b )
{
  return a < b ? 1 : a > b ? -1 : 0;
}

Using this callback the array is ascending.

 

I have two questions :

- Is it possible to have better performances ? How ?

- Is it possible to have a compare callback who works by boolean ? How ?

  the compare callback by boolean should be :

bool (*Compare) ( const T&, const T& )

 

Thanks


#6Alundra

Posted 23 April 2013 - 08:34 PM

Hi,

QuickSort is a sort algorithm who is used a lot.

I use a callback to compare both data :

Int32 (*Compare) ( const T&, const T& )

The complete function is :

QuickSort( const std::size_t First, const std::size_t Last, Int32 (*Compare) ( const T&, const T& ) )
{
  // Check for valid parameters.
  if( ( First >= Last ) || ( m_nData <= 1 ) )
    return;
  
  // Initialize position.
  std::size_t t = First;
  std::size_t p = First;
  std::size_t q = Last;
  
  // Partition.
  while( true )
  {
    while( Compare( m_Data[ p ], m_Data[ t ] ) < 0 )
      ++p;
    
    while( Compare( m_Data[ q ], m_Data[ t ] ) > 0 )
      --q;
    
    if( p > q )
      break;
    
    if( p < q )
    {
      const T Temp = m_Data[ p ];
      m_Data[ p ] = m_Data[ q ];
      m_Data[ q ] = Temp;
      
      if( p == t )
        t = q;
      
      if( q == t )
        t = p;
    }
    
    ++p;
    --q;
  }
  
  // Recursion.
  QuickSort( First, q, Compare );
  QuickSort( p, Last, Compare );
}

An exemple of compare callback is :

Int32 ArrayCompare( const UInt32& a, const UInt32& b )
{
  return a < b ? -1 : a > b ? 1 : 0;
}

Using this callback the array is ascending.

 

I have two questions :

- Is it possible to have better performances ? How ?

- Is it possible to have a compare callback who works by boolean ? How ?

  the compare callback by boolean should be :

bool (*Compare) ( const T&, const T& )

 

Thanks


#5Alundra

Posted 23 April 2013 - 08:33 PM

Hi,

QuickSort is a sort algorithm who is a lot used.

I use a callback to compare both data :

Int32 (*Compare) ( const T&, const T& )

The complete function is :

QuickSort( const std::size_t First, const std::size_t Last, Int32 (*Compare) ( const T&, const T& ) )
{
  // Check for valid parameters.
  if( ( First >= Last ) || ( m_nData <= 1 ) )
    return;
  
  // Initialize position.
  std::size_t t = First;
  std::size_t p = First;
  std::size_t q = Last;
  
  // Partition.
  while( true )
  {
    while( Compare( m_Data[ p ], m_Data[ t ] ) < 0 )
      ++p;
    
    while( Compare( m_Data[ q ], m_Data[ t ] ) > 0 )
      --q;
    
    if( p > q )
      break;
    
    if( p < q )
    {
      const T Temp = m_Data[ p ];
      m_Data[ p ] = m_Data[ q ];
      m_Data[ q ] = Temp;
      
      if( p == t )
        t = q;
      
      if( q == t )
        t = p;
    }
    
    ++p;
    --q;
  }
  
  // Recursion.
  QuickSort( First, q, Compare );
  QuickSort( p, Last, Compare );
}

An exemple of compare callback is :

Int32 ArrayCompare( const UInt32& a, const UInt32& b )
{
  return a < b ? -1 : a > b ? 1 : 0;
}

Using this callback the array is ascending.

 

I have two questions :

- Is it possible to have better performances ? How ?

- Is it possible to have a compare callback who works by boolean ? How ?

  the compare callback by boolean should be :

bool (*Compare) ( const T&, const T& )

 

Thanks


#4Alundra

Posted 23 April 2013 - 08:31 PM

Hi,

QuickSort is a sort algorithm who is a lot used.

I use a callback to compare both data :

Int32 (*Compare) ( const T&, const T& )

The complete function is :

QuickSort( const std::size_t First, const std::size_t Last, Int32 (*Compare) ( const T&, const T& ) )
{
  // Check for valid parameters.
  if( ( First >= Last ) || ( m_nData <= 1 ) )
    return;
  
  // Initialize position.
  std::size_t t = First;
  std::size_t p = First;
  std::size_t q = Last;
  
  // Partition.
  while( true )
  {
    while( Compare( m_Data[ p ], m_Data[ t ] ) < 0 )
      ++p;
    
    while( Compare( m_Data[ q ], m_Data[ t ] ) > 0 )
      --q;
    
    if( p > q )
      break;
    
    if( p < q )
    {
      const T Temp = m_Data[ p ];
      m_Data[ p ] = m_Data[ q ];
      m_Data[ q ] = Temp;
      
      if( p == t )
        t = q;
      
      if( q == t )
        t = p;
    }
    
    ++p;
    --q;
  }
  
  // Recursion.
  QuickSort( First, q, Compare );
  QuickSort( p, Last, Compare );
}

An exemple of compare callback is :

Int32 ArrayCompare( const UInt32& a, const UInt32& b )
{
  return a < b ? -1 : a > b ? 1 : 0;
}

Using this callback the array is ascending.

 

I have two questions :

- Is it possible to have better performances ? How ?

- Is it possible to have a compare callback who works by boolean ? How ?

  the compare callback by boolean should be :

bool (*Compare) ( const T&, const T& )

Thanks


#3Alundra

Posted 23 April 2013 - 08:31 PM

Hi,

QuickSort is a sort algorithm who is a lot used.

I use a callback to compare both data :

Int32 (*Compare) ( const T&, const T& )

The complete function is :

QuickSort( const std::size_t First, const std::size_t Last, Int32 (*Compare) ( const T&, const T& ) )
{
  // Check for valid parameters.
  if( ( First >= Last ) || ( m_nData <= 1 ) )
    return;
  
  // Initialize position.
  std::size_t t = First;
  std::size_t p = First;
  std::size_t q = Last;
  
  // Partition.
  while( true )
  {
    while( Compare( m_Data[ p ], m_Data[ t ] ) < 0 )
      ++p;
    
    while( Compare( m_Data[ q ], m_Data[ t ] ) > 0 )
      --q;
    
    if( p > q )
      break;
    
    if( p < q )
    {
      const T Temp = m_Data[ p ];
      m_Data[ p ] = m_Data[ q ];
      m_Data[ q ] = Temp;
      
      if( p == t )
        t = q;
      
      if( q == t )
        t = p;
    }
    
    ++p;
    --q;
  }
  
  // Recursion.
  QuickSort( First, q, Compare );
  QuickSort( p, Last, Compare );
}

An exemple of compare callback is :

Int32 ArrayCompare( const UInt32& a, const UInt32& b )
{
  return a < b ? -1 : a > b ? 1 : 0;
}

Using this callback the array is ascending.

 

I have two questions :

- Is it possible to have better performances ? How ?

- Is it possible to have a compare callback who works by boolean ? How ?

  the compare callback by boolean should be :

 

bool (*Compare) ( const T&, const T& )

Thanks


#2Alundra

Posted 23 April 2013 - 08:30 PM

Hi,

QuickSort is a sort algorithm who is a lot used.

I use a callback to compare both data :

 

Int32 (*Compare) ( const T&, const T& )

The complete function is :

 

QuickSort( const std::size_t First, const std::size_t Last, Int32 (*Compare) ( const T&, const T& ) )
{
  // Check for valid parameters.
  if( ( First >= Last ) || ( m_nData <= 1 ) )
    return;
  
  // Initialize position.
  std::size_t t = First;
  std::size_t p = First;
  std::size_t q = Last;
  
  // Partition.
  while( true )
  {
    while( Compare( m_Data[ p ], m_Data[ t ] ) < 0 )
      ++p;
    
    while( Compare( m_Data[ q ], m_Data[ t ] ) > 0 )
      --q;
    
    if( p > q )
      break;
    
    if( p < q )
    {
      const T Temp = m_Data[ p ];
      m_Data[ p ] = m_Data[ q ];
      m_Data[ q ] = Temp;
      
      if( p == t )
        t = q;
      
      if( q == t )
        t = p;
    }
    
    ++p;
    --q;
  }
  
  // Recursion.
  QuickSort( First, q, Compare );
  QuickSort( p, Last, Compare );
}

An exemple of compare callback is :

 

Int32 ArrayCompare( const UInt32& a, const UInt32& b )
{
  return a < b ? -1 : a > b ? 1 : 0;
}

Using this callback the array is ascending.

 

I have two questions :

- Is it possible to have better performances ? How ?

- Is it possible to have a compare callback who works by boolean ? How ?

  the compare callback by boolean should be :

 

bool (*Compare) ( const T&, const T& )

Thanks


PARTNERS