Changeset 1474 in Sophya for trunk/SophyaLib/NTools/nbtri.c


Ignore:
Timestamp:
Apr 19, 2001, 9:38:36 PM (24 years ago)
Author:
cmv
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/SophyaLib/NTools/nbtri.c

    r220 r1474  
    278278}
    279279
    280 /*=========================================================================*/
    281 /*
    282 ++
    283   int_4 tri_rapide_I (int_4 *datum,int_4 *index,int_4 N)
    284         algorythme de tri rapide
    285         ( p114-119 THE ART OF COMPUTER PROGRAMMING, vol. 3 SORTING AND
    286         SEARCHING de D.E. Knuth)
    287 | datum  ( entree/sortie ) -> vecteur de dimension N contenant des ENTIERS
    288 |        desordonnes en entree. Ces elements ressortent ordonnes.
    289 | index  ( sortie ) -> vecteur de dimension N contenant des entiers.
    290 |        Le contenu de la case i de index nous indique la place
    291 |        du ieme element du datum originel.
    292 | tri_rapide = -1 si echec, 1 si reussite de l'operation
    293 --
    294 */
    295 int_4 tri_rapide_I (int_4 *datum,int_4 *index,int_4 N)
    296 {
    297 /* 14 = nb max d'entrees que la pile (stack) peut contenir. Ce 14 limite la longueur
    298              maximale possible pour les vecteurs a 32 768 ( = 2**15 ) */
    299 
    300 int_4 stklo[14], stkhi[14], hi, nstak, i, limlo, limhi, lo, ikey;
    301 int_4 dkey;
    302 
    303 /* initialisations */
    304 
    305 for (i=0; i<=N-1 ;i++)  index[i]=i;
    306 
    307 nstak=0;
    308 limlo=0; limhi=N-1;
    309 
    310 grande_boucle:
    311   dkey = *(datum+limlo);
    312   ikey = *(index+limlo);
    313 
    314 /* compare tous les elements d'un ss-vecteur entre limlo et limhi avec la donnee-cle courante */
    315 
    316   lo=limlo; hi=limhi;
    317  
    318 sous_boucle_1:
    319   if ( lo == hi ) goto lo_egal_hi;
    320 
    321   if ( *(datum+hi) <= dkey ) goto remplacement_lo;
    322   hi = hi - 1;
    323 
    324 /* le pointeur  hi doit pointer une donnee plus petite que la cle qui va etre remplacer */
    325 
    326   goto sous_boucle_1;
    327 
    328 remplacement_lo:
    329   *(datum+lo) = *(datum+hi);
    330   *(index+lo) = *(index+hi);
    331   lo = lo + 1;
    332  
    333 sous_boucle_2:
    334   if ( lo == hi ) goto lo_egal_hi;
    335 
    336   if ( *(datum+lo) >= dkey ) goto remplacement_hi;
    337 
    338   lo = lo + 1;
    339   goto sous_boucle_2;
    340 
    341 remplacement_hi:
    342   *(datum+hi) = *(datum+lo);
    343   *(index+hi) = *(index+lo);
    344   hi = hi - 1;
    345 
    346 /* le pointeur lo doit pointer une donnee plus grande que la cle qui va etre remplacer */
    347 
    348   goto sous_boucle_1;
    349 
    350 lo_egal_hi:
    351 
    352 /* 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 */
    353 
    354   *(datum+lo) = dkey;
    355   *(index+lo) = ikey;
    356 
    357 /* 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) 
    358    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.  */
    359  
    360   if ( (limhi-lo) > (lo-limlo) ) goto cas_1;
    361 
    362 /* 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 */
    363 
    364   if ( (lo-limlo) <= 1) goto test_fin;
    365 
    366 /* 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. */
    367 
    368   if ( (limhi-lo) >= 2) goto cas_1b;
    369 
    370 /* 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) */
    371 
    372   limhi=lo-1;
    373   goto grande_boucle;
    374 
    375 /* 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. */
    376 
    377 cas_1b:
    378   nstak=nstak+1;
    379   *(stklo+nstak)=limlo;
    380   *(stkhi+nstak)=lo-1;
    381   limlo=lo+1;
    382   goto grande_boucle;
    383  
    384 /* 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. */
    385 
    386 cas_1:
    387   if ( (limhi-lo) <= 1) goto test_fin;
    388 
    389 /* 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. */
    390 
    391    if ( (lo-limlo) >= 2) goto cas_2b;
    392 
    393 /*  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) */
    394 
    395   limlo=lo+1;
    396   goto grande_boucle;
    397  
    398 /* 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. */
    399 
    400 cas_2b:
    401   nstak=nstak+1;
    402   *(stklo+nstak)=lo+1;
    403   *(stkhi+nstak)=limhi;
    404   limlo=lo-1;
    405   goto grande_boucle;
    406    
    407 /* on prend l'intervalle le plus recent de la pile. Si le stack est vide, c'est fini !!! */
    408        
    409 test_fin:
    410   if (nstak <= 0) return (1);
    411   limlo = *(stklo+nstak);
    412   limhi = *(stkhi+nstak);
    413   nstak=nstak-1;
    414   goto grande_boucle;
    415 
    416 }
    417 
    418 /*=========================================================================*/
    419 /*
    420 ++
    421   int_4 tri_rapide_F (float *datum,int_4 *index,int_4 N)
    422         Idem tri_rapide_I mais pour un tableau de flottants
    423          REMPLI avec des ENTIERS.
    424 --
    425 */
    426 int_4 tri_rapide_F (float *datum,int_4 *index,int_4 N)
    427 {
    428 /* ATTENTION, Ce programme tri un tableau de flottants REMPLI avec des ENTIERS!!!!!
    429   14 = nb max d'entrees que la pile (stack) peut contenir. Ce 14 limite la longueur
    430              maximale possible pour les vecteurs a 32 768 ( = 2**15 ) */
    431 
    432 int_4 stklo[14], stkhi[14], hi, nstak, i, limlo, limhi, lo, ikey;
    433 float dkey;
    434 
    435 /* initialisations */
    436 
    437 for (i=0; i<=N-1 ; i++) index[i]=i;
    438 nstak=0;
    439 limlo=0; limhi=N-1;
    440 
    441 grande_boucle:
    442   dkey = *(datum+limlo);
    443   ikey = *(index+limlo);
    444 
    445 /* compare tous les elements d'un ss-vecteur entre limlo et limhi avec la donnee-cle courante */
    446 
    447   lo=limlo; hi=limhi;
    448  
    449 sous_boucle_1:
    450   if ( lo == hi ) goto lo_egal_hi;
    451 
    452   if ( *(datum+hi) <= dkey ) goto remplacement_lo;
    453   hi = hi - 1;
    454 
    455 /* le pointeur  hi doit pointer une donnee plus petite que la cle qui va etre remplacer */
    456 
    457   goto sous_boucle_1;
    458 
    459 remplacement_lo:
    460   *(datum+lo) = *(datum+hi);
    461   *(index+lo) = *(index+hi);
    462   lo = lo + 1;
    463  
    464 sous_boucle_2:
    465   if ( lo == hi ) goto lo_egal_hi;
    466 
    467   if ( *(datum+lo) >= dkey ) goto remplacement_hi;
    468 
    469   lo = lo + 1;
    470   goto sous_boucle_2;
    471 
    472 remplacement_hi:
    473   *(datum+hi) = *(datum+lo);
    474   *(index+hi) = *(index+lo);
    475   hi = hi - 1;
    476 
    477 /* le pointeur lo doit pointer une donnee plus grande que la cle qui va etre remplacer */
    478 
    479   goto sous_boucle_1;
    480 
    481 lo_egal_hi:
    482 
    483 /* 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 */
    484 
    485   *(datum+lo) = dkey;
    486   *(index+lo) = ikey;
    487 
    488 /* 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) 
    489    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.  */
    490  
    491   if ( (limhi-lo) > (lo-limlo) ) goto cas_1;
    492 
    493 /* 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 */
    494 
    495   if ( (lo-limlo) <= 1) goto test_fin;
    496 
    497 /* 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. */
    498 
    499   if ( (limhi-lo) >= 2) goto cas_1b;
    500 
    501 /* 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) */
    502 
    503   limhi=lo-1;
    504   goto grande_boucle;
    505 
    506 /* 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. */
    507 
    508 cas_1b:
    509   nstak=nstak+1;
    510   *(stklo+nstak)=limlo;
    511   *(stkhi+nstak)=lo-1;
    512   limlo=lo+1;
    513   goto grande_boucle;
    514  
    515 /* 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. */
    516 
    517 cas_1:
    518   if ( (limhi-lo) <= 1) goto test_fin;
    519 
    520 /* 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. */
    521 
    522    if ( (lo-limlo) >= 2) goto cas_2b;
    523 
    524 /*  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) */
    525 
    526   limlo=lo+1;
    527   goto grande_boucle;
    528  
    529 /* 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. */
    530 
    531 cas_2b:
    532   nstak=nstak+1;
    533   *(stklo+nstak)=lo+1;
    534   *(stkhi+nstak)=limhi;
    535   limlo=lo-1;
    536   goto grande_boucle;
    537    
    538 /* on prend l'intervalle le plus recent de la pile. Si le stack est vide, c'est fini !!! */
    539        
    540 test_fin:
    541   if (nstak <= 0) return (1);
    542   limlo = *(stklo+nstak);
    543   limhi = *(stkhi+nstak);
    544   nstak=nstak-1;
    545   goto grande_boucle;
    546 
    547 }
    548 
    549280/*===================================================================================*/
    550281/*
    … …  
    696427                }
    697428        }
     429        /* pour avoir un retour d'indice entre 0 et n-1 */
     430        for (j=0;j<n;j++) indx_c[j]=indx_c[j]-1;
    698431}
    699432#undef SWAP_INDEXR4
    … …  
    780513                }
    781514        }
     515        /* pour avoir un retour d'indice entre 0 et n-1 */
     516        for (j=0;j<n;j++) indx_c[j]=indx_c[j]-1;
    782517}
    783518#undef SWAP_INDEXR8
Note: See TracChangeset for help on using the changeset viewer.