Ubuntu-fr

temps

[résolu] tri dans un tableau en langage C

Bonjours,
J'ai un tableau en langage C composé de valeurs croissantes selon des lois variables.
Je cherche à retrouver la position dans ce tableau de mesures faites à l'aide d'appareils sans précision.
En d'autres mots, retrouver dans quel intervalle du tableau se retrouve des valeurs aléatoires.
En exemple :

int tab[5] = {1,7,30,32,100};

quand j'ai la mesure qui égal 10 , je sais que je suis en troisème position dans le tableau soit x =2
ou quand j'ai la mesure qui égal 40 , je sais que je suis en cinquième position dans le tableau soit x =4

J'imagine faire une boucle qui décrémente la position dans le tableau, jusqu'au moment ou la valeur mesurée soit supérieur à la valeur dans le tableau. Est-ce que quelqu'un a une meilleur idée ou sait comment écrire la mienne ?
Cordialement

Dernière modification par temps (Le 22/01/2012, à 18:24)

---

Parce que l'USB bootable est le support des systèmes experts,
Parce que l'USB bootable contient sa propre image au démarrage.
L'USB bootable permet de créer un monde à la dimension de son imagination
https://www.letime.net

temps

Re : [résolu] tri dans un tableau en langage C

Je vais essayer en nommant ola1 la valeur mesurée

int ola =5;
while (ola1 > tab[ola]) {
      ola--;

}

et je pense retrouver à la fin la position dans le tableau dans ola
Le temps de finir le reste du code et je vous dis, si ça a marché.

---

Parce que l'USB bootable est le support des systèmes experts,
Parce que l'USB bootable contient sa propre image au démarrage.
L'USB bootable permet de créer un monde à la dimension de son imagination
https://www.letime.net

Rolinh

Re : [résolu] tri dans un tableau en langage C

J'imagine faire une boucle qui décrémente la position dans le tableau, jusqu'au moment ou la valeur mesurée soit supérieur à la valeur dans le tableau.

Ça peut marcher mais un algorithme glouton n'est certainement pas la meilleure solution en terme de complexité.
Tu peux déjà avoir un meilleur résultat pour une implémentation simple en adaptant un quicksort à ton cas:
Si ton tableau fait une taille de n, alors tu prends tab[n/2] comme première valeur et tu regardes si la valeur et plus grande ou petite que celle que tu as. Ensuite, tu te concentre sur la partie voulu et tu répètes le processus. Enfin, c'est un description grossière mais ça devrait t'aider à implémenter quelque chose de simple et relativement efficace.

Bousky

Re : [résolu] tri dans un tableau en langage C

Tu peux déjà avoir un meilleur résultat pour une implémentation simple en adaptant un quicksort à ton cas:
Si ton tableau fait une taille de n, alors tu prends tab[n/2] comme première valeur et tu regardes si la valeur et plus grande ou petite que celle que tu as. Ensuite, tu te concentre sur la partie voulu et tu répètes le processus. Enfin, c'est un description grossière mais ça devrait t'aider à implémenter quelque chose de simple et relativement efficace.

C'est pas un quicksort (qui est une méthode de tri) mais une dichotomie.

int ola =5;
while (ola1 > tab[ola]) {
      ola--;

}

for (ola = 5 ; ola1 > tab[ola] ; ola--) ;

Dernière modification par Bousky (Le 22/01/2012, à 18:08)

---

Linux qui plante complètement ? Plus rien ne répond ? On peut toujours le redémarrer proprement :
Alt + SysRq + REISUB (Retourne En Islande Sur Un Bateau !)

Rolinh

Re : [résolu] tri dans un tableau en langage C

Je sais bien que ce n'est pas un quicksort puisque je l'ai dit moi-même... D'ailleurs, le but ici n'est pas de trier. Mais le quicksort procède sur le même principe.

temps

Re : [résolu] tri dans un tableau en langage C

Merci pour les réponses.
Je poste en résolu.
Les trois techniques fonctionnent.
Cordialement

---

Parce que l'USB bootable est le support des systèmes experts,
Parce que l'USB bootable contient sa propre image au démarrage.
L'USB bootable permet de créer un monde à la dimension de son imagination
https://www.letime.net

Bousky

Re : [résolu] tri dans un tableau en langage C

Mais le quicksort procède sur le même principe.

Non. Le quicksort utilise la technique dite "diviser pour reinger". La dichotomie est une méthode de résolution d'équations par approximations successives.

---

Linux qui plante complètement ? Plus rien ne répond ? On peut toujours le redémarrer proprement :
Alt + SysRq + REISUB (Retourne En Islande Sur Un Bateau !)

Rolinh

Re : [résolu] tri dans un tableau en langage C

Oui, c'est vrai. J'avais pensé au quicksort à cause de la recherche du pivot.