Vient d'apprendre et d'implémenter le schéma de partitionnement de Hoare pour le tri rapide en Java. Fonctionne aussi bien que lol annoncé, mais j'ai juste quelques questions à ce sujet. J'ai essayé de rechercher une vidéo youtube dessus, mais je n'en ai trouvé aucune qui me l'expliquait bien.

Je pense que dans la partition actuelle de Hoare, le pivot est censé être le premier élément, mais j'ai utilisé l'élément du milieu comme pivot au cas où le tableau serait déjà trié. J'ai écrit quelques commentaires dans le code sur ce que je suis un peu confus. Principalement pourquoi i et j sont mis à 1 inférieur et 1 supérieur à low et high s'ils sont simplement incrémentés et décrémentés avant de vérifier le tableau.

public static void quicksort(int [] arr, int low, int high){
        if(low < high){
            int pivot = partition(arr, low, high);
            quicksort(arr, low, pivot);
            quicksort(arr, pivot+1, high);
        }
    }

        public static int partition(int [] arr, int low, int high){
        int i = low-1; //Why not just set i to low? 
        int j = high+1;// Why do you have to set it to high+1 and not high?
        int mid = low + (high-low)/2;
        int pivot = arr[mid];
        
        while(true){
            do {
                i++;
            } while(arr[i] < pivot);
            do {
                j--;
            } while(arr[j] > pivot); 
            
            if( i >= j) return j;
            swap(arr, i, j);
           
        } 
    }

Mais lorsque je change le code de partitionnement pour ce qu'il est ci-dessous, il finit par fonctionner apparemment pour toujours avec des tableaux de plus grande taille, par exemple avec 17 numéros différents, et je dois l'arrêter manuellement. La chose étrange est que ce code fonctionnera pour un tableau de plus petite taille, par exemple avec 6 nombres, mais pas pour des tableaux de plus grande taille. Je ne peux pas parcourir manuellement le code des tableaux avec beaucoup de nombres car je me perds dans les appels de récursivité.

 public static int partition(int [] arr, int low, int high){
        int i = low; 
        int j = high;
        int mid = low + (high-low)/2;
        int pivot = arr[mid];
        
        while(true){
           while(arr[i] < pivot){
               i++;
           }
           while(arr[j] > pivot){
               j--;
           } 
            
            if( i >= j) return j;
            swap(arr, i, j);
            
        } 
    }

J'espère donc que quelqu'un pourra me dire pourquoi celui du haut fonctionne parfaitement et celui du bas non.

0
cris 27 août 2020 à 23:17

2 réponses

Meilleure réponse

L'important ici est que après un échange de a[i] et a[j], ces deux index doivent d'abord être incrémentés / décrémentés avant de faire la comparaison suivante avec le pivot.

Cela ne se produit pas dans votre deuxième version.

Ceci est cependant nécessaire. Imaginez qu'à un moment donné, a[i] et a[j] sont tous deux égaux à la valeur pivot (car il y a des valeurs en double). Ensuite, l'échange se produira, mais cela ne changera rien. Pire encore, dans votre deuxième version, la comparaison avec la valeur du pivot montrera à nouveau qu'ils sont égaux, et nous sommes revenus là où nous étions: cela devient une boucle infinie. Si toutefois il y a au moins une exécution de i++ et j-- après un échange, une telle boucle infinie ne se produira pas.

Une façon de s'assurer que i++ et j-- se produisent au moins une fois après un échange, est de les placer dans une boucle do { } while. Et une fois que vous avez fait ce choix, il est évident que la première fois i doit être une de moins que low et j une de plus que high.

2
trincot 27 août 2020 à 20:37

Je voudrais expliquer ce processus à ma façon, car je suis tombé qu'il est parfois mal compris.

Le but de la partition est de réorganiser le tableau afin qu'il soit divisé en deux sous-tableaux avec tous les éléments de la partie «gauche» pas plus grands que ceux de la «partie droite». Attention, le prédicat n'est "pas plus grand", car "plus petit" peut être impossible à réaliser, si tous les éléments sont égaux.

Il est également important de comprendre qu'après le processus de partition, aucun sous-tableau ne peut être vide, sinon il n'y a pas de progression et l'algorithme (Quicksort) peut effectuer une boucle sans fin.

Maintenant, le processus est le suivant:

  • choisissez une valeur pivot. Je dis valeur plutôt que élément car en fait n'importe quelle valeur peut le faire, tant que la valeur n'est pas en dehors de la plage des éléments (cela aurait pour conséquence qu'un sous-tableau soit vide );

  • scannez le tableau de gauche à droite jusqu'à ce que vous trouviez un grand élément à gauche et un petit élément à droite (par rapport à la valeur du pivot *) ou jusqu'à ce que les "pointeurs" se rencontrent;

  • si aucune paire inversée n'a pu être trouvée, vous avez terminé; sinon, permutez ces deux éléments et continuez avec le sous-tableau inclus.

En pratique, la valeur pivot est considérée comme la valeur de un élément dans le tableau (qui garantit la condition de non-vide). Idéalement, prendre la médiane serait optimal, mais obtenir la médiane est coûteux. Une heuristique courante est la «médiane de trois». La moyenne pourrait faire aussi bien, mais elle a un coût linéaire et ne fonctionne que pour les valeurs numériques.

Les scans sont effectués les uns après les autres. L'analyse de gauche terminera certainement à l'intérieur du tableau. Le pointeur droit peut ne pas dépasser celui de gauche.

À des fins de débogage, vous pouvez instrumenter le code afin qu'il vérifie si les pointeurs gauche et droit ne se croisent pas, si un échange est effectué avec des pointeurs inégaux et si les sous-tableaux ne sont pas vides à la fin.


* Que faire lorsqu'un élément a la valeur du pivot est une subtilité: si vous sautez de tels éléments pour éviter qu'ils soient échangés, il y a un risque d'atteindre la fin du tableau lorsque tous les éléments sont égaux.

0
Yves Daoust 28 août 2020 à 08:21