Combsort algorithme de tri simple rapide non-recursif

Télécharger le projet
Commenter

Description

C'est un algorithme de tri simple a coder non récursif et "peut" rivaliser avec les algo complexe a la quicksort.
il est dérive du fameux algorithme merdique le bubblesort (Tri a Bulles),l'idée de base est de élargir le pas 'gap' au lieu de comparer les éléments un a un ( i et i+1 ) , on utilise un shrink factor(1.3) pour calculer le pas jusqu'à ce qu'il soit réduit a 1 et en retourne en mode bubblesort.
voici le résultat obtenu en comparant les algos de tri sur une liste de 10000 nombre aléatore ( d'apres BYTE MAGAZINE)

Algo Vitesse (secondes)
=============================
QSort 0.0038
CombSort 0.0042
BubbleSort 1.36

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.

Source / Exemple : 


/**


  •  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;
}

Conclusion :


RÉFÉRENCE
http://www.nist.gov/dads/HTML/combSort.html
http://www.tscc.de/combsort.html
et les WIKIPEDIA of course

Voila A Vos LeS StuDios.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (xtremejames183)