Answer the question
In order to leave comments, you need to log in
Am I understanding the quicksort algorithm correctly?
public static void quickSort(int[] array, int low, int high) {
//Если массив состоит из одного эл-та(low=high)
//Или, если введены неверные индексы(low>high),
//То функция не сработает!
if (low >= high) {
return;
}
//Ставим маркеры(L и R)
int L = low;
int R = high;
//index среднего эл-та в массиве
int separator = L - (L - R) / 2;
//маркеры не должны пересекаться
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);
//Если маркер L добрался до опорного эл-та раньше, чем маркер R, то
if (L == separator) {
separator = R;
//Если маркер R добрался до опорного эл-та раньше, чем маркер L, то
} else if (R == separator) {
separator = L;
}
}
}
//Cортируем левую часть от опорного эл-та и правую
//(таким же сценарием, что и выше)
//И в итоге получаем, ОТСОРИРОВАННЫЙ массив!
quickSort(array, low, separator);
quickSort(array, separator + 1, high);
}
//index среднего эл-та в массиве
int separator = L - (L - R) / 2;
Answer the question
In order to leave comments, you need to log in
The algorithm was skimmed over - it seems to be true.
I would write like this:
int separator = L + (R - L) / 2;
However, both entries are equivalent, but my version is clearer.
It is understood that L can be any 0 <= L < R.
The options you suggested do not give the correct result for L > 0. Check.
separator - integer index of the middle of the specified range
This form of obtaining an average in the range from L to R is taken so that there is no overflow.
L+(RL)/2 = L-(LR)/2 = (L+R)/2. Yes, here, depending on the parities, there may be a difference of + -1, but this is not important. But in the last expression, L+R may overflow if both L and R are large, although the result always fits into an int.
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question