하나의 루프로 퀵 포트를 작성하십시오.

Question

오빠는 하나의 루프 만 가지고 코드를 최적화하길 원합니다. Quicksort가 하나의 루프와 작업 만 가질 수있는 방법을 알지 못합니다. 학계에 따르면 (또는 내가 공부하고 나는 또한 데이터 구조와 알고리즘 책에 대한 빠른 검사를했다 적어도 퀵 알고리즘

public class QuickSort { 
public static void Quick(int[] target, int lo, int hi) { 
    if (lo >= hi) { 
     return; 
     } 
    Random numberGenerator = new Random(); 
    int pivot = numberGenerator.nextInt(hi-lo)+lo; 
    int pivotValue = target[pivot]; 
    target[pivot]=target[hi]; 
    target[hi]=pivotValue; 
    pivot=hi; 
    int counter; 
    for(counter=lo; counter<pivot ; counter++){ 
     while(target[counter]>target[pivot]){ 
      if(pivot-counter==1){ 
       int temp=target[counter]; 
       target[counter]=target[pivot]; 
       target[pivot]=temp; 
       //return; //possibly the problem 
      } 
      else{ 
       int temp1 = target[pivot-1]; 
       int temp2 = target[pivot]; 
       target[pivot]=target[counter]; 
       target[pivot-1]=temp2; 
       target[counter]=temp1; 
       pivot=pivot-1; 
      } 
     } 
    } 
    Quick(target, lo, counter-1); 
    Quick(target, counter, hi); 
} 

public static void main(String[] args) { 
    int sizeOfArray = 10; 
    int numberOfTests = 1000; 

    int numFailed = 0; 
    for (int i = 0; i < numberOfTests; i++) 
    { 
     int[] iNeedSorting = new int[sizeOfArray]; 
     populateArrayWithRandomNums(iNeedSorting); 
     //System.out.printf("Test #%d\n", i); 
     //System.out.printf("Original Array: %s\n", intArrayToString(iNeedSorting)); 
     Quick(iNeedSorting, 0, iNeedSorting.length-1); 

     if (!isSorted(iNeedSorting)) {numFailed++;} 
     //System.out.printf("New Array: %s\n\n", intArrayToString(iNeedSorting)); 
    } 
    System.out.printf("%d test failed\n\n", numFailed); 
} 

}

Answer 1

을 (그는 내부 루프를 제거하기 위해 나에게 말했다)), quicksort는 재귀에 관한 것입니다. 데이터 세트를 분할 (루프가 필요함) 한 다음 왼쪽과 오른쪽을 재귀 적으로 정렬합니다.

Answer 2

퀵 포트는 개념적으로 두 개의 루프, 즉 전체 배열을 반복하는 내부 분할 루프와 재귀를 통해 일반적으로 표현되는 외부 분할 루프입니다. 여기에서는 고전적인 방식으로 분할 된 부분을 가지고 있지만 분할은 약간 복잡합니다.

바깥 쪽 for 루프는 카운터를 왼쪽으로 한 단계 이동합니다 (왼쪽에서 오른쪽으로 배열을 작성한다고 가정). 내부 for 루프는 피벗을 한 단계 오른쪽으로 이동시킵니다 (카운터가 피벗에 거의 도달하여 최종 스왑을 수행하는 특별한 경우 제외). 카운터를 오른쪽으로 되돌리거나 피벗을 왼쪽으로 뒤로 움직이는 것은 없습니다. 따라서 두 개의 루프로 인해 추가 작업을 수행하지 않습니다. 이는 효율성보다는 명확성의 문제입니다.

분할을 쓰는 일반적인 방법은 하나의 루프 대신 두 개의 카운터가있는 단일 루프를 사용하는 것입니다. 하나의 카운터가 사용 된 카운터입니다. 왼쪽의 모든 것이 피벗보다 적습니다. 다른 카운터는 대칭 역할을합니다. 오른쪽의 모든 것이 피벗보다 큽니다. 루프 본문은 다음을 수행합니다

• 모두 target[left_counter] 경우

  및 target[right_counter] 아웃 오브 장소를 교환된다 이 후에 target[left_counter]과 target[right_counter]이 어레이의 원하는면에 있으므로 left_counter을 증가시키고 right_counter을 감소시킵니다.

• 그렇지 않은 경우 : target[left_counter]이 원하는면에 있으면 left_counter; target[right_counter]이 원하는면에 있으면 right_counter을 감소시킵니다.

카운터가 교차하면 루프가 종료됩니다. 카운터의 적어도 하나가 각 반복에서 이동하기 때문에 결국 종료됩니다.