Algorithe de trie de complexité linéaire!

Résolu/Fermé

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

2 réponses

Réponse 1 / 2

yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476
15 juin 2008 à 15:15

Les clés sont-elles uniques ?

imedmab Messages postés 2 Date d'inscription dimanche 15 juin 2008 Statut Membre Dernière intervention 21 juin 2008
15 juin 2008 à 16:43

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

yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476 > imedmab Messages postés 2 Date d'inscription dimanche 15 juin 2008 Statut Membre Dernière intervention 21 juin 2008
15 juin 2008 à 16:54

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.

imedmab Messages postés 2 Date d'inscription dimanche 15 juin 2008 Statut Membre Dernière intervention 21 juin 2008 > yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024
15 juin 2008 à 17:13

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;
}

yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476
15 juin 2008 à 17:22

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.

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

Réponse 2 / 2

anonyme
30 juin 2013 à 20:34

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

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
30 juin 2013 à 20:43

Ceci n'est pas linéaire :

tant que i<=N
pour k de 1 à tableau[j]

anonyme
30 juin 2013 à 21:16

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

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
30 juin 2013 à 21:47

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

anonyme
1 juil. 2013 à 18:57

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.

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
Modifié par KX le 1/07/2013 à 19:23

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

Newsletters