HeapSort code snipplet donnant Index hors exception liée

Question

J'essaie le code suivant pour tas de tri qui donne ArrayIndexOutOfBoundsException exception:

package com.Sorting; 

import java.util.Arrays; 

public class HeapSort { 

    private static int arr[]; 
    private static int l,r,max,hsize; 
    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     int []numbers={55,2,93,1,23,10,66,12,7,54,3}; 
      System.out.println(Arrays.toString(numbers)); 
      HeapSort(numbers); 
      System.out.println(Arrays.toString(numbers)); 
    } 

    private static void HeapSort(int myarr[]) { 
     // TODO Auto-generated method stub 
     arr = myarr; 
     hsize = arr.length - 1; 
     BuildHeap(arr); 
     for(int i = hsize;i>0;i--) 
     { 
      swap(0,i); 
      hsize--; 
      SatisfyHeap(arr,0); 
     }  
     } 

    private static void BuildHeap(int[] arr) { 
     // TODO Auto-generated method stub 
     for(int i = hsize/2; i>=0;i--) 
     { 
      SatisfyHeap(arr, i); 

     } 
    } 

    private static void SatisfyHeap(int[] arr, int i) { 
     // TODO Auto-generated method stub 
     l = 2*i; 
     r = 2*i+1; 
     if(l<=hsize && arr[l]>arr[i]) 
    // if(arr[l]>arr[i] && l<=hsize ) 
     { 
      max = l; 
     } 
     else 
      max = i; 
     if(r<=hsize && arr[r]>arr[max]) 
     { 
      max = r; 
     } 

     if(max!=i) 
     { 
      swap(i,max); 
      SatisfyHeap(arr, max); 
     } 

    } 

    private static void swap(int i, int max) { 
     // TODO Auto-generated method stub 
     int temp = arr[i]; 
     arr[i] = arr[max]; 
     arr[max] = temp;  
    } 
} 

Le code ci-dessus ne donne aucune erreur si j'échange seulement les expressions utilisées sur le côté gauche et le côté droit dans l'instruction if de la méthode SatisfyHeap. c'est-à-dire que vous pouvez essayer de commenter la troisième ligne de la méthode SatisfyHeap et décommenter la quatrième ligne. S'il vous plaît, aidez à comprendre cette magie.

Answer 1

Réponse courte

La magie est appelée "short-circuit evaluation" et il a été conçu speciifcally pour les cas comme celui-ci.

réponse plus longue

En Java et beaucoup d'autres langues logicallly Code

if (condition1 && condition2) { 
    do something 
} 

est équivalent à

if (condition1) { 
    if (condition2) { 
     do something 
    } 
} 

par "équivalent" ici, je veux dire que si condition2 est quelque chose à être calculé, il ne sera pas calculé si condition1 arrive à être false. Ceci est également correct du point de vue de la logique booléenne. Cette astuce est utile à deux égards. Tout d'abord, il améliore les performances en ignorant l'évaluation calculation2. Deuxièmement, il est utile dans des cas tels que le vôtre condition1 est une "condition de garde" pour condition2.

Un autre exemple est fonction isEmptyString qui est mis en œuvre par de nombreux développeurs Java de manière suivante

public static boolean isEmptyString(String s) { 
    return (string == null) || (string.length() == 0); 
} 

Sans logique à court circuting, cette expression soulèverait un NullPointerException si s se trouve être nulle.

Votre cas particulier (Pourquoi ArrayIndexOutOfBoundsException du tout?)

Un autre point de votre question pourrait être: « Comment il arrive qu'il y ait ArrayIndexOutOfBoundsException du tout? ». Pour répondre à cette question, considérons le cas où le tout premier élément est réellement le plus grand dans le tas et nous devrions le déplacer vers la dernière couche de l'arbre. Ce mouvement vers le bas est implémenté par votre SatisfyHeap. Alors supposons maintenant que nous avons fait un dernier échange qui a déplacé le plus gros élément vers le bas. Maintenant que max a été changé, nous allons faire un autre appel récursif et dans cet appel i > arr.length/2 alors l = 2*i > arr.length et ainsi l'exception se produit.

Side note, je dirais que si vous pré-allouer arr être plus grand que la taille réelle du tas de stockage hsize indépendamment de arr.length est une mauvaise idée qui rend le code plus difficile à comprendre.

Answer 2

Après vous donne une erreur

if(arr[l]>arr[i] && l<=hsize )

parce l est supérieure à la taille du tableau et que vous essayez d'obtenir l'élément de tableau en passant l qui est hors des limites du tableau.

Après travaille pour vous

if(l<=hsize && arr[l]>arr[i])

parce que dans la condition if, la première chose qui est évalué est l'expression l<=hsize. Puisque l est supérieur à hsize, l'expression est évaluée à false. Comme les deux clauses de votre prédicat if sont jointes à un opérateur &&, conformément aux règles de court-circuit, l'expression dans la deuxième clause n'est même pas évaluée, ce qui vous évite d'accéder au tableau avec un index hors limite. Par conséquent, vous n'obtenez aucune erreur.