Выбор стержня для алгоритма дублирования ключей

Я пытаюсь понять, как выбрать точку опоры при поиске повторяющихся ключей в массиве. Большинство примеров, которые я видел, всегда выбирали первый элемент в качестве точки поворота, делая вид, что этот элемент дублируется в массиве. Что, если это не так? Как правильно выбрать ось?

Предположим, что массив a[lo...hi] и v элемент разделения, v = a[lo]. У нас также есть еще 2 индекса gt и lt, где

  • a[lo ... lt] меньше v
  • a[lt ... gt] равны v
  • a[gt ... hi] больше v

Идея состоит в том, чтобы сканировать слева направо, пока i> gt:

  • (a[i] < v) : swap(a[i], a[lt]), i++, lt++
  • (a[i] > v) : swap(a[i], a[gt]); gt--
  • (a[i] == v): i++

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


duplicates sorting algorithm quicksort
person Dimitri    schedule 29.10.2013    source источник
comment
Я не думаю, что «алгоритм дублирования ключей» достаточно известен, чтобы можно было предположить, что все знают, что это такое. Вы должны уточнить.   -  person Bernhard Barker    schedule 29.10.2013
comment
хорошо, я обновлю свой вопрос   -  person Dimitri    schedule 29.10.2013

Ответы (1)


arrow_upward
0
arrow_downward

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

 /*
 *assume that all element are positive, reutrn -1 when there is no duplicate keys
 */
int duplicate_key(int a[], int lo, int ho) { 
 if (ho - lo <= 1) return -1; //no duplicate keys when there is no more than 2 keys
 a[lo ... lt] are less than v
 a[lt ... gt] are equal to v
 a[gt ... hi] are greater than v
 if (gt - lt > 1) return v;
 return max(duplicate_key(a, lo, it), duplicate_key(gt, hi));
}
person notbad    schedule 29.10.2013