COMBSORT ALGORITHME DE TRI SIMPLE RAPIDE NON-RECURSIF

/**
* Voila le commentaire d'origine en Anglais:
' Comb Sort an array of any type
'
' CombSort is faster than all but QuickSort and close to it.
' On the other hand, the code is much simpler than QuickSort
' and can be easily customized for any array type
' This definition is based on an article appeared on the Byte
' magazine in about 1985.
*/

/*
* Comme c'est écrit c'est un algorithme de tri assez rapide simple a implémenter non-récursif et ne requiert aucune
* donné externe (pile,file) pour stocker les indices. il est d'ailleurs utilisé dans le serveur Lighttpd ( mod_dir,... )
* L'idée de base est d'elargir le pas (gap) en utilisant le shrink factor qui est de formule
* GAP = GAP * 1.3
* d'apres les auteurs de l'algorithme un pas de 9 et 10 sont consideres comme mauvais c'est pour cela qu'on
* utlise un SF de 11
* REFERENCE:
* http://www.nist.gov/dads/HTML/combSort.html
* http://www.tscc.de/combsort.html
* et les WIKIPEDIA of course
*/

/*
* $SymiscID: combsort.c 0.0125 15/12/2008 15:19 Win32 MSVC9.0 $
* @auteur Mrad Chems Eddine <xtremejames183@msn.com>
*/

#include <stdio.h>
#include <stdlib.h>
#ifdef _WIN32
typedef unsigned int size_t;
#else
#include <sys/param.h>
#endif

typedef int (*ProcCmp)(const void *,const void *,size_t);

#define BYTE_SWAP(x,y,t)\
 {\
register unsigned char *s = ( unsigned char *)x;\
 register unsigned char *d = ( unsigned char *)y;\
 size_t len = t;\
 do{\
 char t = *s ; *s++ = *d ; *d++ = t;\
 }while(--len);}


void CombSort(int *t,size_t NBElem)
{
 int gap;
 for( gap = NBElem;;){
 short SWAP ; /* flag pour voir si la liste est trie */
 int i;

 /* appliquer le shrink factor */
 gap = gap * 10 / 13;
 if( gap == 9 || gap == 10 ){
 gap = 11;
 }
 if( gap < 1 ){
 gap = 1; /* bubble sort */
 }
 for(i = 0 , SWAP = 0 ; i < ( NBElem - gap) ; ++i){
 if( t[i] > t[i+gap] ){
 /* swap */
 int tmp = t[i];
 t[i] = t[i+gap];
 t[i+gap] = tmp;
 SWAP = 1 ;
 }
 }
	if( gap <= 1 && !SWAP ){
			/* la liste est déjà trie */
		break;
	}

	}
}

static int __CMP(const void *a,const void *b,size_t size)
{
	int _a = *(int *)a;
	int _b = *(int *)b;

	return _a - _b;
}

void GenericCombSort(void *base,size_t NBElem,size_t ElemSize,ProcCmp pcmp)
{
	char *start ;
	int gap;

	if( base == NULL || NBElem <= 1 || pcmp == NULL){
		return;
	}

	for(start = (char *)base,gap = NBElem;;){
		short SWAP;
		size_t i;

		gap = gap * 10 / 13;
		if( gap == 9 || gap == 10 ){
			gap = 11;
		}
		for( SWAP = 0 , i =0 ; i < ( NBElem - gap ) * ElemSize ; i+= ElemSize ){
			int p = ( gap * ElemSize ) +i;
			if( pcmp((start+i),(start+p),ElemSize) > 0 ){
				BYTE_SWAP((start+i),(start+p),ElemSize);
				SWAP = 1;
			}
		}
	if( gap <= 1 && !SWAP ){
			break;
	}
	}
}

int main()
{
 int tab[] = { 56,1,784,-42,8,24,72,-98,153,13,255,27,-17,6,9421,-842,423,61,89,37,10,261,436,175,145 };
 const size_t MAX = sizeof(tab)/sizeof(tab[0]);
 size_t i;

 /* a essayer sur tous;float,long,meme char */
 for( i = 0 ; i < MAX ; ++i )
		printf("%d ",tab[i]);

 printf("\n");

 /* t1 = clock() */
 
 //CombSort(tab,MAX);

 /*
 * tab = Tableau a trier
 * MAX = Nombre d'entre dans le tableau
 * ElemSize = taille d'un seul element dans le tableau (sizeof(tab[0])
 * __CMP =  fonction de comapraison 
 */
 GenericCombSort((void *)tab,MAX,sizeof(int),__CMP);

 /* t2 = clock() */

 puts("Tableau Trier");
  for( i = 0 ; i < MAX ; ++i )
		printf("%d ",tab[i]);

  printf("\n");
#ifdef _WIN32
	getch();
#endif
 return 0;
}