
// chapitre 2 partition.cpp : définit le point d'entrée pour l'application console.
//

#include "stdafx.h"

// pour simplifier l'écriture, définition d'alias de type
typedef void (*pf_echange)(void*,int,int);
typedef int (*pf_comp)(void*,int,int);

// deux fonctions respectant ces signatures
void int_echange(void*t,int p1,int p2)
{
	int*T=(int*)t;
	int aux=T[p1];
	T[p1]=T[p2];
	T[p2]=aux;
}

int int_compare(void*t,int p1,int p2)
{
	int v1,v2;
	int*T=(int*)t;
	v1=(int) T[p1];
	v2=(int) T[p2];
	
	return v1-v2;
}

// l'algorithme devenu général
int partition(void* T,int m,int d,pf_echange fswap,pf_comp fcomp)
{	
	// valeur pivot, variable d'échange
	int pv;		
	int m1=m,d1=d;
	// initialisation
	pv=m+(d-m)/2;	// position du pivot
			
	// tant que les index ne se croisent pas
	while(m<d)
	{
		// rechercher une valeur inférieure à droite
		while(m<d && (*fcomp)(T,d,pv)>0)
			 d--;
					 
		// rechercher une valeur supérieure à gauche
		while(m<d && (*fcomp)(T,m,pv)<0)			
			m++;
		
		if(m>=d)
			break;
			
		if((*fcomp)(T,m,d)!=0)
		{	// échange													
			(*fswap)(T,m,d);
		} 
		 else
			d--;	 	
	}		
		
	return m;
}

void tri_aux(int* T,int m,int d,pf_echange fswap,pf_comp fcomp)
{						
	if(m>=d)
		return;			// rien à trier
			
	int k=partition(T,m,d,fswap,fcomp); // partitionne entre m et d
	tri_aux(T,m,k-1,fswap,fcomp);		// tri à gauche
	tri_aux(T,k+1,d,fswap,fcomp);		// tri à droite
}
	
void tri(int* T,int length,pf_echange fswap,pf_comp fcomp)
{
	tri_aux(T,0,length-1,fswap,fcomp);	
}
	
void afficher(int T[],int m,int d)
{
	// affichage du tableau à chaque étape
	for(int i=m; i<=d; i++)
			printf("%d,",T[i]);	
	printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	int tab[]={ 5,1,7,2,8,4,9,13};
	tri(tab,8,&int_echange,&int_compare);
	afficher(tab,0,7);
	return 0;
}

