Tri Quickstart : tri rapide

[Cynthia67]

Bonjour à tous !

J'essaye d'effectuer en langage C, un tri Quicksort : Tri Rapide

Au départ j'ai 8 chiffres : 5,3,9,1,8,6,4,7

Le pivot est determiné de façon : prend le premier élément du groupe à trier

Donc ici le pivot sera 5

Tout ce qui est inférieur à 5 je veux l'insérer dans un nouveau tableau, et de même pour tout ce qui est supérieur à 5

Ce qui donne un tableau t1 avec 3,1,4 (donc 3 sera le pivot) et un tableau t2 avec 9,8,6,7 (donc le pivot sera 9)

Et ainsi de suite ..

Jusqu'a ce qu'il y'est que un seul chiffre dans un tableau ou plus aucun dans ce cas la on s'arrête.

J'ai commencé à écrire le code mais je suis bloquée concernant le pivot quand il est égal à 5, je n'arrive pas à créer les deux tableaux t1 et t2

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
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
 
int main()
{
    int n,p,i,j,u,t[7],t1[2],t2[3];
    j=-1;
    i=1;
    u=-1;
    t[0]=5;
    t[1]=3;
    t[2]=9;
    t[3]=1;
    t[4]=8;
    t[5]=6;
    t[6]=4;
    t[7]=7;
 
      for(i=0;i<8;i++)
                    {
                        printf("\t%d",t[i]);
                    }
 
 
    p=t[0];
 
    printf("\nLe pivot est %d\n",p);
 
 
    if(p>t[i])
    {
                 i=i+1;
                 j=j+1;
                 t1[j]=t[i];
                 printf("%d",t[j]);
    }
    else
    {
     i=i+1;
     u=u+1;
     t2[u]=t[i];
     printf("\t%d",t[u]);
    }
 
 
getchar();
getchar();
getchar();
}

Pouvez vous m'aider et me dire ou sa ne va pas ?
Merci à vous

PS: Je suis une débutante qui vient juste de débuter le langage C (c'est mon premier langage , je suis actuellement en 1ère année de BTS Informatique)

[Sve@r]

Bonjour
Ca ne va pas à plusieurs niveaux

• Tout d'abord, tu veux remplir t1 et t2 avec des nombres issus de t donc l'étape de base sera de parcourir chaque élément de t (donc une boucle) et si t[x] est inférieur à p tu le copies dans t1[y] et tu incrémentes y et si t[x] est supérieur à p tu le copies dans t2[z] et tu incrémentes z. Là, tu compares juste t[i] (que vaut i à cet endroit ?) avec p. Qu'en est-il des autres t[x] ???
  
• Ensuite tu dis "et ainsi de suite" ce qui signifie qu'il faut recommencer le même algorithme avec t1 et t2 (qui seront eux-mêmes dispatchés dans t11 et t12 pour t1 et t21 et t22 pour t2). Et si t11 a plus d'un élément il faut encore recommencer et, là vraiment, ainsi de suite. Et qu'en sera-t-il si on veut trier non pas un tableau de 8 éléments mais de 500 ???

Donc ce genre de mécanisme est tout à fait possible en C mais il implique de connaitre la notion de récursivité. Cette notion part du principe qu'une fonction se déroule dans un espace local et isolé avec ses propres variables. Il lui est donc tout à fait possible d'appeler un clone d'elle-même et attendre le retour de ce clone. Ledit clone effectuant ses propres calculs avec sa propre zone de travail elle-aussi isolée et si besoin, pouvant lui-aussi appeler un autre clone de lui-même et attendre son résultat.
Une fois que le clone le plus bas se termine, il renvoie son résultat à son appelant qui peut donc terminer son travail et renvoyer le résultat à son propre appelant et, là encore, ainsi de suite.
Exemple de récursivité: la factorielle

Code c :

1
2
3
4
5
unsigned long fact(unsigned short n)
{
    if (n < 2) return 1;
    return n * fact(n - 1);
}

Donc fact(5) cherchera à calculer 5 * fact(4) et attendra le retour de fact(4) pour finir. Mais fact(4) cherchera à calculer 4 * fact(3) qui, lui, cherchera 3 * fact(2) qui cherchera 2 * fact(1).
fact(1) étant prévu par le test (qu'on appelle "test de fin de récursivité") renvoie 1 donc fact(2) calcule 2 * 1 et renvoie 2 à fact(3) qui calcule 3 * 2 et renvoie 6 à fact(4) qui calcule 4 * 6 et renvoie 24 à fact(5) qui calcule 5 * 24 et renvoie au final 120 à l'appelant initial.

Donc avec un tel exemple c'est une notion pas compliquée à percevoir mais il faut la connaitre avant d'essayer de l'appliquer sur un algorithme plus complexe...

PS: un tableau peut se remplir à la déclaration en écrivant: int t[]={5,3,9,1,8,6,4,7}.
PS2: la récursivité est un faux ami car s'il simplifie l'écriture de résolution en profondeur, il est super gourmand pour le système (qui doit, quand un clone est appelé, se charger d'empiler le travail en cours pour instancier un nouveau travail). Donc chaque fois qu'on a un problème à résoudre, on essaye d'abord de voir si on peut s'en passer avant de se résoudre à y recourir
Exemple de factorielle sans récursivité

Code c :

1
2
3
4
5
6
7
unsigned long fact(unsigned short n)
{
    unsigned long res;
    if (n < 2) return 1;
    for (res=1; n > 1; res*=n, n--);
    return res;
}

Toutefois même si le tri rapide est possible sans récursivité, c'est super compliqué à faire ainsi (en fait on simule la récursivité en mettant nous-même en mémoire la position en cours dans le tableau pour travailler sur des parties plus petites) donc dans ton cas, la récursivité reste obligatoire. Cependant je ne sais pas s'il s'agit d'un TP à faire ou si c'est juste pour le plaisir mais dans les deux cas tu as beaucoup de lacunes à combler (comme simplement le fait de savoir parcourir un tableau quand il faut traiter ses éléments).
Plus d'infos sur ton algo ici => http://fr.wikipedia.org/wiki/Tri_rapide

[Cynthia67]

Bonsoir,

Tout d'abord merci pour votre réponse très complète et qui m'a été très utile.

Cet exercice, je l'effectue de ma propre volonté pour m’entraîner à programmer en C.

Mais en effet, je me rend compte qu'au final me manque plusieurs notions avant de pouvoir l'aborder.

J'ai bien compris tout ce que vous m'avez expliquer, et je vais étudier sa de très près.

Concernant la récursivité, on l'a pas encore traité en cours. Mais je vais y travailler dessus.

Avant de repasser à cet exercice, je pense qu'il serait plus judicieux que je fasse d'autres exercices, étape par étape, jusqu'à que j'ai toutes les connaissances pour cet exercice la.

Merci pour le lien concernant l'algorithme du tri rapide, maintenant j'ai vraiment bien compris le procédé du tri rapide. Me reste plus qu'à le transcrire en C !

Je vous remercie pour toute votre aide.
Bonne soirée à vous