Журов Евгений Владимирович

КУРСОВАЯ ЗАДАЧА - Сортировка

Смауг, живущий в пещере с золотом был заперт внутри горы. Чтобы занять свое время помимо сна любил развлекать себя следующей игрой. Он складывал произвольное количество одинаковых монеток по мешочкам, расставлял их в ряд произвольным образом и придумывал алгоритмы, которыми он будет пользоваться для того, чтобы расставить мешочки в порядке возрастания ценности. Времени было много и у него получилось придумать десятки алгоритмов с целью выбрать лучший, который справится с сортировкой за минимальное количество действий.  

Сортировка — алгоритм расположения элементов массива по неубыванию (возрастанию, если элементы не повторяются).

Создайте два метода сортировки: пузырьком и quicksort.

Описание метода пузырьком:

Шаг 1) Метод заключается в попарном сравнении соседних элементов в массиве слева направо. Сначала сравнивается 0 и 1 индексы в массиве. Если значения элемента с 0 индексом больше элемента с 1 индексом: элементы меняются местами.

Потом сравниваются 1 и 2 индексы, и так последовательно попарно сравниваются все элементы массива. При этом максимальный элемент массива окажется самым правым в массиве.

Шаг 2) Далее массивом будем считать неотсортированную часть массива, то есть без последнего самого правого элемента.
Шаг 3) Повторяем шаги 1 и 2 до полной сортировки массива.
Создайте метод быстрой сортировки.

Описание метода 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 – если нужно, меняем эти два элемента местами. Если длина входного массива меньше двух, выходим.

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

Создайте массив рандомных целых чисел из 10 000 элементов и сравните время, которое потребуется для каждой из сортировок.

Требования к оформлению.

При использовании встроенных методов сортировок, коллекций, стримов и материала выходящего за рамки пройденного курса задача не принимается к проверке.
Спасибо Вам за уделенное время. Удачи.