TD No 1
from http://vernier.frederic.free.fr/Teaching/PimpA

Tris

• Copier le code suivant dans un projet C++ code::Block, compilez et éxécutez.
• Copier le fichier contenant la liste des communes de France. (version compréssé)
  Attention : ce fichier doit etre posé à coté de l'executable, pas du fichier source !!!

// compile avec g++ main.cpp -o main.out
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
using namespace std;

struct Ville{
  string Insee;
  int dep;
  string Nom;
  int Altitude;
  string code_postal;
  float longitude_radian;
  float latitude_radian;
  int pop99;
  float surface;
};
vector<Ville> liste;

void permute (int i, int j) {
  Ville temp = liste[i];
  liste[i] = liste[j];
  liste[j] = temp;
}

void triselection (int n) {
  for (int k=0; k<n-1; k++){
    int meilleur = k;
    for (int i=k+1; i<n; i++)
      if (liste[meilleur].pop99>liste[i].pop99) meilleur = i;
    permute(k, meilleur);
  }
}

void lire_fichier(string s){
  ifstream f(s.c_str());
  string line;
  getline(f,line);
  while(getline(f,line)) {
    Ville v;
    int ind = line.find(";");
    v.Insee = line.substr(0, ind);
    v.dep   =  atoi(v.Insee.substr(0, v.Insee.size()-3).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v.Nom = line.substr(0, ind);

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v.Altitude = atoi(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v.code_postal = line.substr(0, ind);

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v.longitude_radian = atof(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v.latitude_radian = atof(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v.pop99 = atoi(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v.surface = atof(line.substr(0, ind).c_str());

    liste.push_back(v);
  }
  f.close();
}

int main(int, char*[]) {
  lire_fichier("villes.csv");

  for (int i=0; i<liste.size(); i++)
    cout << i << " " << liste[i].Nom << " " << liste[i].surface << endl;

  return 0;
}

Questions sans code à écrire

1. Combien y a t-il de communes en France ?
2. Combien y a t-il de variables par ville ?
3. A quoi sert le getLine(f,line) avant le while ?
4. Que manque t-il dans ce code C++ pour plaire à un prof ?
5. Comment rechercher les communes avec exactement 1000 habitants ? (proposez un algorithme)
6. Comment savoir quelle est la population moyenne et la population médiane d'une commune ?
7. Ecrivez l'algorithme de tri par sélection qui trie les villes par code postal croissant et pour les villes avec le même code, privilégie la population (comme second critère) !

Implémentations

7. Triez et affichez la liste des villes par population croissante avec le tri sélection.
8. Calculez la population médiane.
9. Affichez les 15 plus grandes villes de votre département préféré(SAUF Paris)
10. Implémentez le tri par insertion puis le tri à bulle et vérifiez que vous avez les mêmes resultats.
11. Rajoutez un compteur dans votre méthode de permutation et comparez les 3 tris.
12. Triez les communes par rapport à leurs distances à Paris (Lat:48.8567, Lon:2.3508)
13. Implémentez le tri par tas.
    1. la fonction de quasi-tamisage. Testez sur la liste des communes que cette fonction fait bien remonter Paris si on trie par population.
    2. le tamisage.