Quicksort supprimer certaines des conditions

Question

public static void quickSort(Integer[] arr, int low, int high) 
    { 
     //check for empty or null array 
     if (arr == null || arr.length == 0){ 
      return; 
     } 

     if (low >= high){ 
      return; 
     } 

     //Get the pivot element from the middle of the list 
     int middle = low + (high - low)/2; 
     int pivot = arr[middle]; 

     // make left < pivot and right > pivot 
     int i = low, j = high; 
     while (i <= j) 
     { 
      //Check until all values on left side array are lower than pivot 
      while (arr[i] < pivot) 
      { 
       i++; 
      } 
      //Check until all values on left side array are greater than pivot 
      while (arr[j] > pivot) 
      { 
       j--; 
      } 
      //Now compare values from both side of lists to see if they need swapping 
      //After swapping move the iterator on both lists 
      //NUMBER (1) 
      if (i <= j) 
      { 
       swap (arr, i, j); 
       i++; 
       j--; 
      } 
     } 
     //Do same operation as above recursively to sort two sub arrays 
     //NUMBER (2) 
     if (low < j){ 
      quickSort(arr, low, j); 
     } 
     //NUMBER (3) 
     if (high > i){ 
      quickSort(arr, i, high); 
     } 
    } 

Je suis un débutant dans l'algorithme quicksort. Quelqu'un peut-il me dire quel est le but des conditions à savoir si le nombre (1), si le nombre (2) et si le nombre (3) dans l'algorithme quicksort ci-dessus?

Pour le nombre (1), la condition que je ressens n'est pas nécessaire car je serai certainement plus petit ou égal à j et donc le swap devrait simplement s'exécuter.

Pour le nombre (2) et le nombre (3), c'est une explication similaire. S'il vous plaît me corriger si je me trompe vous remercie

Answer 1

Numéro 1 - les deux anciens for boucles vérifient juste pour les bons éléments d'échange (du côté gauche et à droite) alors quand les positions d'index i et j sont calculés, cette condition voir s'ils sont dans une position qui doit être permutée (parce que l'un est implicitement supérieur à l'autre).

Les numéros 2 et 3 font partie de l'algorithme "Diviser pour régner", cette partie ne fait que diviser le tableau en deux parties plus petites.

Jetez un oeil à this (source wikipedia)