Java: Quicksort flag [Résolu]

Signaler
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
-
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
-
Bonjour, j'ai essayé de mettre en place quicksort, mais le résultat que j'obtiens n'est pas celui escompté. Si je veux trier cette liste par exemple:[12, 0, 14, 0, 13], j'obtiens [12, 0, 0, 13, 14].

J'ai le code suivant:
package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import static com.sun.tools.javac.jvm.ByteCodes.swap;
import static java.util.Collections.swap;

public class Quicksort {

    int x;
    int y;

    public Quicksort(int x, int y){
        this.x = x;
        this.y = y;
    }

    public int getX(){
        return x;
    }

    public int getY(){
        return y;
    }

    public static Quicksort partition(ArrayList<Integer> sequence, int gauche, int droite) {

        int milieu = gauche, pivot = sequence.get(droite);
        int i = gauche - 1;

        while (milieu <= droite) {
            if (sequence.get(milieu) < pivot) {
                swap(sequence, gauche, milieu);
                gauche = gauche + 1;
                milieu = milieu + 1;
            } else if (sequence.get(milieu) > pivot) {
                swap(sequence, milieu, droite);
                droite = droite - 1;
            } else {
                milieu = milieu + 1;
            }
        }

        return new Quicksort(gauche - 1, milieu);
    }



    public static ArrayList quicksort(ArrayList<Integer> sequence, int gauche, int droite){

        if (gauche >= droite){
            return sequence; // ?
        }

        if (gauche-droite == 1){
            if (sequence.get(gauche) < sequence.get(droite)){
                swap(sequence, gauche, droite);
            }
            return sequence; //???????
        }

        Quicksort pivot;
        pivot = partition(sequence, gauche, droite);

        quicksort(sequence, pivot.getY(), droite);
        quicksort(sequence, gauche, pivot.getX());

    return sequence;

    }




    /**
     * test quicksort
     */
    public static void main(String[] args) {

        ArrayList sample3 = new ArrayList();
        sample3 = Sequence.sequenceGenerated(5);
        System.out.println("la liste générée est: " + sample3);
        sample3 = Quicksort.quicksort(sample3, 1, sample3.size()-1);
        System.out.println("quicksort: " + sample3 );

    }

}



j'ai mis également des printf avant chaque appel récursif à quicksort, mais il n'y avait qu'un seul changement:
[10, 7, 4, 3, 12]
[10, 7, 4, 3, 12]
[10, 3, 4, 7, 12]
[10, 3, 4, 7, 12]
[10, 3, 4, 7, 12]
[10, 3, 4, 7, 12]


j'ai l'impression que l'appel récursif ne marche qu'une fois, à moins que je me sois trompée dans l'un des return de quicksort ?

2 réponses

Messages postés
16337
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
16 mai 2021
2 829
Bonjour,

Le problème est plus simple que ça : dans ton main tu fais
quicksort(sample3, 1, sample3.size()-1);
en commençant donc le tri avec l'indice 1 au lieu de 0, donc la liste est bien triée, sauf le premier élément qui est ignoré, il suffit donc de faire
quicksort(sample3, 0, sample3.size()-1);
pour bien tout trier.

Remarques :
  • Pour éviter ce genre d'erreur, tu devrais faire une méthode quicksort(sample3) qui initialise à 0 et à size-1 les valeurs de gauche et droite.
  • ArrayList<E> est un type paramétré, tu devrais donc toujours mettre un paramètre, donc ArrayList<Integer> oui. Mais ArrayList tout court, non, car c'est équivalent à ArrayList<Object> et ce n'est pas ce que tu veux.
  • Tu devrais supprimer l'import static de ByteCodes.swap, ça n'a rien à faire là
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
Effectivement, ça venait bien de là. Merci.
J'ai également pris tes conseils en compte afin de faire des changements sur monde. Merci une fois de plus!