Algorithe de trie de complexité linéaire!
Résolu/Fermé
imedmab
Messages postés
2
Statut
Membre
-
anonyme -
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
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
Bonjour,
Puisque ton espace des clé est fini. tu peut faire un tri linéaire:
C'est le suivant:
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
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)
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
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 :
Tableau = [0, 0, 0, 0]
Tableau = [1, 1, 1, 1]
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
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
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é:
Voila, cela te conviendra plus.
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.
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 :
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
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
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.
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;
}
Comme on te demande un algorithme, je suppose que tu es libre de le décrire dans le langage que tu choisis.
ma question c'était plus comment accéder à la clé de chaque t[i]?
la fonction cle(t[i]) existe-elle ?
merci