Java 빠른 정렬을 어떻게 수정합니까?

Question

문제는 네바다 재귀입니다. 나도 모르겠다. 재귀를 어떻게 끝낼 수 있을까? 재밌지 만, arraylist (mergedArray)를 출력하면, 반복 후에 정렬되지만 함수는 결코 멈추지 않습니다. 오류 메시지가 : "javaapplication9.QuickSort.simple_quick_sort (QuickSort.java:40)에서"

아래 코드 : 물론

public ArrayList<Integer> simple_quick_sort(ArrayList<Integer> arr) { 
    ArrayList<Integer> mergedArray = new ArrayList<Integer>(); 
    ArrayList<Integer> left = new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 
    if (arr.size() <= 1) { 
     return arr; 
    } 
    else { 
     int pivot = arr.get(0); 
     for (int i = 0; i < arr.size(); i++) { 
      if (arr.get(i) < pivot) { 
       left.add(arr.get(i)); 
      } 
      else { 
       right.add(arr.get(i)); 
      } 
     } 

    } 
    mergedArray.addAll(left); 
    mergedArray.addAll(right); 
    simple_quick_sort(mergedArray); 
    return mergedArray; 
} 

Answer 1

public ArrayList<Integer> simple_quick_sort(ArrayList<Integer> arr) { 

    if (arr.size() <= 1) { 
    return arr; 
    } 
    else { 
    ArrayList<Integer> mergedArray = new ArrayList<Integer>(); 
    ArrayList<Integer> left = new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 
    int pivot = arr.get(0); 
    for (int i = 0; i < arr.size(); i++) { 
     if (arr.get(i) < pivot) { 
      left.add(arr.get(i)); 
      left = simple_quick_sort(left); 
     } 
     else { 
      right.add(arr.get(i)); 
      right = simple_quick_sort(right); 
     } 
    } 

    } 
    mergedArray.addAll(left); 
    mergedArray.addAll(right); 
} 

, 복사 작업은 정렬 작업을 수행 할 수 있고 복사 작업 및 저장 할당이 필요하지 않기 때문에 좋은 quicksort의 기본 개념과 상반됩니다.

Answer 2

죄송하지만 quicksort의 전체 구현이 잘못된 것입니다. 또한 재귀 함수 내부에서 루프를 사용하면 재귀를 사용하면 얻을 수있는 이점이 없어집니다. 이 루프를 구현하려면 코드를 더 단순하게 만들기 위해 다른 루프 안에 중첩시켜야합니다 (재귀만큼 효율적이지는 않습니다). 당신이 함수의 반환 값을 사용하지 않는

simple_quick_sort(mergedArray); 
return mergedArray; 

을 쓸 때 :이 프로그램을 계속하려면

, 다음과 같은 변경을 시도합니다. 함수를 호출하고 반환 된 값으로 아무 일도하지 않고 있습니다. 이 코드가 작동하기 전에 수정해야 할 사항이 더있을 수 있습니다. 빠른 정렬 및 재귀에 대해 자세히 알아 보려면이 페이지를 찾으십시오. http://www.geeksforgeeks.org/quick-sort/

이 정보가 도움이되기를 바랍니다.