임의의 배열에서 주어진 랭크의 원소를 찾는 것

Question

내가하고있는 것은 퀵 소트 알고리즘을 사용하여, 필자의 피벗 엘리먼트 (항상 배열의 첫 번째 엘리먼트가 정렬 된 배열의 적당한 위치에 위치하게된다. .? 구현 한 알고리즘은 Quickselect라고

public static int arbitrary(int a[],int x,int y,int rank)//x and y are first and last indecies of the array 
{ 
    int j=y,temp; 
    if(x<y) 
    { 
     for(int i=y;i>x;i--) 
     { 
      if(a[i]>a[x]) 
      { 
       temp=a[i]; 
       a[i]=a[j]; 
       a[j]=temp; 
       j--; 
      } 
     } 
     temp=a[x]; 
     a[x]=a[j]; 
     a[j]=temp; 
     //System.out.println("j is "+j); 
     if(j==rank) 
      return a[j]; 
     else if(rank<j) 
      return arbitrary(a,x,j-1,rank); 
     else 
      return arbitrary(a,j+1,y,rank); 
    } 
    else 
     return 0; 

} 

Answer 1

: 나는 주어진 순위에있는 요소를 배치하지 않는 때까지 다시는이 메서드를 호출하고 거기 더 나은 솔루션을 여기에

은 내 코드입니다. 무작위 피벗을 선택하고 O (n²) 시간의 복잡도로 최악의 상황을 없애기 만하면됩니다.
예상 런타임이 이제 약 3.4n + o(n)입니다.
Quickselect는 아마도 성능과 단순성 사이에서 가장 좋은 절충안 일 것입니다.

더욱 향상된 피벗 선택 전략을 사용하면 1.5n + o(n) 예상 시간이 (Floyd-Rivest Algorithm)이됩니다.

재미있는 사실 : 결정 성 알고리즘을 사용하면 2n 이상으로 나아갈 수 없습니다. 예를 들어 BFPRT은 중간 값을 선택하려면 약 2.95n이 필요합니다.