Algorithe de trie de complexité linéaire!

Résolu/Fermé

imedmab Messages postés 2 Statut Membre -
anonyme - 1 juil. 2013 à 20:52

Bonjour,

Je prépare mes examens et je cherche une solution pour la question suivante.
***
On veut trier un tableau t de N enregistrements dont chaque clé est un entier de l'intervalle [0,N-1].
Décrivez un algorithme de complexité linéaire permettant de trier ce type de données
(on pourra pour simplifier rendre un tableau s contenant les données de t triées).
***

Alors, à mes connaissances, on ne peut pas faire mieux que (n*log(n) en complexité quand il s'agit de trier un tableau de n données ?!)
Est ce que quelqu'un a une idée?

Merci de répondre

Configuration: Windows XP
Firefox 2.0.0.14

Afficher la suite

2 réponses

Réponse 1 / 2
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588

Les clés sont-elles uniques ?
0
1. imedmab Messages postés 2 Statut Membre
  
  Salut,
  Oui.
  En fait l'exercice dit qu'elles sont distinctes (c'était un oubli de ma part)
  
  N.B:
  clairement j'ai un problème (de compréhension) car en fait je ne vois pas clairement pourquoi c'est important de le savoir?
  Et c'est quoi la différence entre la clé et la donnée du tableau?
  Et est ce qu'on trie les données ou les clés...et l'exercice demande de trier les clés ou les données?
  bref, ce n'est pas clair pour moi
  merci de me donner un coup de main
  
  0
2. yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588 > imedmab Messages postés 2 Statut Membre
  
  Les données du tableau pourraient être des renseignements (nom, prénom, data de naissance) de personnes. La clé, c'est le critère de tri, qui pourrait être, par exemple, l'àge de la personne, ou le numéro de son département.
  
  Dans le cas de l'exercice, on est dans in cas extremement simple, puisque on a N enregistrements, avec des clés uniques de 0 à N-1. Il suffit donc de parcourir le tableau T. Pour chaque enregistrement, calculer sa clé, et la clé nous donne la position du tableau S où il faut copier l'enregistrement.
  
  0
3. imedmab Messages postés 2 Statut Membre > yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention
  
  merci.
  Et comment calcule t-on les clés?
  cle (t[i]) renvoie t'il la clé de t[i]?
  
  ainsi:
  je propose
  
  int[] tri(int[] t,int N) {
  int[] s;
  int cle;
  int i=0;
  for(i=0;i<=N-1){
  cle=cle(t[i]);
  s[cle]=t[i];
  }
  return s;
  }
  
  0
4. yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention 1 588
  
  La logique me semble correcte.
  Comme on te demande un algorithme, je suppose que tu es libre de le décrire dans le langage que tu choisis.
  
  0
5. imedmab Messages postés 2 Statut Membre > yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention
  
  une dernière intervention :
  ma question c'était plus comment accéder à la clé de chaque t[i]?
  la fonction cle(t[i]) existe-elle ?
  
  merci
  
  0
Réponse 2 / 2
anonyme
Bonjour,

Puisque ton espace des clé est fini. tu peut faire un tri linéaire:
C'est le suivant:
```
pour i de 1 à N (N le cardinal de tes donnée)
tableau[i]=0
fin pour

pour i de 1 à M (M la taille de tes données)
incrémenter tableau[données[i]]
fin pour

soit retour le tableau a retourné
soit i,j
i=1
j=1
tant que i<=N
pour k de 1 à tableau[j]
retour[i]=j
incrémenter i
fin pour
incrémenter j
fin tant que
```
0
1. KX Messages postés 19031 Statut Modérateur 3 020
  
  Ceci n'est pas linéaire :
  
  tant que i<=N pour k de 1 à tableau[j]
  
  0
2. anonyme
  
  Si c'est bien en O(m)
  
  Dans l'algo, N est le cardinal de l'espace des clé (donc il est constant)
  C'est M la variable qu'on parle (qui symbolise N, désolé mes conventions on prêter à confusion)
  
  Je corrige l'algorithme, (je ne pouvais pas éditer le précédent poste)
  pour i de 1 à M (M le cardinal de l'espace des clés) tableau[i]=0 fin pour pour i de 1 à N (N la taille de tes données) incrémenter tableau[données[i]] fin pour soit retour le tableau a retourné soit i,j i=1 j=1 tant que j<=N pour k de 1 à tableau[i] retour[j]=i incrémenter j fin pour incrémenter i fin tant que
  
  0
3. KX Messages postés 19031 Statut Modérateur 3 020
  
  Effectivement j'avais mal compris le rôle de "tableau" qui en fait ne sert à rien... et du coup ton algorithme ne fais rien du tout !
  
  Voici un exemple : Donnees = [ (2,"DEUX"), (1,"UN"), (4,"QUATRE"), (3,"TROIS") ]
  Et le résultat attendu : Retour = [ (1,"UN"), (2,"DEUX"), (3,"TROIS"), (4,"QUATRE") ]
  
  Ce que fais ton algo :
  
  pour i de 1 à 4 tableau[i]=0 fin pour
  
  Tableau = [0, 0, 0, 0]
  
  pour i de 1 à 4 incrémenter tableau[données[i]] fin pour
  
  Tableau = [1, 1, 1, 1]
  
  i=1 j=1 tant que 1<=4 pour k de 1 à 1 retour[1]=1 j=2 fin pour i=2 tant que 2<=4 pour k de 1 à 1 retour[2]=2 j=3 fin pour i=3 tant que 3<=4 pour k de 1 à 1 retour[3]=3 j=4 fin pour i=4 tant que 4<=4 pour k de 1 à 1 retour[4]=4 j=5 fin pour i=5 fin tant que
  
  Retour = [1, 2, 3, 4]
  
  On est très loin d'avoir trié quoi que ce soit ici... en particulier parce que jamais tu ne considères les valeurs à trier !
  
  Remarque : étant donné que cette discussion est résolu depuis 5 ans (!!!) il n'est peut-être pas utile de trop s'attarder là dessus, je t'invite à regarder la solution d'imedmab donnée ici : #4
  
  0
4. anonyme
  
  Je l'ai peut-être mal écrit:
  
  L'idée est juste de compter les élement (une passe)
  Puis des les réécrire ensuite (une passe)
  
  Je vais essayer de faire mieux:
  
  Tes éléments sont dans un emsemble fini F
  soit get_id(F f) qui donne l'identifiant de l'élément f
  soit get_element(int id) qui donne l'élément d'identifiant id
  
  C'est une bijection de F dans (1..card(F))
  
  voila l'algo corrigé:
  
  compteur[1..card(F)) remplir de 0 pour i de 1 à n compteur[get_id(donneed[i])] ++ // incrémentation fin pour j=1 i=1 tant que i<=n pour k de 1 à tableau[j] retour[i]=get_element(j) i++ // incrémenter i fin pour j++ // incrémenter j fin tant que
  
  Voila, cela te conviendra plus.
  
  0
5. KX Messages postés 19031 Statut Modérateur 3 020
  
  Je ne comprends toujours pas pourquoi tu veux utiliser un tableau "compteur" alors que l'on sait que sa valeur sera 1 sur toutes les cases, vu qu'il y a N éléments, avec N clés distinctes.
  Donc ton k va toujours aller de 1 en 1, et on aura toujours i=j, du coup "retour" contiendra les mêmes éléments dans le même ordre. Il n'y a donc aucun tri d'effectué !
  
  Je reprends la solution donnée en 2008 avec tes notations :
  
  Pour i = 1 à N f = tableau[i] j = get_id(f) resultat[j] = f Fin Pour
  
  0

Newsletters