QuickSort pour tableau de char

Version imprimable

Bonjour/Bonsoir a tous,

Voila mon problème, je veu appliquer le quicksort a un tableau de char, le code de la fonction est ok, mais pas le passage du tableau. Pourtant je pense que c'est comme cela que l'ont passe en paramètre un tableau de char. Voici le code :

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 void tri_Qksort(int m,int n,char * szStr[]);
 int partition(int m,int n,char * szStr[]);
 
int main(int argc, char *argv[])
{
  char szStr[7][200] = {{"un"},{"trois"},{"quatre"},{"cinq"},{"AAA"},{"B"},{"b"}};
  int iDeb=0,iFin = 7,i;
 
  /*Affichage tableau non trié*/
  for(i = 0;i<7;++i){
        printf("%s ",szStr[i]);
  }
 
  /* Appel du tri. */
  tri_Qksort(iDeb,iFin,szStr);
 
  printf("\n");
 
  /* Affichage tableau trié. */
  for(i = 0;i<7;++i){
        printf("%s ",szStr[i]);
  }
 
  getch();	
  return 0;
}
 
 int partition(int m,int n,char * szStr[])
 {
     char pivot[200];
     strcpy(pivot,szStr[m]);
     int i = m-1;
     int j = n+1; // indice final du pivot
 
     while (1)
     {
       do
      {
         j--;
       } while (strcmp(szStr[j],pivot)<0);
       do
      {
         i++;
       }while (strcmp(szStr[i],pivot)>0);
       if (i<j)
      {
         char temp[200];
         strcpy(temp,szStr[i]);
         strcpy(szStr[i],szStr[j]);
         strcpy(szStr[j],temp);
       }
      else
      {
         return j;
      }
     }
 }
 void tri_Qksort(int m,int n,char * szStr[]) {
   if (m<n) {
     int p = partition(m,n,szStr);
     tri_Qksort(m,p,szStr);
     tri_Qksort(p+1,n,szStr);
   }
 }

Merci d'avance pour votre aide.

24/10/2006, 18h28
elghadi_mohamed
bonjour :D

essaye de faire:
Code:

1 2 void tri_Qksort(int m,int n,char **szStr)
;)
24/10/2006, 18h34
deck_bsd

Cela revient au mm ;) Et puis je l'avai dja esseye avt :D
24/10/2006, 18h47
elghadi_mohamed

Citation:

Envoyé par deck_bsd

Bonjour/Bonsoir a tous,

.... Pourtant je pense que c'est comme cela que l'ont passe en paramètre un tableau de char.

vaudrais ecrire tableau de string!!!

:chin:
24/10/2006, 18h51
deck_bsd

Mdr oui, mais bon on se comprend. Mais la n'est pas le problème :s
24/10/2006, 19h41
Jean-Marc.Bourguet

szStr est un tableau de tableau de char.
Ta fonction prend un pointeur vers pointeur sur char.
C'est normal que tu ne puisses pas lui passer szStr.

Possiblité 1: un modifie le type de szStr pour un faire un tableau de pointeurs sur char. Elle pourra alors être convertie implicitement en un pointeur vers pointeur vers char.

Code:

char* szStr[] = { "un", ... };

Possibilité 2: tu modifies ta fonction pour qu'elle prenne un pointeur vers tableau de char. szStr pourra alors être convertie implicitement en un pointeur vers tableau de char.

Code:

void tri_Qksort(int m,int n,char (*szStr)[200]);
24/10/2006, 19h43
diogene
Code:

1 2 3 4 5 char szStr[7][200] = {{"un"},{"trois"},{"quatre"},{"cinq"},{"AAA"},{"B"},{"b"}}; .... tri_Qksort(iDeb,iFin,szStr); ..... void tri_Qksort(int m,int n,char * szStr[])....
Le type de l'argument est incorrect : ce n'est pas un tableau de pointeur sur char. Le type écrit ici est équivalent à char** szStr
Si on veut conserver la nature bidimensionnelle de l'argument, szStr est un pointeur sur un tableau de 200 char

Code:

void tri_Qksort(int m,int n,char (* szStr)[200])....

Le 200 est obligatoire pour que le compilateur puisse interpréter correctement le code du style

Code:

strcpy(pivot,szStr[m]);

Une autre alternative est de la déclarer comme char*, ce qu'il est puisqu'il est l'adresse d'un char.

Code:

void tri_Qksort(int m,int n,char * szStr)....

Dans ce cas, le calcul du début des éléments du tableau est de la responsabilité du programmeur :

Code:

strcpy(pivot,szStr +m*200);
24/10/2006, 19h53
Emmanuel Delahaye

Citation:

Envoyé par deck_bsd

Voila mon problème, je veu appliquer le quicksort a un tableau de char, le code de la fonction est ok, mais pas le passage du tableau. Pourtant je pense que c'est comme cela que l'ont passe en paramètre un tableau de char. Voici le code :

Si le but est simplement de trier, pourquoi tu n'utilises pas qsort() ? C'st fait pour ça. Il y a juste à fournir une fonction de comparaison basée sur strcmp()...

Ca se fait en 5 lignes de code, appel compris...

Si c'est un exercice d'implémentation de quicksort, c'est aure chose...
24/10/2006, 19h53
deck_bsd

J'avai déjà esseye certaine soluce que vous venez de me dire, mais le problème est tjrs là et il persiste. :s je ne comprend vraiment pas :(
24/10/2006, 19h59
deck_bsd

Yop Emmanuel Delahaye

Non cela n'ai en rien un exercice, enfin si, pour mon savoir personnel lol. Ben qsort ok je veu bien, mais j'apprend rien. Ici aparement le code fonctionne, c'est le passage du tableau qui ne va pas :( .
24/10/2006, 20h11
diogene

Si tu remplace partout dans les en-tête de fonction tes

Code:

char * szStr[]

par

Code:

char (* szStr)[200]

, ca marche!
24/10/2006, 20h26
deck_bsd

Oui effect , cela fonctionne, hum now c'est mon tri qui va pas didjou.
24/10/2006, 20h44
Jean-Marc.Bourguet

Il faut te décider: est-ce que tu travailles avec des intervalles semi-ouverts (l'indice de fin ne fait pas partie de l'intervalle) comme de coutume en C, ou bien avec des intervalles fermés (l'indice de fin fait partie de l'intervalle). Dans le code ci-dessus, c'est parfois l'un, parfois l'autre.
24/10/2006, 20h50
deck_bsd

intervalles fermé .