IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

[QSort]Problème de compréhension


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Profil pro
    chomeur
    Inscrit en
    Août 2006
    Messages
    343
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : chomeur

    Informations forums :
    Inscription : Août 2006
    Messages : 343
    Par défaut [QSort]Problème de compréhension
    Bonjour,

    J'aimerai comprendre l'algorithme du Qsort. Pour ce faire, j'ai regardé sur wikipédia et pour être plus précis sur le morceau de code quasiment tout en bas en C, que voici :
    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    void quickSort(int tableau[], int p, int r) {
            int q;
            if(p<r)
            {
                    q = partitionner(tableau, p, r);
                    quickSort(tableau, p, q);
                    quickSort(tableau, q+1, r);
            }
    }
     
    int partitionner(int tableau[], int p, int r) {
            int pivot = tableau[p], i = p-1, j = r+1;
            int temp;
            while(1) 
           {
                    do
                            j--;
                    while(tableau[j] > pivot);
                    do
                            i++;
                    while(tableau[i] < pivot);
                    if(i<j) 
                    {
                            temp = tableau[i];
                            tableau[i] = tableau[j];
                            tableau[j] = temp;
                    }
                    else
                            return j;
            }
            return j;
    }
    A sa simple vue je ne comprends pas le While(1)... Est ce que quelqu'un pourrait m'expliquer? car j'ai l'impression que ça va boucler à l'infini.

    De plus j'ai voulu le faire à la main... pour être sur de bien comprendre le raisonnement.
    J'ai pris le tableau : tab=[1;5;6;3]. et j'ai "executé" avec quicksort(tab,1,4).
    j'ai bien une incohérence dans le morceau de code partitionner.
    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    pivot=tab(1)=1
    i=0, j=5
    tab(4)>pivot? Non
    tab(3)>pivot ? non
    tab(2)>pivot? Non
    tab(1)>pivot ? non
    tab(0)>pivot ben... je ne sais pas...

    Si quelqu'un pouvait m'éclairer sur ces quelques points.

  2. #2
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    dans cette boucle, les deux premières boucles do/while vont rechercher les valeurs du tableau qui enfreignent la condition de valeur par rapport au pivot. Le but de la fonction partition étant de mettre toutes les valeurs inférieures à gauche du pivot et toutes les valeurs supérieures à droite.
    Donc lorsque l'on sort de ces boucles, c'est soit pour inverser deux valeurs mal placée, donc on les inverse, soit parce que les drapeaux i et j ont dépassé le pivot et donc enfreignent la condition sur le pivot. Donc dans ce cas on est dans le cas else return.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Membre éclairé
    Profil pro
    chomeur
    Inscrit en
    Août 2006
    Messages
    343
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : chomeur

    Informations forums :
    Inscription : Août 2006
    Messages : 343
    Par défaut
    alors dans mon exemple on doit retourner j=0?

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par EvaristeGaloisBis Voir le message
    alors dans mon exemple on doit retourner j=0?
    oui, dans ce cas très particulier, le partitionnement n'a pas modifié le tableau de départ et le pivot est en position 0:

    [1;5;6;3] --(partition)--> gauche=[1] et droite=[5;6;3]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. [Débutant] problème de compréhension
    Par Sylvester dans le forum Général Java
    Réponses: 18
    Dernier message: 21/07/2005, 09h16
  2. Réponses: 5
    Dernier message: 11/04/2005, 10h21
  3. [C#] Problème de compréhension de System.Convert ET Provider
    Par papouAlain dans le forum Windows Forms
    Réponses: 5
    Dernier message: 18/11/2004, 21h52
  4. onclipevent (problème de compréhension)
    Par stephane eyskens dans le forum Flash
    Réponses: 8
    Dernier message: 24/09/2003, 15h09
  5. Problème de compréhension des ensembles
    Par Cornell dans le forum Langage
    Réponses: 6
    Dernier message: 07/02/2003, 22h07

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo