Quicksort Pivot

Question

Сортировка следующего массива с использованием быстрой сортировки,

[6, 11, 4, 9, 8, 2, 5, 8, 13, 7]

. В качестве среднего арифметического первого и последнего элемента следует выбирать ось, т. Е. (a[0] + a[size - 1]) / 2 (rounded down).

Показатьвсе важные шаги, такие как разбиение и рекурсивные вызовы алгоритма.

---

Я понимаю, как сортировать массив, используя быструю сортировку, однако я не уверен, как рассчитать сводку.

Определяется ли опорная точка как 6 + 7 = 13, затем 13 / 2 = 6.5 (округлено до 6), поэтому опорная точка равна 2 (т.е. 6-й элемент)?

Я знаю, что элементы, меньшие, чем опорная точка, появляются нас левой стороны, и элементы больше, чем шарнир, появляются с правой стороны, и раздел повторяет этот шаг сортировки подмассива.

Любая помощь будет принята с благодарностью.

Answer 1

Для быстрой сортировки пивот может быть любым элементом, который вы хотите.Проверьте Википедия .

Проблема была легко решена путем выбора либо случайного индекса для сводной области, выбора среднего индекса раздела или (особенно для более длинных разделов)выбрав медиану первого, среднего и последнего элемента раздела для оси

Таким образом, возможны три варианта:

• Первый элемент
• Средний элемент
• Медиана первого, среднего и последнего.

И в вашем случае использование среднего значения первого и последнего элемента значение даст вам:

6 + 7 = 13
13 / 2 = 6.5
6.5 rounded down = 6

Answer 2

Между прочим, вопрос должен быть равен 6, а не обязательно 6-му элементу в массиве.

Это наиболее точно так, потому что если бы в массиве было всего 3 элемента, например, а среднее арифметическое оказалось больше 3, у вас не было бы возможности выбора, потому что нет элемента с таким индексом .

Примечание. Будьте осторожны с тем, как индексировать элементы в вашем массиве. Вы сказали, что 6-й элемент - это «2», когда он может быть «5», если ваш язык программирования начинает индексы с 0.

Answer 3

Ваш стержень равен 6. Ваш стержень НЕ является 6-м элементом. Теперь вы можете применить следующий алгоритм.

function quicksort(array)
 var list less, greater
 if length(array) ≤ 1
     return array  // an array of zero or one elements is already sorted
 select and remove a pivot value pivot from array
 for each x in array
     if x ≤ pivot then append x to less
     else append x to greater
 return concatenate(quicksort(less), pivot, quicksort(greater))

Answer 4

Положение центра из этого расчета не важно, быстрая сортировка элементов в зависимости от того, больше они или меньше, чем центр. Затем стержень помещается между двумя наборами (больше и меньше).