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

Это была интересная проблема. Сделать это можно за один последовательный проход по массиву. Пример кода на 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;

Вероятно, есть возможности для оптимизации.

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

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

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

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

Если мы не знаем, что точка поворота существует, мы бы просто обрабатывали значения, равные оси поворота, как значения ‹pivot, т.е. вместо того, чтобы разделять элементы на три группы, меньшие, равные и большие, чем точка поворота, мы бы разделили на две группы меньше или равны pivot и больше pivot, и рекурсивно повторяются на каждом из этих разделов. Это решение было бы правильным.

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

Другая возможность - разделить метод на два, один, который разбивает на [‹= pivot,> 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;
    }
}