퀵소트 : 거의 정렬되었지만별로는 아닙니다. 뭐가 문제 야?

Question

다음은 코드입니다. 출력은 거의 거의 올바르게 정렬 된 배열이지만, 여러 요소가 잘못되어 있습니다. 오류를 발견 할 수있는 사람은 누구입니까?

나는 swap과 quicksort 방법이 정확하다는 것을 확신하지만, 여기에 모든 방법을 게시하고있다.

package quicksort; 
import java.util.Random; 
import java.util.Arrays; 

public class QuickSort { 

/** 
* @param args the command line arguments 
*/ 

private static int[] u; 

public static void main(String[] args) { 

    u = makeArray(100); 
    System.out.println(Arrays.toString(u)); 

    quicksort(0, u.length - 1); 
    System.out.println(Arrays.toString(u)); 

} 

public static int[] makeArray(int n) { 

    int[] a = new int[n]; 
    int j; 
    Random r = new Random(); 

    for (int i = 0; i < n; i++) { 
     j = (r.nextInt(100) + 1); 
     a[i] = j; 
    } 

    return a; 
} 

public static int partition(int left, int right, int pivot) { 

    int p = pivot; // pivot 
    int lPt = left - 1; 
    int rPt = right + 1; 

    while (true) { 

     while ((lPt < right) && (u[++lPt] < p)); 

     while ((rPt > left) && (u[--rPt] > p)); 

     if (lPt >= rPt) { 
      break; 
     } else { 

      swap(lPt, rPt); 
      System.out.println("Swapping " + lPt + " " + rPt); 

     } 


    } 

    return lPt; 
} 

public static void swap (int a, int b) {   
    int temp = u[a]; 
    u[a] = u[b]; 
    u[b] = temp; 
} 

public static void quicksort(int l, int r) { 

    if (r - l <= 0) { 
     return; 

    } else { 

     int part = partition(l, r, u[l]); 

     quicksort (l, part - 1); 
     quicksort (part + 1, r); 

    } 
} 

}

Answer 1

문제는 파티션 방법에 있습니다. 피벗 요소가 스왑의 끝 부분에서 올바른 위치에 있지 않습니다. 오히려 피벗의 가치보다, 피벗 요소의 위치를 ​​전달할 수 있도록 나는 방법 서명을 변경했습니다, 그래서 퀵()에 당신은 지금 작성합니다

int part = partition(l, r, l); 

을 피벗의 몸에서 메서드를 사용하여 피벗 요소를 섹션의 끝으로 바꿨습니다 (오른쪽으로 스와핑하여). 그래서 우리는 스왑을 가지고이 요소를 무시하고, 나는 rPT의 초기화에서 "+ 1"을 없앴습니다. 그런 다음 피벗 요소를 제자리로 이동하기 위해 while 루프 뒤의 명령문을 추가했습니다. 이 세 가지 변화와 함께, 방법은 지금과 같다 : 이러한 변경으로

public static int partition(int left, int right, int pivotPosition) { 

    int p = u[pivotPosition]; // pivot 

    // Move pivot to the end 
    swap(pivotPosition, right); 

    int lPt = left - 1; 
    int rPt = right; 

    while (true) { 

     while ((lPt < right) && (u[++lPt] < p)); 

     while ((rPt > left) && (u[--rPt] > p)); 

     if (lPt >= rPt) { 
      break; 
     } else { 

      swap(lPt, rPt); 
      System.out.println("Swapping " + lPt + " " + rPt); 
     } 

    } 

    // Put pivot in its place 
    swap(lPt, right); 

    return lPt; 
} 

, 코드가 나를 위해 작동합니다.

Answer 2

당신은 피벗 요소보다 큰 왼쪽 목록에서 값을 찾은 다음 우리가 값을 교환 피벗 요소 다음 작 오른쪽 목록에서 값을 찾을 수있다.

package quicksort; 
import java.util.Random; 
import java.util.Arrays; 

public class QuickSort { 
    /** 
    * @param args the command line arguments 
    */ 
    private static int[] u; 

    public static void main(String[] args) { 

     u = makeArray(10); 
     System.out.println(Arrays.toString(u)); 

     quicksort(0, u.length - 1); 
     System.out.println(Arrays.toString(u)); 

    } 

    public static int[] makeArray(int n) { 
     int[] a = new int[n]; 
     int j; 
     Random r = new Random(); 
     for (int i = 0; i < n; i++) { 
      j = (r.nextInt(100) + 1); 
      a[i] = j; 
     } 
     return a; 
    } 

    private static void quicksort(int low, int high) { 
     int i = low, j = high; 
     int pivot = u[low]; 
     while (i <= j) { 
      while (u[i] < pivot) { 
       i++; 
      } 
      while (u[j] > pivot) { 
       j--; 
      } 
      if (i <= j) { 
       exchange(i, j); 
       i++; 
       j--; 
      } 
     } 
     if (low < j) { 
      quicksort(low, j); // note here 
     } 
     if (i < high) { 
      quicksort(i, high); // note here 
     } 
    } 

    private static void exchange(int i, int j) { 
     int temp = u[i]; 
     u[i] = u[j]; 
     u[j] = temp; 
    } 
}