Changeset 1474 in Sophya

Timestamp:

Apr 19, 2001, 9:38:36 PM (24 years ago)

Author:

cmv

Message:

2 routines de tri bugguee enlevees cmv 19/4/2001

Location:

trunk/SophyaLib/NTools

Files:

• nbtri.c (modified) (3 diffs)
• nbtri.h (modified) (1 diff)

trunk/SophyaLib/NTools/nbtri.c

@@ -278 +278 @@
 }
 
-/*=========================================================================*/
-/*
-++
-  int_4 tri_rapide_I (int_4 *datum,int_4 *index,int_4 N)
-        algorythme de tri rapide
-        ( p114-119 THE ART OF COMPUTER PROGRAMMING, vol. 3 SORTING AND
-        SEARCHING de D.E. Knuth)
-| datum  ( entree/sortie ) -> vecteur de dimension N contenant des ENTIERS
-|        desordonnes en entree. Ces elements ressortent ordonnes.
-| index  ( sortie ) -> vecteur de dimension N contenant des entiers.
-|        Le contenu de la case i de index nous indique la place
-|        du ieme element du datum originel.
-| tri_rapide = -1 si echec, 1 si reussite de l'operation
---
-*/
-int_4 tri_rapide_I (int_4 *datum,int_4 *index,int_4 N)
-{
-/* 14 = nb max d'entrees que la pile (stack) peut contenir. Ce 14 limite la longueur 
-             maximale possible pour les vecteurs a 32 768 ( = 2**15 ) */
-
-int_4 stklo[14], stkhi[14], hi, nstak, i, limlo, limhi, lo, ikey;
-int_4 dkey;
-
-/* initialisations */
-
-for (i=0; i<=N-1 ;i++)  index[i]=i;
-
-nstak=0;
-limlo=0; limhi=N-1;
-
-grande_boucle:
-  dkey = *(datum+limlo);
-  ikey = *(index+limlo);
-
-/* compare tous les elements d'un ss-vecteur entre limlo et limhi avec la donnee-cle courante */
-
-  lo=limlo; hi=limhi;
-  
-sous_boucle_1:
-  if ( lo == hi ) goto lo_egal_hi;
-
-  if ( *(datum+hi) <= dkey ) goto remplacement_lo;
-  hi = hi - 1;
-
-/* le pointeur  hi doit pointer une donnee plus petite que la cle qui va etre remplacer */
-
-  goto sous_boucle_1;
-
-remplacement_lo:
-  *(datum+lo) = *(datum+hi);
-  *(index+lo) = *(index+hi);
-  lo = lo + 1;
-  
-sous_boucle_2:
-  if ( lo == hi ) goto lo_egal_hi;
-
-  if ( *(datum+lo) >= dkey ) goto remplacement_hi;
-
-  lo = lo + 1;
-  goto sous_boucle_2;
-
-remplacement_hi:
-  *(datum+hi) = *(datum+lo);
-  *(index+hi) = *(index+lo);
-  hi = hi - 1;
-
-/* le pointeur lo doit pointer une donnee plus grande que la cle qui va etre remplacer */
-
-  goto sous_boucle_1;
-
-lo_egal_hi:
-
-/* lo et hi sont egaux, et pointent sur une valeur qui va etre remplacer. Tant que toutes les valeurs sous ce point sont inferieures a la cle et que toutes les valeurs apres ce point sont superieures a la cle, c'est la que nous remettrons la cle dans le vecteur */
-
-  *(datum+lo) = dkey;
-  *(index+lo) = ikey;
-
-/* A ce point du ss-prog. toutes les donnees entre limlo et lo-1 inclus sont inferieurs a datum(lo), et toutes les donnes entre lo+1 et limhi sont superieures a datum(lo)  
-   Si les deux ss-tableaux ne contiennent pas plus d'un element, on prend l'intervale le plus recent de la pile ( si le stack est vide c'est fini ). Si le plus grand des deux ss-tableaux contient plus d'un element et si le plus petit contient au plus un element, alors on oublie le plus petit et on reduit l'autre. Si le plus petit ss-tableau contient au moins 2 elements, alors on place le plus grand ss-tableau dans la pile et on processe le ss-tableau.  */
-  
-  if ( (limhi-lo) > (lo-limlo) ) goto cas_1;
-
-/* cas 1 : le ss-tableau inferieur est plus long. Si il contient un element au plus, alors on prend l'intervalle du stack le plus recent, on le ramene et on travaille dessus */
-
-  if ( (lo-limlo) <= 1) goto test_fin;
-
-/* si le ss-tableau superieur ( le + court ss-tableau ) contient  un element au plus alors on processe le  ss-tableau inferieur ( le + long), mais si le ss-tableau superieur contient plus d'un element, alors on place le  ss-tableau inferieur ( le + long) sur la pile et on processe le ss-tableau superieur. */
-
-  if ( (limhi-lo) >= 2) goto cas_1b;
-
-/* cas 1a : si le ss-tableau superieur ( le + court ss-tableau ) contient  un element au plus alors on revient en arriere et on agit sur le  ss-tableau inferieur ( le + long) */
-
-  limhi=lo-1;
-  goto grande_boucle;
-
-/* cas 1b :  si le ss-tableau superieur ( le + court ss-tableau ) contient plus d'un element, alors on place le  ss-tableau inferieur ( le + long) sur la pile et on processe le ss-tableau superieur. */
-
-cas_1b:
-  nstak=nstak+1;
-  *(stklo+nstak)=limlo;
-  *(stkhi+nstak)=lo-1;
-  limlo=lo+1;
-  goto grande_boucle;
- 
-/* cas 2 : le ss-tableau superieur est plus long, si il contient  un element au plus alors on agit sur l'intervalle le plus recent de la pile. */
-
-cas_1:
-  if ( (limhi-lo) <= 1) goto test_fin;
-
-/* si le ss-tableau inferieur ( le + court ss-tableau ) contient  un element au plus alors on processe le  ss-tableau superieur ( le + long), mais si le ss-tableau inferieur contient plus d'un element, alors on place le  ss-tableau superieur ( le + long) sur la pile et on processe le ss-tableau inferieur. */
-
-   if ( (lo-limlo) >= 2) goto cas_2b;
-
-/*  cas 2a : si le ss-tableau inferieur ( le + court ss-tableau ) contient  un element au plus alors on revient en arriere et on agit sur le  ss-tableau superieur ( le + long) */
-
-  limlo=lo+1;
-  goto grande_boucle;
-  
-/* cas 2b :  si le ss-tableau inferieur ( le + court ss-tableau ) contient plus d'un element, alors on place le  ss-tableau superieur ( le + long) sur la pile et on processe le ss-tableau inferieur. */
-
-cas_2b:
-  nstak=nstak+1;
-  *(stklo+nstak)=lo+1;
-  *(stkhi+nstak)=limhi;
-  limlo=lo-1;
-  goto grande_boucle;
-   
-/* on prend l'intervalle le plus recent de la pile. Si le stack est vide, c'est fini !!! */
-        
-test_fin:
-  if (nstak <= 0) return (1);
-  limlo = *(stklo+nstak);
-  limhi = *(stkhi+nstak);
-  nstak=nstak-1;
-  goto grande_boucle;
-
-}
-
-/*=========================================================================*/
-/*
-++
-  int_4 tri_rapide_F (float *datum,int_4 *index,int_4 N)
-        Idem tri_rapide_I mais pour un tableau de flottants
-         REMPLI avec des ENTIERS.
---
-*/
-int_4 tri_rapide_F (float *datum,int_4 *index,int_4 N)
-{
-/* ATTENTION, Ce programme tri un tableau de flottants REMPLI avec des ENTIERS!!!!!
-  14 = nb max d'entrees que la pile (stack) peut contenir. Ce 14 limite la longueur 
-             maximale possible pour les vecteurs a 32 768 ( = 2**15 ) */
-
-int_4 stklo[14], stkhi[14], hi, nstak, i, limlo, limhi, lo, ikey;
-float dkey;
-
-/* initialisations */
-
-for (i=0; i<=N-1 ; i++) index[i]=i;
-nstak=0;
-limlo=0; limhi=N-1;
-
-grande_boucle:
-  dkey = *(datum+limlo);
-  ikey = *(index+limlo);
-
-/* compare tous les elements d'un ss-vecteur entre limlo et limhi avec la donnee-cle courante */
-
-  lo=limlo; hi=limhi;
-  
-sous_boucle_1:
-  if ( lo == hi ) goto lo_egal_hi;
-
-  if ( *(datum+hi) <= dkey ) goto remplacement_lo;
-  hi = hi - 1;
-
-/* le pointeur  hi doit pointer une donnee plus petite que la cle qui va etre remplacer */
-
-  goto sous_boucle_1;
-
-remplacement_lo:
-  *(datum+lo) = *(datum+hi);
-  *(index+lo) = *(index+hi);
-  lo = lo + 1;
-  
-sous_boucle_2:
-  if ( lo == hi ) goto lo_egal_hi;
-
-  if ( *(datum+lo) >= dkey ) goto remplacement_hi;
-
-  lo = lo + 1;
-  goto sous_boucle_2;
-
-remplacement_hi:
-  *(datum+hi) = *(datum+lo);
-  *(index+hi) = *(index+lo);
-  hi = hi - 1;
-
-/* le pointeur lo doit pointer une donnee plus grande que la cle qui va etre remplacer */
-
-  goto sous_boucle_1;
-
-lo_egal_hi:
-
-/* lo et hi sont egaux, et pointent sur une valeur qui va etre remplacer. Tant que toutes les valeurs sous ce point sont inferieures a la cle et que toutes les valeurs apres ce point sont superieures a la cle, c'est la que nous remettrons la cle dans le vecteur */
-
-  *(datum+lo) = dkey;
-  *(index+lo) = ikey;
-
-/* A ce point du ss-prog. toutes les donnees entre limlo et lo-1 inclus sont inferieurs a datum(lo), et toutes les donnes entre lo+1 et limhi sont superieures a datum(lo)  
-   Si les deux ss-tableaux ne contiennent pas plus d'un element, on prend l'intervale le plus recent de la pile ( si le stack est vide c'est fini ). Si le plus grand des deux ss-tableaux contient plus d'un element et si le plus petit contient au plus un element, alors on oublie le plus petit et on reduit l'autre. Si le plus petit ss-tableau contient au moins 2 elements, alors on place le plus grand ss-tableau dans la pile et on processe le ss-tableau.  */
-  
-  if ( (limhi-lo) > (lo-limlo) ) goto cas_1;
-
-/* cas 1 : le ss-tableau inferieur est plus long. Si il contient un element au plus, alors on prend l'intervalle du stack le plus recent, on le ramene et on travaille dessus */
-
-  if ( (lo-limlo) <= 1) goto test_fin;
-
-/* si le ss-tableau superieur ( le + court ss-tableau ) contient  un element au plus alors on processe le  ss-tableau inferieur ( le + long), mais si le ss-tableau superieur contient plus d'un element, alors on place le  ss-tableau inferieur ( le + long) sur la pile et on processe le ss-tableau superieur. */
-
-  if ( (limhi-lo) >= 2) goto cas_1b;
-
-/* cas 1a : si le ss-tableau superieur ( le + court ss-tableau ) contient  un element au plus alors on revient en arriere et on agit sur le  ss-tableau inferieur ( le + long) */
-
-  limhi=lo-1;
-  goto grande_boucle;
-
-/* cas 1b :  si le ss-tableau superieur ( le + court ss-tableau ) contient plus d'un element, alors on place le  ss-tableau inferieur ( le + long) sur la pile et on processe le ss-tableau superieur. */
-
-cas_1b:
-  nstak=nstak+1;
-  *(stklo+nstak)=limlo;
-  *(stkhi+nstak)=lo-1;
-  limlo=lo+1;
-  goto grande_boucle;
- 
-/* cas 2 : le ss-tableau superieur est plus long, si il contient  un element au plus alors on agit sur l'intervalle le plus recent de la pile. */
-
-cas_1:
-  if ( (limhi-lo) <= 1) goto test_fin;
-
-/* si le ss-tableau inferieur ( le + court ss-tableau ) contient  un element au plus alors on processe le  ss-tableau superieur ( le + long), mais si le ss-tableau inferieur contient plus d'un element, alors on place le  ss-tableau superieur ( le + long) sur la pile et on processe le ss-tableau inferieur. */
-
-   if ( (lo-limlo) >= 2) goto cas_2b;
-
-/*  cas 2a : si le ss-tableau inferieur ( le + court ss-tableau ) contient  un element au plus alors on revient en arriere et on agit sur le  ss-tableau superieur ( le + long) */
-
-  limlo=lo+1;
-  goto grande_boucle;
-  
-/* cas 2b :  si le ss-tableau inferieur ( le + court ss-tableau ) contient plus d'un element, alors on place le  ss-tableau superieur ( le + long) sur la pile et on processe le ss-tableau inferieur. */
-
-cas_2b:
-  nstak=nstak+1;
-  *(stklo+nstak)=lo+1;
-  *(stkhi+nstak)=limhi;
-  limlo=lo-1;
-  goto grande_boucle;
-   
-/* on prend l'intervalle le plus recent de la pile. Si le stack est vide, c'est fini !!! */
-        
-test_fin:
-  if (nstak <= 0) return (1);
-  limlo = *(stklo+nstak);
-  limhi = *(stkhi+nstak);
-  nstak=nstak-1;
-  goto grande_boucle;
-
-}
-
 /*===================================================================================*/
 /*
@@ -696 +427 @@
                 }
         }
+        /* pour avoir un retour d'indice entre 0 et n-1 */
+        for (j=0;j<n;j++) indx_c[j]=indx_c[j]-1;
 }
 #undef SWAP_INDEXR4
@@ -780 +513 @@
                 }
         }
+        /* pour avoir un retour d'indice entre 0 et n-1 */
+        for (j=0;j<n;j++) indx_c[j]=indx_c[j]-1;
 }
 #undef SWAP_INDEXR8

trunk/SophyaLib/NTools/nbtri.h

@@ -21 +21 @@
 int_4 tri_entier ( int_4 *tab,int_4 *indx,int_4 N);
 
-int_4 tri_rapide_I (int_4 *datum,int_4 *index,int_4 N);
-int_4 tri_rapide_F (float *datum,int_4 *index,int_4 N);
-
 int qSort_Float(const void *a1,const void *a2);
 int qSort_Dble(const void *a1,const void *a2);