Индекс массива вне границ в массиве на основе массива

Question

Я пытаюсь написать массив на основе реализации алгоритма сортировки кучи. Цель состоит в том, чтобы построить кучу в массиве, а затем удалить минимальный элемент в корневом массиве и вернуть его в исходный массив. Это выполняется до тех пор, пока массив не будет отсортирован.

Замена корня должна исходить из последнего элемента массива, который затем удаляется и помещается в корень. Новый корневой элемент по необходимости заменяется одним своим дочерним элементом. Это продолжается до тех пор, пока оно не находится в правильном месте.

Однако я продолжаю получать исключение индекса массива из-за пределов, и я просто не могу найти проблему. Я слишком долго работал над этим.

Я был бы очень признателен, если бы кто-то мог мне помочь.

public class ImprovedHeapSort<T> 
{ 
    /** 
    * @param unsortedArr Array to be sorted 
    * @return sortedArr The sorted array 
    * 
    * Static method which is an improved version of the HeapSort algorithm. The array 
    * is used to create a sorted array, which is treated as a minheap. 
    * 
    * The root is at index 0 and the last element is at index length-1. 
    * Each element is compared to its children, which are at positions 2n+1 and 2(n+1). 
    * Swapping and comparison continues until the root is reached. 
    * 
    * 
    */ 

    public static <T extends Comparable<T>> T[] HeapSort (T[] unsortedArr) 
    { 
     /* 
     * Throw exception if array is empty. 
     */ 
     if (unsortedArr[0] == null) 
     { 
      throw new EmptyCollectionException("Array"); 
     } 

     /* 
     * If array only contains one element. 
     */ 
     if (unsortedArr.length == 1) 
     { 
      return unsortedArr; 
     } 



     T[] heapArr = Arrays.copyOf(unsortedArr, unsortedArr.length); 


     for(int i = 0; i < unsortedArr.length; i++) 
     { 

      heapArr[i] = unsortedArr[i]; 

      /* 
      * Swapping to put element in appropriate location, if necessary. 
      */ 

       int cur = i; 
       T temp = heapArr[i]; 

       /* 
       * Swapping until root isn't reached and the element being added 
       * would no longer be less than its parent. 
       */ 
       while(cur > 0 && temp.compareTo(heapArr[(cur-1)/2]) < 0) 
       { 
        heapArr[cur] = heapArr[(cur-1)/2]; //Swap cur with parent 
        cur = (cur-1)/2;      //Move up to parent 

       } 

       heapArr[cur] = temp;      //Insert at appropriate spot. 

     } 

     /* 
     * Remove the root element from the heap array and add it to unsortedArr 
     * 
     */ 




     for (int y = 0; y < unsortedArr.length; y++) 
     { 
       int count = heapArr.length - (y+1);  //Count decreased after every pass. 
       T rootElem = heapArr[0];    //Store root 
       heapArr[0] = heapArr[heapArr.length- (y+1)]; //Set root to last element. 
       unsortedArr[y] = rootElem;    //Add root to unsortedArr 

       int node = 0; 
       int left = 1; 
       int right = 2; 
       int next; 


       if ((heapArr[left] == null) && (heapArr[right] == null)) 
        next = count-1; 
       else if (heapArr[right] == null) 
        next = left; 
       else if (heapArr[left].compareTo(heapArr[right]) < 0) 
        next = left; 
       else 
        next = right; 

       T temp = heapArr[node]; 


      /* 
      * Swap until appropriate location is found. Least child is shifted up. 
      */ 

      while ((next < count) && 
       (heapArr[next]).compareTo(temp) < 0) 
      { 
       heapArr[node] = heapArr[next]; 
       node = next; 
       left = 2 * node + 1; 
       right = 2 * (node + 1); 

       if ((heapArr[left] == null) && (heapArr[right] == null)) 
        next = count-2; 
       else if (heapArr[right] == null) 
        next = left; 
       else if (heapArr[left].compareTo(heapArr[right]) < 0) 
        next = left; 
       else 
        next = right; 
      } 
      heapArr[node] = temp;  //Insert node at appropriate location 
     } 



     return unsortedArr; 

Answer 1

У вас есть ошибки в вашем коде.

Во-первых, давайте посмотрим здесь:

/* 
    * Throw exception if array is empty. 
    */ 
    if (unsortedArr[0] == null) 
    { 
     throw new EmptyCollectionException("Array"); 
    } 

Этот код не будет на самом деле бросить исключение, если массив пуст. Вместо этого он пытается посмотреть индекс 0, посмотреть, является ли это значение нулевым, и, если это так, выбросить исключение. Поэтому, если вы попытаетесь передать массив размером 0 или пустой массив, вы получите либо ошибку границ, либо исключение с нулевым указателем. Чтобы исправить это, попробуйте переписать его, как

if (unsortedArr == null) { 
    ... 
} 

Вы, вероятно, не хотят, чтобы автоматически неудачу на массиве длины 0. Это совершенно четко определенной как сортировать его: это уже отсортирован!

Кроме того, я не уверен, что вы имели в виду, чтобы сделать здесь, но я почти уверен, что это не то, что вы хотели:

  int node = 0; 
      int left = 1; 
      int right = 2; 
      int next; 


      if ((heapArr[left] == null) && (heapArr[right] == null)) 
       next = count-1; 
      else if (heapArr[right] == null) 
       next = left; 
      else if (heapArr[left].compareTo(heapArr[right]) < 0) 
       next = left; 
      else 
       next = right; 

Обратите внимание, что node, left и right всегда индексы 0, 1 и 2, независимо от того, насколько велик массив. Если вы передадите небольшой массив (скажем, размер 2), это будет считаться с конца.

Идти вперед, смысл в том, что вам нужно научиться отлаживать свои программы немного больше. Исключения, возникающие здесь, когда я запускал код, поменяли меня на линию программы, вызвавшую эту проблему, и оттуда было не слишком сложно понять, где что-то необычное происходит. Надеюсь, это поможет вам в правильном направлении и удачи!