problème tri ascii

Bonsoir,
Je rencontre un petit problème pour trier une liste de char ** dans l'ordre ascii :
En fait aucuns problèmes quand tous les mots commencent par une lettre différente par contre quand plusieurs mots possèdent des lettres communes impossible de trier.
Le truc c'est que je ne vois pas quelle algo appliqué , surtout que je dois utilisé ce tri d'une facon un peu particulière..
pour expliqué rapidement mon code, voila ce que je fais : je prends le premier char * comme base et compare le caractère avec les autres char * , si ces caractères sont différents je return la différence entre ces deux caractères (cela me permet de trier ces char * pour qu'il s'affiche parfaitement dans l'ordre ducoup le char * de base est à 0, ceux que je print avant sont un nb négatif et ceux que j'affiche après sont positif).
Voilà ce que je viens de vous décrire brièvement réussit à classer dans l'ordre en comparant tout. Malheureusement je dois trier parfaitement ces mots pour pouvoir les envoyer en tant que nb (ceux dont je vous ai parlé juste au dessus) qui me serviront de compteur pour afficher chaque char * mots par mots.
je pense qu'il y a plus simple , je crois que je me prends un peu la tete ..
Bref je vous poste le code . Si vous avez une toute petite idée d'algo (ou une question sur pourquoi je fais cela , ect) dites moi.

Merci pour votre aide :)

commencez à la fin PAR DEBUG_TETRI !

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

int funct(t_tetris_game *game, int x) { int j; char *word_base;   word_base = game->tetrim->list[0]->name; j = 0; if (word_base[j] == game->tetrim->list[x]->name[j] && word_base != game->tetrim->list[x]->name) return (game->tetrim->list[x]->name[j] - word_base[j]); else if (word_base[j] != game->tetrim->list[x]->name[j]) return (game->tetrim->list[x]->name[j] - word_base[j]); j++; return (0); }     int check(t_tetris_game *game, int *tab, int var) { int x;   x = 0; while (x != game->tetrim->nb) { if (tab[x] == var) { my_putstr("Tetriminos : Name "); parcing_name(game, x); my_putchar('\n'); return (x); } x++; } return (0); }     int *find_diff(t_tetris_game *game) { int x; int *tab;   x = 0; my_putstr("\n"); tab = malloc(sizeof(int) * (game->tetrim->nb * 4096)); while (x != game->tetrim->nb) { tab[x] = funct(game, x); x++; } return (tab); }     void debug_tetri(t_tetris_game *game) { int *tab; int x; int y; int var;   x = 0; y = 0; tab = find_diff(game); while (x != game->tetrim->nb) { var = tab[0]; while (y != game->tetrim->nb) { if (var > tab[y] && tab[y] != 100) var = tab[y]; if (y == game->tetrim->nb-1) tab[check(game, tab, var)] = 100; y++; } y = 0; x++; } free (tab); }

---

En gros, ce que tu cherches à faire, c'est ramener tes chaînes à des nombres qui suivent le même ordre que l'ordre lexicographique des chaînes?

Franchement, je ne vois pas d'autre méthode fiable pour ça que de trier les chaînes dans un tableau (avec qsort(), par exemple) puis récupérer les indexes de ce tableau pour les associer à chaque chaîne.

Déjà qu'on a une bonne réputation de m*rde sur le net ça va pas aider si tu viens et poses un pavé incompréhensible cher camarade !
De plus sois tu fournis toute la doc utilisée dans ton code soit tu fais un échantillon pour qu'on se retrouve pas avec des trucs du genre :

Code:

---

game->tetrim->list[x]->name[j]

---

Du coup si j'ai bien compris tu as déjà effectuer un tri en fonction de la première lettre, du genre :
abc, cde, bcd -> abc, bcd, cde

Pour l'algo tu peux partir très simple en parcourant ton tableau et comparant mots par mots avec un fonction qui te dit quel mot est plus "grand" que l'autre

Quelque chose de ce genre :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

typedef struct s_mot { char *str; bool done; } t_mot;   void tri_tab(t_mot *tab) { int i; t_mot *stock;   while (all_done(tab) != true) { i = 0; stock = NULL; while (tab[i] != NULL) { if (stock == NULL && tab[i].done == false) stock = &(tab[i]); else if (plus_grand(stock->str, tab[i].str) == true) stock = &(tab[i]); i++; } printf("%s\n", stock->str); stock->done = true; } }

---

ahah désolé pour le gros bloc c'est vrai que c'est un peu lourd.
Bref merci pour vos conseils , j'ai totalement revu mon code et j'ai fait un tri en boucle , je m'explique :
je tri d'abord les mots deux par deux ensuite je passe au suivant ect jusqu'a arriver à la fin . Lorsque je suis à la fin j'ai une fonction qui checke si la liste est bien trié ,si c'est le cas j'ai finis sinon je reprends ma liste et je la retri encore une fois. De ce fait , à un moment la liste est bien trié et je sors de cette boucle .

Merci pour votre aide , Bonne journée !

En gros, un bubble sort en moins bien?

oui une sorte de tri à bulle, mais je vois pas pourquoi c'est moins bien, le tri est bien fait et sans erreurs . à savoir que je n'ai le droit qu'à très peu de fonctions, vu que ca fait partit d'un projet scolaire. si tu as une autre idée de tri , n'hésite pas . Merci

Généralement si je ne peux pas utiliser qsort(), je me contente du tri à bulle "correct", celui qui fait n*(n+1)/2 comparaisons.
Ou quand j'ai besoin d'un tri stable, je fais un tri-fusion qui alterne sur deux buffers (car tenter le tri-fusion in-place change sa complexité de linéarithmique à quadratique).

exact je ne pouvais pas utiliser qsort. Je n'ai pas l'habitude de faire régulièrement des algo de tri en c mais le dernier que j'ai utilisé pour le tri que je veux effectuer ici est plus ou moins "correct" . Après je me rends compte que j'aurais pu l'améliorer mais bon mon projet est terminé et l'algo n'a pas posé de problème .

Pourquoi trié avec n*(n+1)/2 comparaisons? le nombre de comparaison ne peut être définit par rapport au nombre d'élément à trié, si?

Citation:

---

Envoyé par awesomeman

Pourquoi trier avec n*(n+1)/2 comparaisons? le nombre de comparaisons ne peut être définit par rapport au nombre d'éléments à trier, si?

---

Ben si, c'est précisément comme ça qu'on définit la complexité d'un algorithme de tri (enfin, nombre de comparaisons ou nombre de déplacements/permutations, selon ce qui est le pire):

• Le tri à bulle "correct" est n*(n+1)/2, ce qui donne O(n²) --> complexité quadratique.
• Les algorithmes de tri "efficaces" ont une complexité (moyenne ou "au pire" selon les cas) de O(n*log₂(n)) --> complexité linéarithmique
  
  • Le "tri rapide" (quicksort) possède une complexité moyenne de O(n*log₂(n)) et une complexité au pire de O(n²).
  • Le tri fusion (merge sort) possède une complexité au mieux, moyenne et au pire de O(n*log₂(n)) quand il n'est pas "sur place", mais passe à O(n²) si on tente de le faire "sur place" à cause des déplacements supplémentaires.
    Un de ses avantages est d'être un tri stable, c'est-à-dire que des éléments dont la clé est égale conserveront le même ordre.