D
D
Den4_x2019-08-06 16:20:55
Java
Den4_x, 2019-08-06 16:20:55

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);
    }

Explain please why there is such a record, and not, say, (L + R) / 2 or even simpler: R>> 1;
//index среднего эл-та в массиве
int separator = L - (L - R) / 2;

THANK YOU in advance for your reply!

Answer the question

In order to leave comments, you need to log in

2 answer(s)
R
res2001, 2019-08-06
@res2001

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

W
Wataru, 2019-08-07
@wataru

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 question

Ask a Question

731 491 924 answers to any question