Quicksort : 피벗 선택

Quicksort : 피벗 선택

---

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 ² ) 성능 이 발생할 가능성이 최소화 됩니다 (항상 첫 번째 또는 마지막을 선택하면 거의 정렬되거나 거의 역 정렬 된 데이터에 대해 최악의 성능이 발생 함). 대부분의 경우 중간 요소를 선택하는 것도 허용됩니다.

또한이를 직접 구현하는 경우 제자리에서 작동하는 알고리즘 버전이 있습니다 (즉, 두 개의 새 목록을 만든 다음 연결하지 않고).

---

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

---

업데이트 : 댓글을 답변으로 가져옵니다.

mdkess는 다음과 같이 주장했습니다.

'중앙값 3'은 첫 번째 마지막 중간이 아닙니다. 세 개의 임의 인덱스를 선택하고이 값의 중간 값을 가져옵니다. 요점은 피벗 선택이 결정적이지 않은지 확인하는 것입니다. 그렇다면 최악의 경우 데이터가 매우 쉽게 생성 될 수 있습니다.

내가 응답 한 내용 :

• P Kirschenhofer, H Prodinger, C Martínez 의 Hoare의 Find Algorithm With Median-Of-Three Partition (1997)은 귀하의 경합을 지원합니다 ( 'median-of-three'는 무작위 항목 3 개임).

• The Computer Journal, Vol 27, No 3, 1984에 게재 된 Hannu Erkiö의 'The Worst Case Permutation for Median-of-Three Quicksort'에 대한 기사가 portal.acm.org에 설명되어 있습니다 . [Update 2012-02- 26 : 기사 의 텍스트를 얻었습니다 . 섹션 2 '알고리즘'은 다음과 같이 시작합니다. ' A [L : R]의 첫 번째, 중간 및 마지막 요소의 중앙값을 사용하면 대부분의 실제 상황에서 상당히 동일한 크기의 부분으로 효율적으로 분할 할 수 있습니다. '따라서 첫 번째 중간 마지막 Mo3 접근 방식을 논의하고 있습니다.]

• 흥미로운 또 다른 짧은 기사는 MD McIlroy의 "A Killer Adversary for Quicksort" 이며 Software-Practice and Experience, Vol. 29 (0), 1–4 (0 1999). 거의 모든 Quicksort가 2 차적으로 작동하도록하는 방법을 설명합니다.

• AT & T Bell Labs Tech Journal, 1984 년 10 월 "작업 정렬 루틴 구축의 이론 및 실습"은 "Hoare는 무작위로 선택된 여러 라인의 중앙값을 기준으로 분할을 제안했습니다. Sedgewick [...]은 첫 번째 [. ..] 마지막 [...] 및 중간 ". 이것은 '중위수'에 대한 두 가지 기술이 문헌에 알려져 있음을 나타냅니다. (2014-11-23 업데이트 :이 기사는 IEEE Xplore 또는 Wiley 에서 제공되는 것으로 보입니다. 멤버십이 있거나 수수료를 지불 할 준비가되어있는 경우)

• 1993 년 11 월 Software Practice and Experience Vol 23 (11)에 게시 된 JL Bentley와 MD McIlroy의 'Engineering a Sort Function' 은이 문제에 대한 광범위한 논의를 다루고, 부분적으로는 적응 형 파티셔닝 알고리즘을 선택했습니다. 데이터 세트의 크기. 다양한 접근 방식에 대한 장단점에 대해 많은 논의가 있습니다.

• '중앙값 3'에 대한 Google 검색은 추가 추적에 매우 적합합니다.

정보 주셔서 감사합니다; 나는 결정 론적 '3 중위수'를 전에 만났었다.

---

헤, 방금이 수업을 가르쳤어요.

몇 가지 옵션이 있습니다.
단순 : 범위의 첫 번째 또는 마지막 요소를 선택합니다. (부분적으로 정렬 된 입력에 좋지 않음) 더 좋음 : 범위 중간에있는 항목을 선택합니다. (부분적으로 정렬 된 입력에 더 적합)

그러나 임의의 요소를 선택하면 크기 n의 배열을 크기 1과 n-1의 두 배열로 잘못 분할 할 위험이 있습니다. 그렇게 자주하면 퀵소트가 O (n ^ 2)가 될 위험이 있습니다.

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

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

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

---

고정 피벗을 선택하지 마십시오. 알고리즘의 최악의 경우 O (n ^ 2) 런타임을 악용하기 위해 공격을받을 수 있습니다. Quicksort의 최악의 경우 런타임은 파티셔닝 결과 1 요소의 배열 하나와 n-1 요소의 배열 하나가 될 때 발생합니다. 파티션으로 첫 번째 요소를 선택한다고 가정합니다. 누군가가 내림차순으로 알고리즘에 배열을 공급하면 첫 번째 피벗이 가장 크므로 배열의 다른 모든 항목이 왼쪽으로 이동합니다. 그런 다음 재귀하면 첫 번째 요소가 다시 가장 커지므로 다시 한 번 모든 요소를 ​​왼쪽에 배치하는 식입니다.

더 나은 기술은 3 개의 요소를 무작위로 선택하고 중간을 선택하는 3 중위수 방법입니다. 선택한 요소가 첫 번째 또는 마지막 요소가 아니라는 것을 알고 있습니다. 중앙 극한 정리에 따르면 중간 요소의 분포는 정상이 될 것입니다. 즉, 중간으로 향하는 경향이 있음을 의미합니다. , n lg n 시간).

If you absolutely want to guarantee O(nlgn) runtime for the algorithm, the columns-of-5 method for finding the median of an array runs in O(n) time, which means that the recurrence equation for quicksort in the worst case will be T(n) = O(n) (find the median) + O(n) (partition) + 2T(n/2) (recurse left and right.) By the Master Theorem, this is O(n lg n). However, the constant factor will be huge, and if worst case performance is your primary concern, use a merge sort instead, which is only a little bit slower than quicksort on average, and guarantees O(nlgn) time (and will be much faster than this lame median quicksort).

Explanation of the Median of Medians Algorithm

---

Don't try and get too clever and combine pivoting strategies. If you combined median of 3 with random pivot by picking the median of the first, last and a random index in the middle, then you'll still be vulnerable to many of the distributions which send median of 3 quadratic (so its actually worse than plain random pivot)

E.g a pipe organ distribution (1,2,3...N/2..3,2,1) first and last will both be 1 and the random index will be some number greater than 1, taking the median gives 1 (either first or last) and you get an extermely unbalanced partitioning.

---

It is entirely dependent on how your data is sorted to begin with. If you think it will be pseudo-random then your best bet is to either pick a random selection or choose the middle.

---

If you are sorting a random-accessible collection (like an array), it's general best to pick the physical middle item. With this, if the array is all ready sorted (or nearly sorted), the two partitions will be close to even, and you'll get the best speed.

If you are sorting something with only linear access (like a linked-list), then it's best to choose the first item, because it's the fastest item to access. Here, however,if the list is already sorted, you're screwed -- one partition will always be null, and the other have everything, producing the worst time.

However, for a linked-list, picking anything besides the first, will just make matters worse. It pick the middle item in a listed-list, you'd have to step through it on each partition step -- adding a O(N/2) operation which is done logN times making total time O(1.5 N *log N) and that's if we know how long the list is before we start -- usually we don't so we'd have to step all the way through to count them, then step half-way through to find the middle, then step through a third time to do the actual partition: O(2.5N * log N)

---

It is easier to break the quicksort into three sections doing this

1. Exchange or swap data element function
2. The partition function
3. Processing the partitions

It is only slightly more inefficent than one long function but is alot easier to understand.

Code follows:

/* 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
  };
};

---

Ideally the pivot should be the middle value in the entire array. This will reduce the chances of getting worst case performance.

---

Quick sort's complexity varies greatly with the selection of pivot value. for example if you always choose first element as an pivot, algorithm's complexity becomes as worst as O(n^2). here is an smart method to choose pivot element- 1. choose the first, mid, last element of the array. 2. compare these three numbers and find the number which is greater than one and smaller than other i.e. median. 3. make this element as pivot element.

choosing the pivot by this method splits the array in nearly two half and hence the complexity reduces to O(nlog(n)).

---

On the average, Median of 3 is good for small n. Median of 5 is a bit better for larger n. The ninther, which is the "median of three medians of three" is even better for very large n.

The higher you go with sampling the better you get as n increases, but the improvement dramatically slows down as you increase the samples. And you incur the overhead of sampling and sorting samples.

---

I recommend using the middle index, as it can be calculated easily.

You can calculate it by rounding (array.length / 2).

---

In a truly optimized implementation, the method for choosing pivot should depend on the array size - for a large array, it pays off to spend more time choosing a good pivot. Without doing a full analysis, I would guess "middle of O(log(n)) elements" is a good start, and this has the added bonus of not requiring any extra memory: Using tail-call on the larger partition and in-place partitioning, we use the same O(log(n)) extra memory at almost every stage of the algorithm.

참고URL : https://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot