Algorithe de trie de complexité linéaire! [Résolu/Fermé]

Signaler
Messages postés
2
Date d'inscription
dimanche 15 juin 2008
Statut
Membre
Dernière intervention
21 juin 2008
-
 anonyme -
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

2 réponses

Messages postés
11513
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 juillet 2020
659
Les clés sont-elles uniques ?
Messages postés
11513
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 juillet 2020
659 >
Messages postés
2
Date d'inscription
dimanche 15 juin 2008
Statut
Membre
Dernière intervention
21 juin 2008

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.
Messages postés
2
Date d'inscription
dimanche 15 juin 2008
Statut
Membre
Dernière intervention
21 juin 2008
>
Messages postés
11513
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 juillet 2020

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;
}
Messages postés
11513
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 juillet 2020
659
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.
Messages postés
2
Date d'inscription
dimanche 15 juin 2008
Statut
Membre
Dernière intervention
21 juin 2008
>
Messages postés
11513
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 juillet 2020

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
Messages postés
11513
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
10 juillet 2020
659 >
Messages postés
2
Date d'inscription
dimanche 15 juin 2008
Statut
Membre
Dernière intervention
21 juin 2008

Cela me semble une bonne idée d'imaginer que cette fonction existe.
En fait, elle n'existe pas, mais, dans l'énoncé du problème, rien n'indique comment calculer la clé. Cette fonction représente la recherche de la clé.
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
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.
Messages postés
15932
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 juillet 2020
2 629
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
Non, c'est bien bon.
Il y a des éléments on double, en triple et compteur correspond au nombre d'occurrence de chaque éléments.

Un lien wikipédia qui correspond parfaitement:
http://fr.wikipedia.org/wiki/Tri_comptage

D'ailleurs c'est assez drôle, je ne pensais pas qu'il existait cette page et l'algorithme est mot pour mot celui que j'ai écrit.

Bonne journée.
Messages postés
15932
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 juillet 2020
2 629
"Il y a des éléments on double, en triple et compteur correspond au nombre d'occurrence de chaque éléments"
Non, justement, pas dans le cas qui nous intéresse ici. C'était d'ailleurs la première question de yg_be : "Les clés sont-elles uniques ?", à laquelle imedmab à précisé qu'elles étaient effectivement distinctes. On a donc N valeurs, avec N clés différentes comprise entre 0 et N-1, qui apparaissent donc toute une fois et une seule, il n'y a pas de doublon ici. Restons en au problème initial !
Oui en effet,
D'ailleurs le problème est résolu.
Désolé, j'aurais du mieux lire.

Bonne journée.