Какой должна быть позиция указателей сортировки quck, если piot является первым или последним?

Question

Я много раз обсуждал это во многих местах, но я искал 3 дня и не понимал, как это происходит.Мой вопрос:

Где находится второй указатель, если мы возьмем первый или последний элемент в качестве оси?

Что я буквально имею в виду:

Случай 1

Центральный элемент массива в виде оси

Это все clear , когда 5 находится в центре, мы идем дальше и находим элементы, которые соответствуют условиям:

1.) Элемент

2.) Element> pivot для правой стороны, если найден, мы останавливаем указатель

3.) Поменяйте местами элементы, на которых мы остановили указатели во время шагов 1 и 2

Случай 2: ( неясно один )

первый или последний элемент какa pivot

Здесь неясно, куда я должен поместить оба указателя, чтобы начать поиск элементов, и в каком направлении относительно поворота я должен двигаться?Должны ли это быть два указателя, и как их следует перемещать?Еще должно быть ровно два указателя?

Answer 1

Если используются два указателя, это некоторая вариация схемы разбиения Hoare, где указатели начинаются с первого и последнего элемента массива и продвигаются навстречу друг другу, сканируя «неуместные» элементы. Если в качестве основного элемента выбран первый или последний элемент, первый своп будет включать основной элемент.

Обратите внимание, что алгоритм Хоара обычно включает опору в одном из разделов. Это создает проблему при использовании первого или последнего элемента в качестве сводной, поскольку шаблоны данных, такие как уже отсортированные данные, могут привести к переполнению стека, поскольку разделение всегда будет 0 элементами и n элементами. Чтобы решить эту проблему, алгоритм должен был бы исключить стержень в рекурсивных вызовах.