Учитывая произвольно упорядоченный массив элементов n, они разбивают элементы на два подмножества так, что элементы меньше x находятся в одном подмножестве, а элементы больше x находятся в отдельном подмножестве. Например, [28, 26, 25, 11, 16, 12, 24, 29, 6, 10] и x = 17 приводят к массиву [10, 6, 12, 11, 16, 25, 24, 29, 26, 28].
Я думал об алгоритме следующим образом:
Establi sh массив a[0,...,n] и значение разбиения x.
Перемещайте разделы друг к другу до тех пор, пока не встретятся неправильно размещенные элементы. Разрешить для особых случаев, таких как x, выходящих за пределы диапазона значений массива.
Пока два раздела не пересекаются, обмениваются неправильно разделенной парой и расширяют оба раздела внутрь на один элемент
расширяет левую перегородку, в то время как элементы меньше или равны x
расширяют правую перегородку, в то время как элементы больше x
Возвращает индекс секционирования p в секционированном массиве.