Discussion :

[joe0703]

bonjour,
Le plus important est dit dans le titre de mon article ^^"
je suis étudiant en programmation informatique
je suis actuellement sur un TP mais le soucis est que je bloque complètement sur une notion que je ne comprend pas .
Le but du sujet est de crée une fonction de tri sort(int* begin,int*end,char* type,char sens)
recevant donc un pointeur sur le début d un tableau , un pointeur sur la fin d un tableau, soit quicksort ( que l on devra coder ) soit fusion ( que l on devra code) ET le sens de tri ( 'd' ou 'c' pour croissant et décroissant ). Je suis malheureusement bloquer sur la notion de pointeur et de tableau .... je n'arrive pas a assimiler et a comprendre comment a partir d un pointeur de début et un pointeur de fin on peut parcourir puis gérais un tableau....
En désespoir de cause je me tourne donc vers vous afin de savoir si une âme charitable pourrais m'expliquer le mode de fonctionnement d un parcours de tableau a partir de mes deux pointeur ....

j'ai pour l instant juste fait un main que j’espère être correcte pour que ma fonction reçoivent les dites informations ^^"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    int indice =0;
    cout<<"taille du tableau ?"<<endl;
    cin >> indice;
    int tableau[indice];
    int x;
    for(int i=0; i < indice; ++i)
    {
        cout << "Valeur pour la case " << i << " ? :" << endl;
        cin >> x;
        tableau[i] = x;   //On remplit la case correspondante
    }
    int *debut = tableau;
    int*fin = tableau[indice];
    char* type;
    char sens;
    cout << "QUICKSORT ou Fusion ? " << endl;
    cin >> type;
    cout << "Decroissant 'd' ou croissant 'c' ? " << endl;
    cin >> sens;
    sort(debut , fin,type,sens);
}

j'ai également commencer mon sort qui donne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
sort(int* begin,int*end,char* type,char sens)
{
    if (sens == "d")
    {
        if (type =='Fusion')
        {
           fusiondecroissant(begin,end);
        }
        else if (type =='QuickSort')
        {
             quickSortdecroissant( begin, end);
        }
        else
            cout<<"ce type de tri n'existe pas"<<endl;
    }
    else if(sens =='c')
            {
        if (type =='Fusion')
        {
           fusioncroissant(begin,end);
        }
        else if (type =='QuickSort')
        {
            quickSortCroissant( begin, end);
        }
        else
            cout<<"ce type de tri n'existe pas"<<endl;
    }
    else
            cout<<"entrez un sens de tri valide"<<endl;
}

et c'est la après que je ne sais comment faire car comme je l'indique plus haut je n'est pas saisie la notion de parcours d'un tableau a partir d'un pointeur...et je n'est rien trouver sur internet qui resemble un temps soit peut a ce que l'on a vu en cours .....

MERCI d'avance aux âme chaleureuse qui m'accorderont un peu de leur temps pour tenter de faire entrer ces notion dans mon crane de piaf ^^"

[foetus]

Effectivement c'est un peu technique parce que, tu n'as pas le nombre d'éléments dans l'intervalle (ni la taille de ton tableau mais dans ton cas là tu n'en as rien à faire)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
    if ((begin == NULL) || (end == NULL)) { return; }
 
    if (begin < end) { // or if (begin <= end)
       do {
 
//        ...
 
          ++begin; // next case
       } while(begin < end); // or while(begin <= end)
    }

Édit: Je travaille avec begin, mais tu peux utiliser une variable temporaire pour ce parcours int* tmp = begin;.

[joe0703]

plutot que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  if ((begin == NULL) || (end == NULL)) { return; }

je peut faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  if ((begin == end == NULL)) { return; }

non ?

et donc il suffit just incrementer begin ? par contre avec ++ ? pas begin +1 ?

incrémenter le début revient donc a faire tableau[i++] c est cela ?

et pour la taille du tableau, pour le quisort non j en est pas besoin mais pour le fusion j'en est besoin normalement non ? vu qu'il s'agit de couper le tableau pour trier les sous tableau puis les fusionner non ?
ou il me suffit de faire end/2 ?

edit: on a pas appris a travailler avec des vector ou des tmp ( les chose que l on voit partout sur le net ......

[joe0703]

si je suis la logique de ton code ( avec quelque modification)
pour mon quicksort cela donnerais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void QuickSortCroissant(int* begin, int* end)
{
       if ((begin == NULL) || (end == NULL))
            { return; }
 
    if (begin < end) { 
        for(begin;begin<end;begin++)
       {
           if(begin>begin+1)
           {
               int * memoire;
               memoire=&begin;
               begin=begin+1;
               begin+1=memoire;
 
           }
       }
    }
}

c'est cela ?

[foetus]

if ((begin == end == NULL)) { return; }

non ?

Non, un double test en 1 . Si le compilateur ne fait pas la tronche, il y a 90% de chance que cela ne fasse pas ce que tu penses

et donc il suffit just incrementer begin ? par contre avec ++ ? pas begin +1 ?

Oui, le pointeur contient l'adresse d'une case. Et comme les éléments de ton tableau sont contiguës, il faut juste incrémenter de 1 (et avec algorithmie des pointeurs on passe au suivant)

Après ++ ou + 1 c'est la même chose (<- enfin presque)

incrémenter le début revient donc a faire tableau[i++] c est cela ?

Non parce avec tableau[i++] tu prends la valeur à l'indice i, et tu incrémentes ton index

il s'agit de couper le tableau pour trier les sous tableau puis les fusionner non ?

Je m'en fiche de ton tri: regarde wiki

ou il me suffit de faire end/2 ?

divisé par 2 avec une adresse (un pointeur)

Soit tu fais une boucle pour compter le nombre d'éléments, soit tu tentes (end - begin) / (2 * sizeof(int)) à 1 près

c'est cela ?

Il y a de l'idée, mais il manque déjà le pivot

Sinon, tu as affaire à un tableau linéaire, pas à une liste chaînée: il faut inverser les valeurs pour les adresses des cases


Indication: array[i] est équivalent à *(array + i)

[joe0703]

Non parce avec tableau[i++] tu prends la valeur à l'indice i, et tu incrémentes ton index

je comprend pas car begin = tableau[0] non ?
donc begin +1 = tableau[1] qui lui meme est égale a tableau [0+1] ( ou i+1) non ?

divisé par 2 avec une adresse (un pointeur)

pardon oui en effet ^^ je voulais mettre
&end/2 car si je m abuse le pointeur pointe vers l adresse du tableau non ? donc si
end=tableau[10]
&end vaudra 10 non ?

edit: egalement e ne comprend pas vraiment comment on peut définir un pointeur sur le dernier élément du tableau sachant que l on ne connait pas la taille du tableau pour ma part au début j'ai fait

int*fin = (tableau+indice);

mais si je ne me trompe pas cela ne pointe pas sur l adresse mais sur la valeur contenu dans tableau[indice] non ?

[Bousk]

C'est un tableau, donc les cases sont contigües.
Après c'est de la simple arithmétique de pointeurs.
begin vaut &tab[0]; end vaut &tab[tab size];
Généralement end est la première adresse invalide, c'est ainsi que fonctionne la STL en tous cas. J'ignore si ton exercice suit cette règle ou non.
A partir de là la taille ben c'est end-beginEt pour parcourir tu fais une simple boucle while(begin < end) et tu oublies pas d'incrémenter begin dans la boucle.

[joe0703]

Après c'est de la simple arithmétique de pointeurs.

^^" simple ? ^^" ca depend le point de vu si tu veux mon avis ^^" car pour ma part j'ai beaucoup de mal a assimiler les notions

Généralement end est la première adresse invalide,

premiere adresse invalide ? c est a dire ? end=null ?
pour mon tp end pointe sur la fin du tableau donc normalement sur l adresse de la dernière valeur du tableau et non pas sur une adresse invalide

c'est ainsi que fonctionne la STL en tous cas

heuuuu STL ? quesaquo ^^" ?

begin vaut &tab[0]; end vaut &tab[tab size];

c est la que je bloque le plus je pense

begin = &tab[0]
cela si j ai bien compris les cour en ligne equivaux a dire que
begin = adresse de tab[0]
non ?
car si c est le cas mon soucis est donc comment connaitre la valeur justement contenu a cette adresse

partir de là la taille ben c'est end-begin

juste end - beggin ? l adresse end - l adresse beggin c est ca ? ce qui donne (vu que les adresse du tableau sont continue , le nombre d élément du tableau c est ca ? )

donc si je me trompe pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
    int tab[7] = {10, 2,573, 26000,1,5,4};
    int *debut = tableau;
 
    int*fin = (tableau+7);
    int TailleTableau= fin-debut

c est ca ?
Par contre reste toujours mon soucis de savoir comment recuperais les valeurs contenu dans les adresses pointer

[foetus]

juste end - beggin ? l adresse end - l adresse beggin c est ca ?

Réfléchis si begin c'est l'adresse de la première case (disons 0xC10), la deuxième case sera sizeof(int) plus loin (soit 0xC14 (32-64) ou 0xC18 (64)), la troisième 2 fois sizeof(int) (soit 0xC18 (32-64) ou 0xC20 (64)) et ainsi de suite

Par contre reste toujours mon soucis de savoir comment recuperais les valeurs contenu dans les adresses pointer

En déférençant avec la petite étoile :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
    int* tmp = begin;
 
    int value1 = *(tmp); // or *(begin + i)
    int value2 = begin[i]; // <- mais pas sûr parce que on confond pointeur et tableau

[joe0703]

cela est il correct donc ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void quickSortCroissant(int arr[], int* left, int* right) {
 
    int* tmpdebut = left;
    int* tmpfin = right;
    int i = tmpdebut, j = tmpfin;
    int i = left, j = right;
    int tmp;
    int pivot = arr[ right-left ) / 2];
 
      /* partition */
    while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
 
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

[joe0703]

Réfléchis si begin c'est l'adresse de la première case (disons 0xC10), la deuxième case sera sizeof(int) plus loin (soit 0xC14 (32-64) ou 0xC18 (64)), la troisième 2 fois sizeof(int) (soit 0xC18 (32-64) ou 0xC20 (64)) et ainsi de suite

heuuuu rien compris ^^"

[foetus]

heuuuu rien compris ^^"

Ton tableau est contiguë: c'est le cas le plus trivial de la Terre

Donc si tu codes int array[] = {8, 52, 96, 946}.

En mémoire ce sera | 8 | 52 | 96 | 946 |

Et comme en C/ C++, un int occupe sizeof(int) en mémoire (soit 4 soit 8 en fonction que tu sois en 32 bits ou en 64 bits)

Donc ton tableau: | 8 à l'adresse X | 52 à l'adresse (X+ 4/8) | 96 à l'adresse (X+ 8/16) | 946 à l'adresse (X+ 12/24) |

[joe0703]

donc par exemple si comme pivo je veux l 'element premier du tableau je doit faire

int pivot = debut / sizeof(int)

c est ca ?

et si je veux celui du milieu je ferais donc

(debut+((fin-debut)/2))/sizeof(int)

[koala01]

Salut,

Je n'ai pas (une fois n'est pas coutume, hein?) lu toutes les interventions, il y aura donc peut être des redites

Mais, pour l'essentiel, ce qu'il faut comprendre, c'est qu'un pointeur n'est jamais qu'une valeur numérique entière (généralement) non signée qui représente... l'adresse mémoire à laquelle nous (devrions) pourrons trouver un élément du type indiqué.

L'avantage qu'il y a avec les pointeurs, c'est que leur arithmétique prend en compte la taille de l'élément pointé, et qu'une simple incrémentation (++pointer;) suffit à passer à l'adresse mémoire à laquelle nous trouverons l'élément suivant.

Si l'on part du principe que les éléments que tu dois trier sont placés de manière contigüe en mémoire (ce qui est le cas lorsque l'on parle d'un tableau d'éléments), que le pointeur "begin" représente l'adresse du premier élément du tableau et que le pointeur "end" représente l'adresse "de ce qui suit" le dernier élément du tableau, on peut assez facilement connaitre le nombre d'éléments contenus dans le tableau en ayant recours à std::distance(begin, end).

Mais le nombre d'éléments n'est pas forcément primordial, car il ne sera utilisé que si tu décide d'avoir recours à une boucle "pour" "classique (for(size_t i=0;i<nbElements;++i)).

Or, il y a également possibilité d'utiliser d'autres boucles, dont principalement la boucle "tant que" (while(condition est respectée){/* ce qui doit être fait*/}) qui en l'occurrence pourrait très bien ressembler à while(ptr!=end){/*ce qui doit être fait*/} pour autant que tu prenne la précaution de faire varier ptr de telle sorte qu'il finisse par... atteindre l'adresse de end.

Pour le reste, il n'y a plus qu'à mettre en place l'algorithme de tri, mais ca, je vais te laisser y réfléchir à ton aise

[joe0703]

oui foetus ma plus ou moins expliquer la meme chose et ma donner ceci

if ((begin == NULL) || (end == NULL)) { return; }

if (begin < end) { // or if (begin <= end)
do {

// ...

++begin; // next case
} while(begin < end); // or while(begin <= end)
}

a l heure actuel le soucis c est comme je disais trouver les valeur associer au adresse pointer car foetus me dit de faire ( si j ai bien compris)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

begin/sizeof(int)

pour obtenir par exemple la valeur de t[0] ( vu que begin au tout debut pointe sur le 1er element du tableau )

MAIS le commentaire d avant il me dit

En déférençant avec la petite étoile :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 int* tmp = begin;
    int value1 = *(tmp); // or *(begin + i)
    int value2 = begin[i]; // <- mais pas sûr parce que on confond pointeur et tableau

je suis donc perdu, quel méthode est la bonne ? ou si les deux fonctionnes, laquelle est la plus efficace

[foetus]

a l heure actuel le soucis c est comme je disais trouver les valeur associer au adresse pointer car foetus me dit de faire ( si j ai bien compris)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

begin/sizeof(int)

Ahahahaha c'est pour cela que tu cale

Non, c'est pour trouver le nombre d'éléments entre begin et end.
Soit tu fais une boucle (de begin jusqu'à end), soit tu tentes (end - begin) / (sizeof(int)).

Reprends mon tableau: | 8 à l'adresse X | 52 à l'adresse (X+ 4/8) | 96 à l'adresse (X+ 8/16) | 946 à l'adresse (X+ 12/24) |

Si begin c'est la première case (à l'adresse X),
alors si end c'est la troisième 96 alors ((X + 8 ou 16) - X) / (4 ou 8) -> 2 (à 1 près)
alors si end c'est la quatrième 946 alors ((X + 12 ou 24) - X) / (4 ou 8) -> 3 (à 1 près)

[foetus]

Je n'ai pas (une fois n'est pas coutume, hein?) lu toutes les interventions

Oui cela devient un fil de discussion pareil à ceux que tu interviens avec tes longues réponses

[joe0703]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
fonction triFusion(int * debut, int * fin)
    {
       int taille=fin-debut;
       int milieu=taille/2;
       int*PointeurMilieu= debut+milieu;
 
        if ((begin == NULL) || (end == NULL)) 
            { 
                return; 
            }
        else
                  return fusion(triFusion(int*debut,int*PointeurMilieu), triFusion(int*(PointeurMilieu+1),int*fin),))        
    }

j ai commencer cela pour mon tri par fusion
j ai fait mon pseudo code de ma fonction
entrée:
2 tableaux triés A et B
sortie :
un tableau trié qui contient exactement les éléments des tableaux A et B

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
fonction fusion(A[int*debut, int*milieu], B[int*milieu+1, int*fin])
      si A est le tableau vide
              retourner B
      si B est le tableau vide
              retourner A
      si A[1] ≤ B[1]
              retourner A[1] :: fusion(A[2, …, a], B)
      sinon
              retourner B[1] :: fusion(A, B[2, …, b])

mais comme vous pouvez le voir ma fonction fusion prend en compte deux tableau ( ce qui est logique) mais je voi pas comment je peut la modifier pour recevoir les pointeur fourni par ma fonction tri-fusion , j ai bien tenter

fonction fusion(A[int*debut, int*milieu], B[int*milieu+1, int*fin])

mais je pense pas que cela soit permis nn ?

[joe0703]

et pour quicksort j ai fait cela vous en pensez quoi ? savoir si j ai bien compris

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void quickSortCroissant( int* debut, int* fin ) {
 
    int* tmpdebut = debut; 
    int* tmpfin = fin;
    int valuedebut = *(tmpdebut);//valeur stocker a l adresse pointer par debut
    int valuefin = *(tmpdefin);//valeur stocker a l adresse pointer par fin
    int  taille=end-debut;//taille du tableau
    int  milieu=taille/2;
    int* tmp = debut+milieu;//pointeur visant l adresse de la valeur au milieu du tableau
    int pivot = *(tmp);//le pivot correspond a la valeur stocker par l adresse pointer par tmp
      /* partition */
    while (debut != fin) {//temps que le pointeur fin et le pointeur début ne pointe pas la meme adresse
            while (valuedebut < pivot)//faire temps que la valeur de l élément étudier est inférieur au pivot
                  debut+1;
            while (valuefin > pivot)
                  fin-1;
            if (valuedebut <= valuefin) {
                  tmp = valuedebut;
                  valuedebut = valuefin;
                  valuefin = tmp;
                  debut+1;
                  fin-1;
            }
      };
 
}

[Bousk]

A[int*debut, int*milieu], B[int*milieu+1, int*fin] doit-on deviner ce que veut dire cette écriture ?

debut+1; ça ressemble furieusement à une tentative de copier/coller sans réfléchir de morceau de messages précédents.
Il n'y a aucune chance que ton professeur t'ait donné un tel exercice sans la possibilité de le résoudre, donc tu devrais commencer par (re)lire tes cours plutôt que de tenter des écritures au petit bonheur. L'algorithme en soit se trouve sur internet aisément, mais là c'est ta syntaxe basique du langage qui est mauvaise. Et ça ne fait rien d'autre que ce qui écrit : additionner 1 à l'adresse de debut, puis... rien. Strictement inutile donc.
Sans compter que même la logique des expressions de base ne semble pas maîtrisée puisque while (valuedebut < pivot) sans que ni valuedebut ni pivot ne change - puisque la seule ligne exécutée sous cette condition est debut+1; - mène bien évidemment droit à une boucle infinie.