В быстрой сортировке допускается что при разбиении на две части перед опорным числом будет стоять элемент который больше за него?
Если есть массив 2 10 3 8 5 12 1 8 опорным элементом есть число 8 под индексом 3 при разбиении массива на две части вышло 1 2 3 1 5 | 12 8 10 получается что массив то разбился на две части но не выполняется условие что все элементы больше за опорный элемент должны быть слева от него (12 стоит перед 8). Тогда вопрос - нужно разбить массив просто на две части или нужно разбить массив на две части относительно опорного элемента?
Ответы (1 шт):
В процедуре разделения (partition) главное то, что массив должен быть разбит на две части - слева от некого индекса стоят элементы, меньшие разделительного элемента, а справа - большие, или равные, порядок в каждой половине не важен.
Конкретная реализация разделения может обеспечивать выставление элемента-разделителя (pivot element) именно на точку деления - например, разделитель ставится в конец массива, и процедура работает для всех элементов, кроме последнего, а потом он меняется с тем, что стоит на точке разделения. Но в общем, этого не требуется.