Combsort algorithme de tri simple rapide non-recursif

Soyez le premier à donner votre avis sur cette source.

Vue 6 868 fois - Téléchargée 208 fois

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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
76
Date d'inscription
lundi 21 mars 2005
Statut
Membre
Dernière intervention
29 novembre 2009

c'est écrit "peux rivaliser" ca ne veut pas dire de maniere égal. Je crois que tu te prends la tête pour rien, et frenchement il serait bon de prendre un peu de recul pour t'en appercevoir. Je ne sais pas si tu remarques, il n'y a que toi qui s'enflamme, alors que tout le monde est cool... après c'est toi qui voit, mais je pense que tu sais te remettre en question quand il le faut. voila, sujet clos parceque je sais que ca va dégéner et polluer pour rien.
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
20
Vous réfléchissez 2 mn sur ce que vous dites ?

On est en présence d'une source, non compilée ni compilable et donc pas d'exemple d'utilisation, qui affirme fournir un algo aussi performant que quicksort.

Si sur un site C/C++ on appelle "réaction d'ado" remettre les choses en place avec cette fois un exemple pour vérifier, c'est qu'on n'a pas les mêmes mots pour les mêmes définitions.
Quand je ne réagirai plus en "ado" en pareil cas, c'est qu'il sera temps de prendre ma retraite.
Messages postés
76
Date d'inscription
lundi 21 mars 2005
Statut
Membre
Dernière intervention
29 novembre 2009

je confirme, brunews tu as eu la réaction d'un ado. Surtout pour faire ton propre source juste pour s'amuser à demontrer celui-ci. Mais après je dis cela sans agression ni mort d'homme. Faut calmer cette agressivité...
Messages postés
229
Date d'inscription
dimanche 14 septembre 2003
Statut
Membre
Dernière intervention
20 août 2014

bah laisses tomber, si tu ne sais pas accepter les critiques te signalant les erreurs répétées dans ton code tant pis, c'est sympa pour la lisibilité en tout cas d'avoir 2 variables t dans une macro, surtout si tu t'adresses à des débutants
Messages postés
32
Date d'inscription
vendredi 26 mai 2006
Statut
Membre
Dernière intervention
14 avril 2009

SHERNON66:
la question n'es pas de remplacer d par t ou outre chose , c'est la vitesse d'exécution de l'algorithme , et pour ton grand plaisir tu peux enlever la fonction générique ainsi que toutes ses macros et tester que CombSort(int *tab,size_t NBElem);
Le code compile est tant-mieux.
A+.
Afficher les 15 commentaires

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.