Журов Евгений Владимирович
КУРСОВАЯ ЗАДАЧА - QUICKSORT
Создайте метод быстрой сортировки.
Описание метода:
Это рекурсивный метод, основанный на разделении 1 массива на 2 подмассива по принципу поиска опорного элемента. Далее каждый из двух массивов снова рекрсивно вызывает тот же метод сортировки.
Разбиение 1 массива на 2 подмассива происходит поиском «опорного элемента».
Опорный элемент делит массив таким образом, что элементы, меньшие опорного, помещаются перед ним(левее), а большие или равные — после(правее). При этом сам опорный элемент не обязан быть элементом массива.
Вопрос выбора лучшего опорного элемента пока остается открытым в математике. Цель опорного элемента — попытаться разделить массив пополам, тогда сортирока пройдет максимально быстро. В задаче опорный элемент = (max + min) / 2 (считается каждый раз для каждого нового подмассива). Где max и min — максимальный и минимальный элементы массива (подмассива).
Шаг 1)
В одном цикле два итератора: i слева направо от left до right, j – справа налево от right до left, где left и right индексы, вставляемые в метод в качестве аргументов. Ищем значение опорного элемента.
Шаг 2)
Пока i <= j: двигаем i, пока не встретим элемент, который >= опорного элемента. Двигаем j, пока не встретим элемент, который <= опорного элемента. Если i <= j, то делаем обмен элементов по этим индексам. Нужно добиться, чтобы каждый элемент слева от опорного элемента был <= опорного элемента, а каждый элемент спрва от опорного элемента был >= опорного элемента. Таким способом мы найдем индекс опорного элемента в массиве или 2 соседних индекса, если опорного элемента в массиве нет.
Шаг 3)
Мы узнали индекс опорного элемента и добились того, что опорный элемент поделил массив на 2 массива. Осталось каждый подмассив поставить в качестве аргумета вызывая рекурсию.
Шаг 4)
Выход из рекурсии: массив длины 2 – если нужно, меняем эти два элемента местами. Если длина входного массива меньше двух, выходим.
При использовании встроенных методов сортировок, коллекций, стримов и материала выходящего за рамки пройденного курса задача не принимается к проверке.