Quicksort Algorithm throws StackOverflowException

Question

숙제를 위해 QuickSort 알고리즘 구현을 작성하고이를 사용하여 임의의 순서로 100k 숫자 목록을 정렬해야합니다.

과제의 첫 번째 부분에서는 피벗 요소로 배열의 첫 번째 항목을 사용해야합니다. 이것은 실제로 정렬 된 목록을 반환합니다. 그러나 할당의 두 번째 부분에 대해서는 StackOverflowException을 발생시키는 마지막 항목을 피벗으로 사용해야합니다. 내가 8 개 레코드의 더 작은 콜렉션에서 시도하면 제대로 작동한다. 나는 내 코드를보고 있었지만 실수를 저지르고있는 곳을 알아낼 수는 없다. 어떤 도움이라도 대단히 감사하겠습니다. 내 코드는 다음과 같습니다 :

public class QuickSort { 

    private QuickSortStrategyEnum quickSortStrategy; 

    public QuickSort(QuickSortStrategyEnum quickSortStrategy) { 

     this.quickSortStrategy = quickSortStrategy; 
    } 

    public List<Integer> sortIntegerArray(List<Integer> arrayList, int left, int right) { 

     if (left >= right) { 
      return arrayList; 
     } 

     int i = partition(arrayList, left, right); 

     if (i <= right) { 

      int pivotNew = partition(arrayList, i, right); 
      int pivotIndex = arrayList.indexOf(pivotNew); 

      arrayList = sortIntegerArray(arrayList, left , pivotIndex - 1); 
      arrayList = sortIntegerArray(arrayList, pivotIndex + 1, right); 
     } 

     return arrayList; 
    } 

    private int partition(List<Integer> arrayList, int left, int right) { 

     int pivot = getPivot(arrayList, left, right); 
     int i = left + 1; 

     for (int j = i; j <= right; j++) { 

      if (arrayList.get(j) < pivot) { 

       Collections.swap(arrayList, j, i); 
       i++; 
      } 
     } 

     Collections.swap(arrayList, left, i - 1); 
     return i; 
    } 

    private int getPivot(List<Integer> arrayList, int left, int right) { 

     int pivot = 0; 

     switch (quickSortStrategy) { 

      case FIRST: 
      pivot = arrayList.get(left); 
      break; 

      case LAST: 
      pivot = arrayList.get(right); 
      break; 
     } 
     return pivot; 
    } 

} 

Answer 1

David Harkness가 지적한 사실과 함께 파티션 논리에 문제가 있습니다. 이것을 시도해보십시오. (David Harkness가 지적한 것을 제거한 후)

private int partition(List<Integer> arrayList, int left, int right) { 

    int pivot = getPivot(arrayList, left, right); 
    int i = left - 1; 

    for (int j = left; j < right; j++) { 
     if (arrayList.get(j) <= pivot) { 
      i++; 
      Collections.swap(arrayList, j, i); 
     } 
    } 

    Collections.swap(arrayList, i+1, right); 
    return i+1; 
} 

피벗이 마지막 요소 인 경우에 작동합니다. 첫 번째 요소가 아닙니다.

읽고, 종이 작업을 이해하고, 마른 것을 실행하고, 의사 코드를 작성한 다음 Eclipse에 인사하십시오. 일을 빨리 서두르지 마라.

Answer 2

힌트 : right == left + 1 일 경우 어떻게됩니까? 무엇 partition 반환에

int pivotNew = partition(arrayList, i, right); 
int pivotIndex = arrayList.indexOf(pivotNew); 

봐하고 그 결과를 사용하는 방법과 비교 :

Answer 3

이 두 라인은 비린내가 보인다.