Discussion :

[sofiane61]

salut
j'ai un tableau de données de type double
je cherche à trier ce tableau afin d'obtenir que les éléments distincts.
j'ai une solution mais c'est un peu long.
quelqu'un a t'il une idée pour résoudre ce probleme?
merci
sof

[Neo82]

Salut

deja quelle est ta solution à toi...

Donne la nous et on verra si il y a moyen de faire plus court

@+

[progfou]

Tu as un tableau de doubles : OK
Tu cherches à trier : OK

Une fois ton tableau trié tu auras les éléments distincts, enfin, je sais pas trop ce que tu entends par là ?

[sofiane61]

exemple
tableau du depart (1,3,1,12,8,3,7)
tableau final (1,3,12,8,7)
on ne garde que les elements disctincts

[Neo82]

Oui...

et as tu des idées pour résoudre ce problème ou pas du tout?

De plus, l'exemple que tu présente n'est pas un "tri"... tu supprimes juste quelques valuers...

Faut-il aussi que les nombres soient classé dans un ordre particulier (croissant ou décroissant..)?

@+

[chrispdc]

Faudrai que tu explique un peu mieux. Parcque si c'est juste suprimé les doubles, c'est vraiment pas dur.

[sovitec]

Une solution toute simple qui doit être optimale en complexité:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Créer une liste de pointeurs vers chaque élément du tableau (O(n))
Trier cette liste (O(n.log(n)))
Supprimer les doublons (O(n))

[Trap D]

Une solution toute simple qui doit être optimale en complexité:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Créer une liste de pointeurs vers chaque élément du tableau (O(n))
Trier cette liste (O(n.log(n)))
Supprimer les doublons (O(n))

Tu es sûr que le tri d'une liste soit en n log(n) ? et pas en n^2 ?

[David.V]

Une solution toute simple qui doit être optimale en complexité:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Créer une liste de pointeurs vers chaque élément du tableau (O(n))
Trier cette liste (O(n.log(n)))
Supprimer les doublons (O(n))

Tu es sûr que le tri d'une liste soit en n log(n) ? et pas en n^2 ?

C'est vieux tout ça pour moi, mais il me semble en effet que le tri "quicksort" est en n.log(n) (sauf dans le pire des cas). Les autres modèles de tri en revanche sont plutôt en n².

[sovitec]

C'est vieux tout ça pour moi, mais il me semble en effet que le tri "quicksort" est en n.log(n) (sauf dans le pire des cas). Les autres modèles de tri en revanche sont plutôt en n².

Pour être exact le quicksort est en n.log(n) en moyenne mais en n² dans le pire des cas. Il existe des tris tels que le heapsort qui sont en n.log(n) dans le pire des cas.

[progfou]

Il est peut être possible de faire un tri légèrement plus "intelligent" que le simple fait de trier.
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Pour i de 0 à taille_tableau-1 
  Prendre la valeur tableau[i]
  Si elle existe dans le tableau d'arrivée
     ne pas la stocker et passer i=i+1
  Sinon
     la placer dans le tableau d'arrivée.
     i=i+1
FinPour
Trier Tableau arrivée si nécessaire.

[sovitec]

Il est peut être possible de faire un tri légèrement plus "intelligent" que le simple fait de trier.
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Pour i de 0 à taille_tableau-1 
  Prendre la valeur tableau[i]
  Si elle existe dans le tableau d'arrivée
     ne pas la stocker et passer i=i+1
  Sinon
     la placer dans le tableau d'arrivée.
     i=i+1
FinPour
Trier Tableau arrivée si nécessaire.

Rechercher un élément dans un tableau non trié est en O(n), donc l'algo si dessus est en O(n²).

[progfou]

Il souhaite placer les éléments dans un tableau en supprimant les doublons, le tri était pour lui une solution simple. Cependant, pour répondre à la question, point n'est besoin de trier .
Or, le parcours du tableau est en O(n), donc la complexité de mon algo est en O(n) non ?
Si on supprime le tri à la fin.

[sovitec]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Pour i de 0 à taille_tableau-1 
  ...
  Si elle existe dans le tableau d'arrivée
  ...

Tester si une valeur est dans le tableau d'arriver se fait en O(n), puisque le tableau n'est pas trié. Il y a donc 2 boucles imbriquées en O(n), soit une complexité globale en O(n²).

[ben04]

Si tu utilise le C++ tu peux faire cela en 3 lignes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
vector<double>vec;
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

[Trap D]

Une solution toute simple qui doit être optimale en complexité:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Créer une liste de pointeurs vers chaque élément du tableau (O(n))
Trier cette liste (O(n.log(n)))
Supprimer les doublons (O(n))

Tu es sûr que le tri d'une liste soit en n log(n) ? et pas en n^2 ?

C'est vieux tout ça pour moi, mais il me semble en effet que le tri "quicksort" est en n.log(n) (sauf dans le pire des cas). Les autres modèles de tri en revanche sont plutôt en n².

Je parle bien de listes (chaînées comme en C), pas des tableaux pour lesquels les algo de tri arrivent à être en n Log(n).

[David.V]

Une solution toute simple qui doit être optimale en complexité:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Créer une liste de pointeurs vers chaque élément du tableau (O(n))
Trier cette liste (O(n.log(n)))
Supprimer les doublons (O(n))

Tu es sûr que le tri d'une liste soit en n log(n) ? et pas en n^2 ?

C'est vieux tout ça pour moi, mais il me semble en effet que le tri "quicksort" est en n.log(n) (sauf dans le pire des cas). Les autres modèles de tri en revanche sont plutôt en n².

Je parle bien de listes (chaînées comme en C), pas des tableaux pour lesquels les algo de tri arrivent à être en n Log(n).

C'est un problème de vocabulaire alors. Il fait mention d'une liste certes, mais tout porte à croire que sa "liste" est en faite un tableau de pointeur... Rien à voir avec une liste chainée donc.

[sovitec]

Si tu utilise le C++ tu peux faire cela en 3 lignes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
vector<double>vec;
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

Cette méthode renvoie une liste triée, ce qui ne semble pas être le but, d'après l'exemple.

[sovitec]

Je parle bien de listes (chaînées comme en C), pas des tableaux pour lesquels les algo de tri arrivent à être en n Log(n).

Comme dit David.V j'ai dit liste, mais ça peut être n'importe quelle structure de données, la plus adaptée au problème. D'ailleurs je ne suis pas sûr qu'il existe d'algorithme de tri en O(n.log(n)) sur les tableaux non plus.

[ben04]

Si tu utilise le C++ tu peux faire cela en 3 lignes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
vector<double>vec;
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

Cette méthode renvoie une liste triée, ce qui ne semble pas être le but, d'après l'exemple.

Moi je ne pense pas qu'on pourrai supprimer les doubles plus efficace sans trier. S'il veut garder l'order relative alors il faut un algorithme specific mais moi j'ai compri que l'order final n'est pas important, donc il peut aussi être trié. sort a une complexité de O(N log N) et unique de O(N) donc la complexité totale est de O(N log N + N) donc à peu près O(N log N).

progman a déjà proposé l'algorithme de base et la seule façon de l'optimiser que je vois et d'utiliser la recherche binaire, cependant celle ci a besoin d'une liste triée.

Sans stocker de relations complexes entre les données on ne peut à mon avis pas faire mieu que O(N^2) et la façon la plus simple de stocker ces informations est de trier donc à mon avis il est plus vite de trier.

Si je n'avais pas l'STL à ma disposition j'utiliserais une algorithme heapsort modifié. Quand je sortirais les valeurs du heap j'y ajouterais un test s'il y a déjà une valeur équivalente, comme la liste est triée ça ce fait en temps constant et donc la complexité de l'algorithme reste O(N log N).