Разделение на месте, когда массив может содержать или не содержать элемент pivot

Question

Существует ли алгоритм разделения на месте (такой, какой используется в реализации Quicksort ), который не использует элемент сводки, присутствующий в массиве?

Другими словами, элементы массива должны быть расположены в следующем порядке:

• Элементы меньше точки поворота (если есть)
• Элементы равны точке поворота (если есть)
• Элементы больше, чем сводная (если есть)

Он все равно должен возвращать индекс (после сортировки) элемента сводной диаграммы, если он присутствует в массиве, илиособое значение, если нет;Это может быть дополнение индекса, куда элемент может быть вставлен для поддержания порядка (например, возвращаемое значение стандартной функции Java двоичный поиск ).

Реализации, которые я видел, требуют, чтобы индекс элемента сводки был задан в качестве параметра (или всегда должен быть в начале массива.) К сожалению, я не знаю заранее, присутствует ли свод в массиве (или где он находитсянаходится в массиве.)

---

Редактировать (в ответ на комментарии meriton ): Мы также можем предположить, что выполняется одно из следующих условий:

• Длина массива составляет <2, <strong>или
• По крайней мере один элемент равен <= pivot <strong>и по крайней мере один элемент равен> = pivot.

В массиве могут быть повторяющиеся значения (включая дубликаты значения сводки.)

Answer 1

Это была интересная проблема. Вы можете сделать это с помощью одного последовательного прохода через массив. Пример кода в C # ниже. Предполагается массив целых чисел с именем a и значением pivot.

// Skip initial items that are < pivot
int iInsert = 0;
while (iInsert < a.Length && a[iInsert] < pivot)
{
    ++iInsert;
}
// Skip items that are = pivot
int numPivot = 0;
while (iInsert < a.Length && a[iInsert] == pivot)
{
    ++iInsert;
    ++numPivot;
}

int iCurrent = iInsert;
// Items will be added AFTER iInsert.
// Note that iInsert can be -1.
--iInsert;
while (iCurrent < a.Length)
{
    if (a[iCurrent] < pivot)
    {
        if (numPivot == 0)
        {
            ++iInsert;
            int temp = a[iInsert];
            a[iInsert] = a[iCurrent];
            a[iCurrent] = temp;
        }
        else
        {
            ++iInsert;
            int temp = a[iInsert];
            a[iInsert - numPivot] = a[iCurrent];
            a[iCurrent] = temp;
            a[iInsert] = pivot;
        }
    }
    else if (a[iCurrent] == pivot)
    {
        ++iInsert;
        int temp = a[iInsert];
        a[iInsert] = pivot;
        a[iCurrent] = temp;
        ++numPivot;
    }
    ++iCurrent;
}

int firstPivot = iInsert - numPivot + 1;

Возможно, есть некоторые возможности оптимизации.

Интересным в этом подходе является то, что вы можете легко адаптировать его для построения из потока входящих данных. Вам не нужно было бы знать, сколько предметов приходит. Просто используйте список, который может быть изменен динамически. Когда появится последний элемент, ваш список будет в правильном порядке.

Answer 2

Другая возможность состоит в том, чтобы разделить метод на два: один, который разбивает на [<= pivot,> pivot], и другой, который разбивает первую часть этого результата на [ = pivot].

public static int partitionLE(double[] a, int left, int right, double pivot) {
    double x, y;
    if (left >= right) return left;
    for (;;) {
        while ((x = a[left]) <= pivot) {
            if (++ left >= right) return left;
        }
        while ((y = a[right-1]) > pivot) {
            if (left >= -- right) return left;
        }
        if (left < right) {
            a[left] = y;
            a[right-1] = x;
        } else {
            return left;
        }
    }
}
public static int partitionLT(double[] a, int left, int right, double pivot) {
    double x, y;
    if (left >= right) return left;
    for (;;) {
        while ((x = a[left]) < pivot) {
            if (++ left >= right) return left;
        }
        while ((y = a[right-1]) >= pivot) {
            if (left >= -- right) return left;
        }
        if (left < right) {
            a[left] = y;
            a[right-1] = x;
        } else {
            return left;
        }
    }
}
public static int partition(double[] a, int left, int right, double pivot) {
    int lastP = partitionLE(a, left, right, pivot);
    int firstP = partitionLT(a, left, lastP, pivot);
    if (firstP < lastP) {
        return firstP;
    } else {
        return ~firstP;
    }
}

Answer 3

Вам повезло: в последние месяцы кодирование kata было для реализации быстрой сортировки. Вот что я придумал:

/**
 * Sorts the elements with indices i such that l <= i < r
 */
private static void qsort(int[] a, int left, int right) {
    int l = left;
    int r = right - 1;

    if (l >= r) {
        return;
    }

    int pivot = a[l];
    l++;
    for (;;) {
        while (l <= r && a[l] <= pivot) l++;
        while (a[r] > pivot  && l < r) r--;

        if (l < r) {
            int t = a[l];
            a[l] = a[r];
            a[r] = t;
        } else {
            break;
        }
    }
    l--;
    a[left] = a[l];
    a[l] = pivot;

    qsort(a, left, l);
    qsort(a, r, right);
}

Как вы можете видеть, алгоритм использует исходное местоположение сводной точки только для того, чтобы найти значение этой сводной точки и для ее свопинга к индексу между разделами.

Если мы не знаем, что стержень существует, мы просто обработали бы значения, равные значениям, похожим на сводку

Однако завершение больше не гарантируется: известно, что QuickSort завершается, потому что каждый шаг рекурсии использует работы на более коротком срезе массива, чем его вызывающая сторона, а срезы массива, как известно, короче, поскольку они не содержат элемент pivot. , Это больше не верно для вашего модифицированного алгоритма. В самом деле, легко увидеть, что завершение будет зависеть от вашей стратегии выбора значения разворота.