begin process at 2010 03 21 11:38:39
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths et Algorithmes

 > A QUOI RESSEMBLE UN TRI ENCORE?

A QUOI RESSEMBLE UN TRI ENCORE?


 Information sur la source

Note :
Aucune note
Catégorie :Maths et Algorithmes Niveau :Débutant Date de création :19/02/2004 Vu / téléchargé :3 671 / 111

Auteur : tds

Ecrire un message privé
Commentaire sur cette source (2)
Ajouter un commentaire et/ou une note

 Description

Voici donc le corps d'un algorithme de tri. Ce dernier est plus rapide lors de tris sur de petits tableaux, il vaut celui de java sur les autres tailles (Medium, java légèrement meilleur:: huge,mon tri légèrement meilleur)
Voilou, amusez-vous bien
B@ron

Source

  • package ShellSort;
  • import java.util.Arrays;
  • public class deSanyFromBelgiumSort
  • {
  • private int[] local; //copy of the array.
  • private int increment = 1; //jump in the array.
  • private int size; //size of the array.
  • private int c,j; //useful for the trt
  • private int cpt,cpt2; //the counters.
  • public deSanyFromBelgiumSort(){}
  • //JAVA SORT
  • public int[] javaSort(int[] tmp){
  • local = tmp;
  • Arrays.sort(local);
  • return local;
  • }
  • //MY SORT
  • // => MYSORT IS FASTER WITH SMALL ARRAYS.
  • // => JAVASORT IS BETTER WITH MEDIUM ARRAYS.
  • // => EQUIVALENT WITH HUGE ARRAYS.
  • public int[] mySort(int[] tmp){
  • local = tmp;
  • size = tmp.length;
  • while(increment < (size/9)) increment = (increment * 3) + 1; //FIRST LOOP TO DETERMINE THE JUMP SIZE
  • do{
  • for (cpt = 1; cpt <= increment; cpt ++){
  • for (cpt2 = increment+cpt; cpt2 < size; cpt2+=increment){
  • c = local[cpt2];
  • j = cpt2 - increment;
  • while ((j >= 0) && (local[j] > c)){
  • local[j+increment] = local[j];
  • j -= increment;
  • }
  • local[j+increment] = c;
  • }//FOR 2
  • }//FOR 1
  • increment /= 3;
  • }while(increment != 0);
  • return local;
  • }
  • }
package ShellSort;

import java.util.Arrays;

public class deSanyFromBelgiumSort 
{
  private int[] local;            //copy of the array.
  private int increment = 1;      //jump in the array.
  private int size;               //size of the array.
  private int c,j;                //useful for the trt
  private int cpt,cpt2;           //the counters.

  public deSanyFromBelgiumSort(){}
  
  //JAVA SORT
  public int[] javaSort(int[] tmp){    
    local = tmp;
    Arrays.sort(local);
    return local;
  }
  
  //MY SORT
  // => MYSORT    IS FASTER WITH SMALL ARRAYS.
  // => JAVASORT  IS BETTER WITH MEDIUM ARRAYS.
  // => EQUIVALENT          WITH HUGE ARRAYS.
  public int[] mySort(int[] tmp){            
    local = tmp;
    size = tmp.length;
    
    while(increment < (size/9)) increment = (increment * 3) + 1;  //FIRST LOOP TO DETERMINE THE JUMP SIZE
    
    
    do{
      for (cpt = 1; cpt <= increment; cpt ++){          
        for (cpt2 = increment+cpt; cpt2 < size; cpt2+=increment){                    
          c = local[cpt2];
          j = cpt2 - increment;
          while ((j >= 0) && (local[j] > c)){
            local[j+increment] = local[j];
            j -= increment;
          }
          local[j+increment] = c;
        }//FOR 2        
      }//FOR 1
      increment /= 3; 
    }while(increment != 0);        
    return local;
  }
}

 Conclusion

Java je trouve qu'il n'y a pas grand chose de mieux, cependant cela serait triste de ne plus réfléchir à cause des nombreux programmes d'aides et méthodes qui sont mis à notre disposition. Voici donc un tri qui vaut celui de java mais qui est tjs plus rapide avec les petits tris ;p

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Sources du même auteur

Source avec Zip Source avec une capture IA PREVIEW-PRINTER
Source avec Zip Source avec une capture PRINT PREVIEW
Source avec Zip Source avec une capture UTILISER SAX POUR LIRE DU XML
Source avec Zip RECONNAISSANCE VOCALE DANS VOS MENUS
Source avec Zip MAIL COMPOSE (WITH .DOC, .HTML)

 Sources de la même categorie

TEST DE PRIMALITÉ OPTIMISÉ par Julien39
Source avec Zip CLASSE MATRICE par frankladen11
Source avec Zip Source avec une capture RÉSOLUTION D'ÉQUATION GRÂCE AU CALCUL DES DÉTERMINANTS par frankladen11
Source avec Zip TYPE DE DONNÉES ABSTRAIT GRAPHE par smutsonberg
Source avec Zip Source avec une capture SIMPLEXE ET DUAL par MrRenaud

Commentaires et avis

Commentaire de Taquilla le 19/02/2004 17:35:39

Lu tds,


J'ai fait des tests de performances entre ton tri(mySort) et celui de Java(javaSort). Voici ce que j'obtiens :

                              javaSort()         mySort()
pour t[500]                10ms               10ms
pour t[5000]              15ms               20ms
pour t[10000]            25ms               25ms
pour t[100000]          70ms               220ms


Si on considère que t[500] est un small array alors mySort() n'est pas plus rapide que javaSort().

Si on considère que t[100000] est un huge array alors javaSort() est 3 fois plus rapide que mySort().

Si on considère que t[5000] et t[10000] sont des medium array alors javaSort() et mySort() reste à peu près équivalent..


Peux-tu m'indiquer les ordres de grandeurs des small, medium et huge array pour toi?car apparemment, je ne trouve pas les mêmes performances que toi.

J'ai aussi comparé ton tri au "tri par tas". Ton tri est plus rapide à partir d'un tableau au dessus de 5000 éléments.

Cependant, les tests entre javaSort() et mySort() restent approximatifs pour les tests avec les small array. Il faudrait que je prenne une mesure plus petite que la milliseconde.


a+

Commentaire de tds le 20/02/2004 08:09:28

Bien vu ;)
Je parle de small array de 1..100 éléments. On trie souvent des tableaux d'éléments de taille inférieure à cela. C'est le but premier de mon algorithme. En effet, quand on doit trier des ensembles plus important, il s'agit alors en général de données venant de bases de données et on utilise alors un ORDER BY. Ce qui résoud bien sur le problème.
Mais tu as raison, pour les tailles moyenne et grande ne venant pas d'une DB, il vaut mieux se résoudre à utiliser java car ce dernier utilise différents algorithmes d'après ce qu'il doit trier.
SMALL 1..100                               BETTER
MEDIUM disons, 100..2500            ~EQUAL
HUGE 2500...[                              WORSE

Si des personnes, on des idées pour améliorer l'algo. Ce serait super, merci pour vos commentaires.
TDS (B@ron)

 Ajouter un commentaire




Nos sponsors


Sondage...

CalendriCode

Mars 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728
293031    

Consulter la suite du CalendriCode

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,811 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales