sort.cpp

来自「计算机人工智能方面的决策树方法 c4.5」· C++ 代码 · 共 72 行

/*************************************************************************/
/*                                                                       */
/*      Sorting utilities                                                */
/*      -----------------                                                */
/*                                                                       */
/*************************************************************************/


#include "defns.h"
#include "c45types.h"
#include "extern.h"



/*************************************************************************/
/*                                                                       */
/*      Sort items from Fp to Lp on attribute a                          */
/*                                                                       */
/*************************************************************************/


void    Quicksort(ItemNo Fp, ItemNo Lp, Attribute Att, void (*Exchange)(int,int))
/*  ---------  */
{
    register ItemNo Lower, Middle;
    register double Thresh;
    register ItemNo i;

    if ( Fp < Lp )
    {
	Thresh = CVal(Item[Lp], Att);

	/*  Isolate all items with values <= threshold  */

	Middle = Fp;

	for ( i = Fp ; i < Lp ; i++ )
	{ 
	    if ( CVal(Item[i], Att) <= Thresh )
	    { 
		if ( i != Middle ) (*Exchange)(Middle, i);
		Middle++; 
	    } 
	} 

	/*  Extract all values equal to the threshold  */

	Lower = Middle - 1;

	for ( i = Lower ; i >= Fp ; i-- )
	{
	    if ( CVal(Item[i], Att) == Thresh )
	    { 
		if ( i != Lower ) (*Exchange)(Lower, i);
		Lower--;
	    } 
	} 

	/*  Sort the lower values  */

	Quicksort(Fp, Lower, Att, Exchange);

	/*  Position the middle element  */

	(*Exchange)(Middle, Lp);

	/*  Sort the higher values  */

	Quicksort(Middle+1, Lp, Att, Exchange);
    }
}