Quick sort code:

void qsort(int l,int r) { int i,j; int t,x; i=l; j=r; x=A[(l+r)/2]; do{ while(A[i]<x) i++; while(A[j]>x) j--; if(i<=j) { t=A[i]; A[i]=A[j]; A[j]=t;i++;j--;} }while(i<=j); if(l<j) qsort(l,j); if(i<r) qsort(i,r); }

Question: what is a pivot. Is it the same as the median?

How to find the median? pivot = a [(l + (rl) / 2)]; Is this also a median?

Why is the separating element sometimes chosen randomly, sometimes they take the median (which I don’t know how to find)?

Why sometimes after finding this middle element it turns out that the large middle elements are on the right and the smaller ones on the left? In general - confused. Wirth is incomprehensibly written.

  Что такое медиана из трёх ключей ?

    2 answers 2

    This is not a “median”, but the element by which partitioning of the elements of the array into two groups is performed. For the algorithm to work perfectly as a pivot element for each subarray, you need to take its exact median. But we do not know the median of the subarray while the algorithm is running. And finding the exact median takes time. We do not want to spend time searching for the exact median - in general, it will be irrational.

    Therefore, instead of searching for the exact median, we use some tricks that, as a pivot-element, will give us some more or less “approximately median” element. In your code, an element from the middle of the array is just stupidly selected as a pivot element. In an unordered array, this element can be anything. It can be very far from the median. It is easy to create an example in which your code will work very poorly precisely because of the repeated unsuccessful selection of the pivot element.

    A popular trick to better select a pivot-element is the median-of-three, when three different elements of the array are taken and the middle one in order is chosen as the pivot-element. This, of course, also does not necessarily give us a median, but could potentially bring our choice closer to it.

    • As I understand it, this refers to the so-called median of 3 keys . As the pivot, we choose the middle of the first, last, and located in the middle of the elements of the sorted segment. - avp
    • @avp: I mentioned the "median of three" in my answer. But I do not see any hints on the "median of three" in question. In the above code, there is no mention of the “median of three”. - AnT
    • @AnT, I read the same about the median of the three, but I didn’t understand one thing-how to find it. Is it supposed to take the first, last and middle element and do something with them, choose someone? - Elvin
    • @AnT, and where does this code? The essence of the question. - avp
    • @ AnT, what is the median of three keys, can you tell about it, how to find it? - Elvin

    Yes, this is the median. As a mediator you can choose any element of the array, or any special one by one of the methods. In your case, the arithmetic average between the first and last element is used as the median.