Блог

Отсортируйте следующий массив a с помощью быстрой сортировки,

 [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-м элементом)?

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

Любая помощь была бы высоко оценена.

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

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

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

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

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

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

Для данного массива [6, 11, 4, 9, 8, 2, 5, 8, 13, 7]

Вычислите что-то вроде этого:

• Выберите первый элемент, который 6

• Выберите последний элемент списка, который 7

• Выберите средний элемент, который является mid = (length%2==0) ? (length/2)-1 : (length-1)/2 , который является 8

• Это создает массив и сортирует его так, как это будет [6,7,8] , теперь средний элемент в вашем массиве — медиана.

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

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

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

Ваша сводная таблица равна 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))
  

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