자바 코드에서 힙 정렬?

Question

저는 재미있는 일을 위해 자바에서 몇 가지 시도를하고 있습니다.

먼저 최대 힙을 만듭니다. 그런 다음 첫 번째 요소를 max 변수로 가져 와서 정렬되지 않은 배열의 마지막 항목을 힙 상단으로 이동 한 다음 아래로 누릅니다.

나는 21 개의 요소를 시험해 보았고, 70 %의 시간이 걸렸다. 문제가 누구인지를 궁금해하고있다.

감사합니다.

public class HeapSort extends Sort{ 
    public int sort(int arr[]) { 
     for (int i = 1; i < arr.length; i++) { 
      // add to heap 
      int p = i; 
      int pp = p /2 ; 
      while (p > 0 && arr[pp] < arr[p]) { 
       swap(arr, p, pp); 
       p = pp; 
       pp = p/2; 
      } 

     } 

     for (int i = arr.length - 1; i > 0; i--) { 
      swap(arr, 0, i); 
      int p = 0; 
      int child1 = (p << 1) + 1; 
      int child2 = (p << 1) + 2; 

      while (child2 < i || child1 < i) { 
       if (child1 >= i) { 
        if (arr[p] < arr[child2]) { 
         swap(arr, p, child2); 
         p = child2; 
        } else { 
         break; 
        } 
       } else if (child2 >= i) { 
        if (arr[p] < arr[child1]) { 
         swap(arr, p, child1); 
         p = child1; 
        } else { 
         break; 
        } 
       } else { 
        int minIdx = arr[child1] < arr[child2] ? child1 : child2; 
        int maxIdx = child1 == minIdx ? child2 : child1; 

        if (arr[p] < arr[maxIdx]) { 
         swap(arr, p, maxIdx); 
         p = maxIdx; 
        } else { 

         break; 

        } 
       } 
       child1 = (p << 1) + 1; 
       child2 = (p << 1) + 2; 
      } 

     } 
     return 0; 

    } 
    void swap(int arr[], int idx1, int idx2) { 
     int tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp; 
    } 
    public String toString() { 
     return "HeapSort"; 
    } 

} 

Answer 1

힙 정렬의 첫 번째 단계에서는 올바르게 힙을 빌드하지 않습니다. 0부터 시작하는 배열에서 2를 나누기 전에 1을 빼야합니다.

public class HeapSort extends Sort{ 
    public int sort(int arr[]) { 
     for (int i = 1; i < arr.length; i++) { // add to heap 
     int p = i; 
     // int pp = p /2 ; <======= Problem! 
     int pp = (p-1)/2; 
     while (p > 0 && arr[pp] < arr[p]) { 
      swap(arr, p, pp); p = pp; 
      // pp = p/2; // <=====Problem! 
      pp = (p-1) /2; 

}