Do I understand the quicksort algorithm?

public static void quickSort(int[] array, int low, int high) {

 //If the array consists of one e-TA(low=high) 
 //Or, if incorrect indexes(low>high),
 //The function does not work!
 if (low >= high) {
return;
}

 //Put the handles(L and R)
 int L = low;
 int R = high;

 //index is the average e-TA in the array
 int separator = L - (L - R) / 2;

 //the tokens should not overlap
 while (L < R) {
 while ((array[L] <= array[separator]) && L < separator) {
L++;
}
 while ((array[separator] <= array[R]) && R > separator) {
R--;
}
 if (L < R) {
 swap(array, L, R);
 //If the token L got to support e-TA before marker R
 if (L == separator) {
 separator = R;
 //If the token R got to support e-TA earlier than the marker L, 
 } else if (R == separator) {
 separator = L;
}
}
}
 //Sort the left part of the reference e-TA and right
 //(same scenario as above)
 //And as a result, we DORINVANDY array!
 quickSort(array, low, separator);
 quickSort(array, separator + 1, high);
 }


explain please why there is such a record, and not, say, (L+R)/2 or more simply: R>>1;

//index is the average e-TA in the array
int separator = L - (L - R) / 2;


THANKS in advance for your answer!
March 25th 20 at 13:37
2 answers
March 25th 20 at 13:39
The algorithm I looked briefly - seems to be true.
explain please why there is such a record

I would write this:
int separator = L + (R - L) / 2;
However, both entries are equivalent, but my version is clearer.
Implies that L can be any 0 <= L < R.
Your proposed options do not give the correct result when L > 0. Check.
separator - the integer index of the middle of the specified range
March 25th 20 at 13:41
This form of the receiving medium in the range from L to R is taken to avoid overflow.

L+(R-L)/2 = L-(L-R)/2 = (L+R)/2. Yes, there is, depending on the parity can be +-1, but it doesn't matter. But in the last expression L+R may overflow if L and R are large, although the result always fits into int.
L+(R-L)/2 == L-(L-R)/2 != (L+R)/2

No there is no overflow protection. Overflow here can not be in both forms (the third not considered, because it is not true). If we assume that the input parameters are initially correct: 0 <= low <= high. Correctness is almost guaranteed if the first, lacking only check for low >= 0. - Ethan.Deckow commented on March 25th 20 at 13:44
@Ethan.Deckow, You probably misread something.

third do not consider, as it is not true


This school mathematics, probably 9th grade high:
L+(R-L)/2 = 2L/2+(R-L)/2 = (2L+R-L)/2 = (L+R)/2

Just often third form and use when you need to take the middle of the interval, you just take the arithmetic average of its ends. It seems obvious.

The expression, about which the author asks the question - is better, because there is, as you said, cannot be overflow. And it does the same thing - looking for the middle of the array. But it is less clear than the arithmetic average of all, if the author sets about his question. - Jaqueline_Lind commented on March 25th 20 at 13:47
@Jaqueline_Lind, Heh, you're right. Plus - Ethan.Deckow commented on March 25th 20 at 13:50

Find more questions by tags AlgorithmsJava