문제

QuickSort를 구현할 때, 당신이해야 할 일 중 하나는 피벗을 선택하는 것입니다. 그러나 아래의 유사 코드를 볼 때 피벗을 어떻게 선택 해야하는지는 확실하지 않습니다. 목록의 첫 번째 요소? 다른 것?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

누군가가 피벗을 선택하는 개념을 파악하고 다른 시나리오가 다른 전략을 요구하는지 여부를 파악할 수 있도록 도와 줄 수 있습니까?

도움이 되었습니까?

해결책

임의의 피벗 선택하면 최악의 O (N을 만날 가능성이 최소화됩니다.2) 성능 (항상 첫 번째 또는 마지막을 선택하면 거의 정렬 된 또는 거의 반대 방향으로 분류 된 데이터에 대한 최악의 성능을 유발할 수 있습니다). 대부분의 경우 중간 요소를 선택하는 것도 허용됩니다.

또한이 직접 구현하는 경우 내내에서 작동하는 알고리즘 버전이 있습니다 (즉, 두 개의 새로운 목록을 작성하지 않고 연결하지 않고 연결합니다).

다른 팁

요구 사항에 따라 다릅니다. 무작위로 피벗을 선택하면 O (n^2) 성능을 생성하는 데이터 세트를 만들기가 더 어려워집니다. '중간-세 번째'(첫 번째, 마지막, 중간)도 문제를 피하는 방법입니다. 그러나 비교의 상대적 성능을 조심하십시오. 비교 비용이 많이 드는 경우 Mo3는 무작위로 (단일 피벗 값)를 선택하는 것보다 더 많은 비교를합니다. 데이터베이스 레코드는 비교 비용이 많이들 수 있습니다.

업데이트 : 댓글을 답으로 끌어 당깁니다.

mdkess 주장 :

'중앙값 3'은 첫 번째 중간 중간이 아닙니다. 세 가지 임의의 인덱스를 선택하고 이것의 중간 값을 취하십시오. 요점은 피벗 선택이 결정적이지 않도록하는 것입니다. 만약 그렇다면 최악의 데이터를 쉽게 생성 할 수 있습니다.

내가 응답 한 다음 :

  • Hoare의 중앙 파티션을 사용한 알고리즘을 찾으십시오 (1997) P Kirschenhofer, H Prodinger, C Martínez는 귀하의 논쟁을지지합니다 ( '세 번째 중앙'은 세 가지 임의의 항목입니다).

  • 다음에 설명 된 기사가 있습니다 portal.acm.org 그것은 Hannu Erkiö의 '3 번 중간 속 작용의 최악의 순열'에 관한 것입니다. Hannu Erkiö, Computer Journal, Vol 27, No 3, 1984에 게시되었습니다. [업데이트 2012-02-26 : 텍스트를 얻었습니다. 기사. 섹션 2 '알고리즘'이 시작됩니다 : 'l : r]의 첫 번째, 중간 및 마지막 요소의 중앙값을 사용함으로써, 대부분의 실제 상황에서 상당히 동일한 크기의 일부로 효율적인 파티션을 달성 할 수 있습니다.'따라서, 그것은 1 차 미만의 MO3 접근법에 대해 논의하고있다.

  • 흥미로운 또 다른 짧은 기사는 MD McIlroy의 것입니다. "QuickSort의 킬러 대적", 소프트웨어 실습 및 경험, Vol. 29 (0), 1–4 (0 1999). 거의 모든 QuickSort가 2 차적으로 행동하게 만드는 방법을 설명합니다.

  • AT & T Bell Labs Tech Journal, 1984 년 10 월 "이론 및 실습은 작업 정렬 루틴의 구성"Hoare가 무작위로 선택된 여러 줄의 중앙값 주위에 파티셔닝을 제안했습니다. Sedgewick [...] 첫 번째 중앙값을 선택할 것을 권장했습니다 [. ..] 마지막 [...] 및 중간 ". 이는 '중앙의 중앙'에 대한 두 기술이 문헌에 알려져 있음을 나타냅니다. (업데이트 2014-11-23 :이 기사는 IEEE XPLORE 또는 와일리 - 회원이 있거나 수수료를 지불 할 준비가 된 경우.)

  • '정렬 기능 엔지니어링' 1993 년 11 월 소프트웨어 실습 및 경험에 발표 된 JL Bentley와 MD McIlroy는 1993 년 11 월에 발표 된 Vol 23 (11)은이 문제에 대한 광범위한 논의를 시작했으며 데이터 세트의 크기에 따라 적응 형 파티션 알고리즘을 선택했습니다. 다양한 접근 방식에 대한 트레이드 오프에 대한 많은 논의가 있습니다.

  • '중앙의 중앙'에 대한 Google 검색은 추가 추적에 효과적입니다.

정보 주셔서 감사합니다; 나는 이전에 결정 론적 '중앙의 중앙'을 만났다.

헤, 나는 방금이 수업을 가르쳤다.

몇 가지 옵션이 있습니다.
단순 : 범위의 첫 번째 또는 마지막 요소를 선택하십시오. (부분적으로 정렬 된 입력에도 불량) 더 나은 : 범위 중간에 항목을 선택하십시오. (부분적으로 정렬 된 입력에 더 나은)

그러나 임의의 요소를 선택하면 크기 N 배열을 크기 1과 N-1의 두 배열로 제대로 분할 할 위험이 없습니다. 당신이 그렇게 자주 그렇게한다면, 당신의 QuickSort는 O (n^2)가 될 위험이 있습니다.

내가 본 한 가지 개선은 선택 중앙값 (첫 번째, 마지막, 중간)입니다. 최악의 경우 여전히 O (n^2)로 갈 수 있지만 확률 적으로 이것은 드문 경우입니다.

대부분의 데이터의 경우 첫 번째 또는 마지막을 선택하면 충분합니다. 그러나 최악의 시나리오에 종종 (부분적으로 정렬 된 입력)에 실행된다면 첫 번째 옵션은 중심 값 (부분적으로 정렬 된 데이터에 대한 통계적으로 좋은 피벗)을 선택하는 것입니다.

여전히 문제가 발생하면 중간 경로로 이동하십시오.

절대로 고정 된 피벗을 선택하지 마십시오. 이것은 알고리즘의 최악의 경우 O (n^2) 런타임을 악용하기 위해 공격 할 수 있습니다. QuickSort의 최악의 런타임은 분할하면 1 개의 요소가 1 개의 배열과 N-1 요소의 하나 배열을 초래할 때 발생합니다. 첫 번째 요소를 파티션으로 선택한다고 가정하십시오. 누군가가 순서가 감소한 알고리즘에 배열을 공급하면 첫 번째 피벗이 가장 큰 것이므로 배열의 다른 모든 것이 왼쪽으로 이동합니다. 그런 다음 재발하면 첫 번째 요소가 다시 가장 큰 요소가 될 것이므로 다시 한 번 모든 것을 왼쪽에 넣습니다.

더 나은 기술은 3 개의 요소를 무작위로 선택하고 중간을 선택하는 3 가지 방법입니다. 당신은 당신이 선택한 요소가 첫 번째 또는 마지막 요소가 아니라 중심 한계 정리에 의해 중간 요소의 분포가 정상이되므로 중간을 향한 경향이 있음을 알고 있습니다. , n lg n 시간).

알고리즘에 대한 O (NLGN) 런타임을 절대적으로 보장하려면 배열의 중앙값을 찾는 5 열 메소드는 O (n) 시간으로 실행됩니다. 즉, 최악의 경우 QuickSort의 재발 방정식이 t (n) = o (n) (중앙값 찾기) + o (n) (파티션) + 2t (n/2) (왼쪽과 오른쪽으로 재발) 마스터 정리에 의해 이것은 O (n lg n)입니다. . 그러나 상수 요인은 거대하고 최악의 사례 성능이 주요 관심사 인 경우 대신 병합 정렬을 사용하여 평균적으로 QuickSort보다 약간 느리고 O (NLGN) 시간을 보장합니다 (그리고 훨씬 더 빠릅니다. 이 절름발이 중앙값 QuickSort보다).

중앙값 알고리즘의 중앙값에 대한 설명

너무 영리하려고 시도하지 말고 피벗 전략을 결합하십시오. 중간에 첫 번째, 마지막 및 임의의 인덱스의 중앙값을 선택하여 3의 중앙값을 임의의 피벗과 결합한 경우, 3 차 중앙값을 보내는 많은 분포에 여전히 취약 해집니다 (따라서 실제로는 더 나쁩니다. 평범한 무작위 피벗)

예를 들어 파이프 오르간 분포 (1,2,3 ... N/2..3,2,1) 먼저 1 일이되고 마지막은 1이면 1보다 큰 숫자가 1보다 큽니다. 첫 번째 또는 마지막) 그리고 당신은 uptreply 균형 불균형 파티션을받습니다.

데이터가 어떻게 정렬되는지에 따라 전적으로 의존합니다. 그것이 의사 랜덤이라고 생각되면 가장 좋은 방법은 무작위 선택을 선택하거나 중간을 선택하는 것입니다.

임의 액세스 가능한 컬렉션 (배열과 같은)을 정렬하는 경우 물리적 중간 항목을 선택하는 것이 가장 좋습니다. 이를 통해 배열이 모두 정렬 된 경우 (또는 거의 정렬 된) 두 파티션이 가깝게 가깝고 최상의 속도를 얻을 수 있습니다.

선형 액세스 (링크리스트와 같은)만으로 무언가를 정렬하는 경우 첫 번째 항목을 선택하는 것이 가장 좋습니다. 그러나 여기서 목록이 이미 정렬 된 경우 나사가 나게됩니다. 한 파티션은 항상 Null이고 다른 파티션은 모든 것이있어 최악의 시간을 생성합니다.

그러나 링크 된 목록의 경우 첫 번째 외에는 아무것도 선택하면 문제가 악화 될 것입니다. 목록에서 중간 항목을 선택하면 각 파티션 단계에서 단계를 밟아야합니다. O (N/2) O (N/2) 작업을 추가하여 LOGN TIMES를 완료했습니다. 그리고 그것은 우리가 시작하기 전에 목록이 얼마나 오래 있는지 알면 일반적으로 우리는 그들을 세기 위해 끝까지 걸어 가야 할 필요가 없습니다. 실제 파티션을 세 번째 시간 : O (2.5n * log n)

QuickSort를 세 부분으로 나누는 것이 더 쉽습니다.

  1. 교환 또는 교환 데이터 요소 기능
  2. 파티션 함수
  3. 파티션 처리

하나의 긴 기능보다 약간 더 비효율적이지만 이해하기 쉽습니다.

코드는 다음과 같습니다.

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

이상적으로는 피벗이 전체 배열에서 중간 값이어야합니다. 이렇게하면 최악의 사례 성능을 얻을 가능성이 줄어 듭니다.

빠른 정렬의 복잡성은 피벗 값 선택에 따라 크게 다릅니다. 예를 들어 항상 첫 번째 요소를 피벗으로 선택하면 알고리즘의 복잡성이 O (N^2)만큼 최악이됩니다. 다음은 피벗 요소를 선택하는 스마트 방법입니다. 1. 배열의 첫 번째, 마지막 요소를 선택하십시오. 2.이 세 숫자를 비교하고 1보다 큰 숫자를 다른 IE 중앙값보다 찾으십시오. 3.이 요소를 피벗 요소로 만듭니다.

이 방법으로 피벗을 선택하면 배열이 거의 절반으로 나뉘어 복잡성이 O로 줄어 듭니다 (nlog (n)).

평균적으로, 3의 중앙값은 작은 n에게 좋습니다. 5의 중앙값은 더 큰 n에게는 조금 더 좋습니다. "3 명의 중앙값 중앙값"인 Ninther는 매우 큰 n에게는 더 좋습니다.

샘플링을할수록 높을수록 N이 증가함에 따라 더 잘 얻을 수 있지만 샘플을 늘리면 개선이 크게 느려집니다. 샘플 샘플링 및 정렬 오버 헤드가 발생합니다.

쉽게 계산할 수 있으므로 중간 지수를 사용하는 것이 좋습니다.

반올림 (Array.length / 2)으로 계산할 수 있습니다.

진정으로 최적화 된 구현에서 피벗을 선택하는 방법은 배열 크기에 따라 달라져야합니다. 큰 배열의 경우 좋은 피벗을 선택하는 데 더 많은 시간을 소비하기 위해 지불합니다. 전체 분석을하지 않으면 "O (log (n)) 요소의 중간에 좋은 시작이라고 생각합니다. 이것은 추가 메모리가 필요하지 않은 추가 보너스가 있습니다. 더 큰 파티션 및 In- 파티셔닝을 배치하면 알고리즘의 거의 모든 단계에서 동일한 O (log (N)) 추가 메모리를 사용합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top