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.