Если в массиве четное количество элементов, какое значение становится «идеальным» стержнем для быстрой сортировки?

Question

Допустим, у нас есть массив, который состоит из -5,1, -9, -3. Я предполагаю, что идеальный стержень - это тот, который разбивает массив на два равных подмассива, но это возможно только для массивов с нечетным числом элементов. Как я понимаю, идеальный шарнир в этом случае будет либо -3, либо 1, поскольку они не являются элементами с самым низким или самым высоким значением?

Answer 1

Во многих случаях несколько пивотов будут одинаково хороши. Кроме того, если использовать трехстороннее подразделение, в котором все элементы, равные центральной точке, группируются в середине, оптимальный выбор основной точки будет зависеть не только от количества элементов выше и ниже основной точки, но также и от распределения их значений. Например, учитывая [1,2,2,2,3,4,5,6,7], медианное значение равно 3, но поворот вокруг 3 потребует одной операции поворота слева и двух справа, а поворот вокруг4 приведет к тому, что с каждой стороны потребуется только одна дополнительная операция.