Tri par insertion des éléments dans un vector<string>

Version imprimable

Bonjour,

Je suis en train de mettre en oeuvre le tri par insertion des éléments dans un vector<string>, voici comment j'ai conçu mon programme :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#ifndef INSERTIONSORT_H
#define INSERTIONSORT_H
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
class InsertionSort {    
    public:  
        InsertionSort(vector<string>);
        ~InsertionSort();
        InsertionSort();
 
    public:            
        void populate(vector<string>);         
        void sort(vector<string>);   
        void display(vector<string>);                
        void treatment(vector<string>);
};
 
#endif // INSERTIONSORT_H

Code:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include "InsertionSort.h"
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
InsertionSort::InsertionSort(){}
 
InsertionSort::InsertionSort(vector<string> words) {
}
 
InsertionSort::~InsertionSort() {
    cout << "instance is destroyed" << endl;
}
 
void InsertionSort::treatment(vector<string> datastore) {
    populate(datastore);
    sort(datastore);
    display(datastore);
}
 
void InsertionSort::populate(vector<string> datastore) {
    string elements = "";
	char answer;
	do {
		cout << "Enter value : " << flush;
		cin >> elements;
 
		datastore.push_back(elements);
 
		cout << "More elements (y/n)? " << flush;
        cin >> answer;
	} while(answer == 'y' || answer == 'Y');
    cout << datastore.size() << " elements are added to your basket " << endl;
    // display elements added
    vector<string>::iterator it;
    for(it=datastore.begin(); it<datastore.end(); ++it) {
        cout<< *it << endl;
    }
}
 
/**
 * @brief Implémentation du tri par insertion des éléments dans un vector
 * @param datastore le vector pour stocker les éléments
 */
void InsertionSort::sort(vector<string> datastore) {
    int indice = 1; // le parcours du vecteur débute à partir du 2ème élément
    int indiceInserer;
    string valeurAInserer;
 
    while(indice < datastore.size()) {
        // lors du parcours du tableau on recherche la plus petite valeur et on la stocke dans
        // la variable valeurAInserer
        valeurAInserer = datastore[indice];
        indiceInserer = indice - 1; // indice de la valeur à insérer
 
        while((indiceInserer >= 0) && (valeurAInserer <= datastore[indiceInserer])) {
            datastore[indiceInserer + 1] = datastore[indiceInserer];
            indiceInserer = indiceInserer - 1;
        }
        datastore[indiceInserer + 1] = valeurAInserer;
        indice++;
    }
}
 
void InsertionSort::display(vector<string> datastore) {
    cout << "Display basket :" << endl;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <InsertionSort.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
 
using namespace std;
 
int main() {	    
 
    vector<string> fruits(0); // initialize an empty vector of strings
    InsertionSort basket(fruits);
    basket.treatment(fruits);
 
    return EXIT_SUCCESS;
}

Mon problème est où intégrer dans mon code la fonction de tri et comment l'afficher? Il s'agit d'un problème de conception algorithmique ... mais je coince.

Merci d'avance.
Transact.

21/08/2016, 16h21
JolyLoic

Je ne comprends pas trop la question, serait-il possible de la détailler ?

J'espère qu'il ne s'agit que d'un exercice, car dans la vraie vie, on écrirait simplement std::sort(v.begin(), v.end().

Le principal problème technique que je vois par un rapide parcours du code est le passage d'arguments par copie. En Java (je dis ça parce qu'en dessous de ton nom est indiqué développeur Java), quand tu passes en argument une classe, tu passes en réalité un hanldle qui te permet de modifier cette classe. En C++, c'est différent. Ainsi, void sort(vector<string> datastore) va dupliquer le tableau qui lui est passé en entrée, et travailler sur cette copie. Si tu ne veux pas que ça arrive, il faut écrire void sort(vector<string>& datastore), et là, ce qui sera transmis à la fonction est une référence vers le tableau défini à l'extérieur, qui te permet de le modifier.

Mais sinon, je ne vois pas du tout l'intérêt de cette organisation du code. La classe InsertionSort mélange plusieurs responsabilités (saisie de données, tri, affichage des résultats). On doit en créer une instance, mais elle ne stocke aucun état...
Je ferais simplement de la fonction de tri une fonction libre (pas une fonction membre de classe), c'est plus simple, plus propre et plus lisible.
21/08/2016, 16h46
Rony Rauzduel

Bonjour,

Merci pour ton retour, je vais t'apporter quelques précisions.
Il s'agit en effet d'un exercice car à la base je suis développeur Java et je vais basculer vers le "C++" ... en vue d'une redirection professionnelle.
J'avais lu la section du cours sur le passage par valeur et le passage par référence. Je pensais avoir compris ... mais apparemment ce n'est pas le cas. Donc il va falloir revoir cela.

Sachant qu'il s'agit d'un exercice en Java que je refais en "C++", je constate qu'il faut penser différemment et adopter un autre paradigme.
Je vais revoir la conception du code avec tes conseils.

Transact.

Effectivement , en modifiant mon code ainsi :

Code:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void sort(vector<string> &datastore) {
    int indice = 1; // le parcours du vecteur débute à partir du 2ème élément
    int indiceInserer;
    string valeurAInserer;
 
    while(indice < datastore.size()) {
        // lors du parcours du tableau on recherche la plus petite valeur et on la stocke dans
        // la variable valeurAInserer
        valeurAInserer = datastore[indice];
        indiceInserer = indice - 1; // indice de la valeur à insérer
 
        while((indiceInserer >= 0) && (valeurAInserer <= datastore[indiceInserer])) {
            datastore[indiceInserer + 1] = datastore[indiceInserer];
            indiceInserer = indiceInserer - 1;
        }
        datastore[indiceInserer + 1] = valeurAInserer;
        indice++;
    }
}
 
int main() {
 
    //Format: vector<DataType> nameOfVector
    // fruits.push_back(value) ==> adds an element to the END of the vector (also resize it)
    // fruits.at(index) ==> returns element at specified index number
    // fruits.size() ==> returns an unsigned  int equal top the number of elements
    vector<string> fruits(0); // initialize an empty vector of strings
 
 
    fruits.push_back("apple");    
    fruits.push_back("orange"); 
    fruits.push_back("pear");    
    fruits.push_back("pineapple"); 
    fruits.push_back("strawberry");    
    fruits.push_back("mango"); 
    fruits.push_back("grapes");    
    fruits.push_back("banana"); 
    fruits.push_back("watermelon"); 
    fruits.push_back("cherry"); 
    fruits.push_back("raspberry"); 
    fruits.push_back("mandarin"); 
 
    cout << fruits.size() << endl;
    for(unsigned i=0; i<fruits.size(); ++i) {
        cout << fruits[i] << endl;        
        //sort(fruits.begin(), fruits.end());
        sort(fruits);
    }
 
    return EXIT_SUCCESS;
}

J'obtiens le résultat escompté, le code est plus clair, plus lisible et plus propre ...
J'ai utilisé ma fonction personnelle de tri pour vérifier que l'algorithme écrit sur papier était correct.
J'ai ajouté l'opérateur & pour effectuer un passage par référence ==> modification des données du vector
Sans l'ajout de l'opérateur & ==> le tri ne s'effectue pas.
Maintenant je comprends la différence entre le passage par valeur et le passage par référence.

Merci encore pour cet éclaircissement.
Transact.

Citation:

Envoyé par transact

Code:

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
32
33
 
 
int main() {
 
    //Format: vector<DataType> nameOfVector
    // fruits.push_back(value) ==> adds an element to the END of the vector (also resize it)
    // fruits.at(index) ==> returns element at specified index number
    // fruits.size() ==> returns an unsigned  int equal top the number of elements
    vector<string> fruits(0); // initialize an empty vector of strings
 
 
    fruits.push_back("apple");    
    fruits.push_back("orange"); 
    fruits.push_back("pear");    
    fruits.push_back("pineapple"); 
    fruits.push_back("strawberry");    
    fruits.push_back("mango"); 
    fruits.push_back("grapes");    
    fruits.push_back("banana"); 
    fruits.push_back("watermelon"); 
    fruits.push_back("cherry"); 
    fruits.push_back("raspberry"); 
    fruits.push_back("mandarin"); 
 
    cout << fruits.size() << endl;
    for(unsigned i=0; i<fruits.size(); ++i) {
        cout << fruits[i] << endl;        
        //sort(fruits.begin(), fruits.end());
        sort(fruits);
    }
 
    return EXIT_SUCCESS;
}

C'est en effet déjà bien mieux. Quelques remarques :
- Pourquoi tu tries dans la boucle d'affichage ?
- Pour initialiser tes données, tu peux directement écrire :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<string> fruits = {
    {"apple"},   
    {"orange"},
    {"pear"},   
    {"pineapple"},
    {"strawberry"},   
    {"mango"},
    {"grapes"},   
    {"banana"},
    {"watermelon"},
    {"cherry"},
    {"raspberry"},
    {"mandarin"}
 };

- Pour parcourir l'ensemble d'un conteneur, tu peux simplement écrire:

Code:

1
2
3
    for(auto &fruit : fruits) {
        cout << fruit << endl;        
    }