Метод выбора и перестановки java

Сортировка массива методом перестановки

Всем здравствуйте. Только учусь программировать!
Столкнулся с проблемой. Имеется код. Код рабочий, но его нужно улучшить, как это сделать я не знаю. Было предложение добавить флаг , что за флаг хз. Буду признателен если кто-то поможет разобраться и допилить код.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

public class BubbleSort { public int[] sort(int[] array) { for (int i = 0; i  array.length; i++) { for (int j = 0; j  array.length; j++) { if (array[i]  array[j]) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } return array; } } /** * *Это тест для проверки кода. * */ import org.junit.Test; import static org.hamcrest.core.Is.is; import static org.junit.Assert.assertThat; public class BubbleSortTest { @Test public void whenSortArrayWithTenElementsThenSortedArray() { BubbleSort buble = new BubbleSort(); int[] mas = new int[] {1, 5, 4, 2, 3, 1, 7, 8, 0, 5}; int[] result = buble.sort(mas); int[] expexted = new int[] {0, 1, 1 ,2 ,3 , 4, 5, 5, 7, 8}; assertThat(mas,is(expexted)); //напишите здесь тест, проверяющий сортировку массива из 10 элементов методом пузырька, например . } }

Источник

[Путь новичка] Сортировки на java

Что бы начать писать статью для Хабра, надо начать писать статью для Хабра.

Просто звучит — не просто написать.

О себе

После 30 решил сменить профессию. Раньше был станочник, а теперь безработный джавист мечьтающий запилить стартап. Многие наверное замечали что у кого то не очень прет со структурами, так вот я как раз из тех. Что бы сесть и сделать сортировки на джава мне понадобилось сначала изучить все разделы от core до multythreading, а потом вдруг решить что мне нужны все таки сортировки.

Gaziz

Собственно о сортировках

Предстваленные алгоритмы сортировок. Для меня это важно быть автором каждой строчьки кода, зачастую это играет злую шутку со мной.

Входные данные

Занчения сортируемых данных.

• Количество сортировок для средних показателей 10 (Main.TIMES)
• Замер времени осуществлялся через класс Calendar

 Calendar timeStart = Calendar.getInstance(); // Measure start time. innerSort(integers); // Sort Calendar timeEnd = Calendar.getInstance(); // Measure end time. 

 public int[] generate() < int length = Main.LENGTH; int[] randomIntegersArray = new int[length]; for (int i = 0; i < length; i++) < randomIntegersArray[i] = random.nextInt(); >return randomIntegersArray; >

• Bubble — пузырьковая сортировка. Самая долгая, но не дорогая по памяти сортировка. Тут итерируем массив сравиния соседние значения и меняем местами значения. Сложность по времени О(N^2) по памяти О(1).

 public int[] innerSort(int[] integers) < boolean isSorted = false; while (!isSorted) < isSorted = true; for (int i = 0; i < integers.length - 1; i++) < if (integers[i] >integers[i + 1]) < functions.swapValues(integers, i, i + 1); isSorted = false; >> > return integers; >

• Comb — сортировка расческой. Понравилась простотой для понимания и сравнительной скоростью. Тут надо итерировать как в Bubbel, с той лишь разницей что сравниваемые элементы находиться на расстоянии R = Array.length/FACTOR. FACTOR в свою очередь равно FACTOR = 1.247. Как раз таки благодаря расстоянию между сравниваемыми значениями большие значения переставляются в конец за меньшее количество итераций. Сложность по времени худшеe О(N^2) лучшеe О(nlog(n)) по памяти О(1).

 public int[] innerSort(int[] integers) < int step = (int) (integers.length / FACTOR); boolean isSorted = false; while (!isSorted) < isSorted = true; for (int i = 0; i + step < integers.length; ++i) < if (integers[i] >integers[i + step]) < functions.swapValues(integers, i, i + step); isSorted = false; >> step = (int) (step / FACTOR); if (step return integers; >

• Insertion — сортировка вставками. Понравилась. Тут приходить каждый элемент ташить чуть ли не через весь отсортировнный массив. И пальцы так не загибаються что бы хоть как то разьяснить как это выглядит. Смотрите код. Сложность по времени худшее О(N^2) лучшее О(N) по памяти О(1).

 public int[] innerSort(int[] integers) < for (int i = 1; i < integers.length; i++) < int x = integers[i]; int j = i; while (j >0 && integers[j - 1] > x) < integers[i] = integers[i - 1]; --j; >integers[j] = x; > return integers; >

• Merge — сортировка слиянием. Из за большой вложенности итераторов и рекурсий сразу не далась. Тут надо делить массив до тех пор пока не поделишь на массивы длиной 1 элемент. Затем производишь слияние 2-x поэлементно сравния и записывая в буфферный или сразу в исходный массив, тут уж кто на что горазд.

Сложность по времени худшее О(nlog(n)) по памяти О(n).

 private void sortImpl(int[] integers, int[] arrayBuffer, int leftIndex, int rightIndex) < if (leftIndex < rightIndex) < int middle = (leftIndex + rightIndex) / 2; sortImpl(integers, arrayBuffer, leftIndex, middle); sortImpl(integers, arrayBuffer, middle + 1, rightIndex); int k = leftIndex; for (int i = leftIndex, j = middle + 1; i rightIndex || (i else < arrayBuffer[k] = integers[j]; ++j; >++k; > for (int i = leftIndex; i > >

• NativeJava — нативная сортировка Arrays.sort (Скопипасчено с документации на java 17) Этот класс реализует мощные и полностью оптимизированные версии, как последовательные, так и параллельные, алгоритма Dual-Pivot Quicksort Владимира Ярославского, Джона Бентли и Джоша Блоха. Этот алгоритм обеспечивает производительность O(n log(n)) для всех наборов данных и, как правило, быстрее, чем традиционные реализации быстрой сортировки (с одним поворотом). Существуют также дополнительные алгоритмы, вызываемые из быстрой сортировки Dual-Pivot, такие как смешанная сортировка вставками, слияние прогонов и сортировка кучи, сортировка подсчетом и параллельная сортировка слиянием. С: 1,7*14

Сложность по времени худшее О(n log (n)).

 public int[] innerSort(int[] integers) Arrays.sort(integers); return integers; >

• Pyramid — сортировка через построение дерева. По началу вообще не понял как делать. Окзалось тут положили дерево на массив и перебирают узлы соритруя занчение в каждом из 3 значений: корне и двух листьях. Тут хорошее подробное описание этой сортировки.

Сложность по времени худшее О(n log (n)) по памяти О(n).

 public int[] innerSort(int[] integers) < int length = integers.length; for (int i = length / 2 - 1; i >= 0; i--) < heapify(integers, length, i); >for (int i = length - 1; i > 0; i--) < functions.swapValues(integers, 0, i); // перемешение корня в конец heapify(integers, i, 0); // рекурсивный обход текушей кучи >return integers; > void heapify(int[] integers, int length, int i) // Рекурсивный обход кучи int largest = i; // с перестановками согласно порядку int left = 2 * i + 1; int right = 2 * i + 2; if (left < length && integers[left] >integers[largest]) largest = left; if (right < length && integers[right] >integers[largest]) largest = right; if (largest != i) < functions.swapValues(integers, i, largest); heapify(integers, length, largest); >>

• Quick — быстрая сортировка. Думаю эта сортировка нравиться не только мне, хоть и не сразу я с ней подружился. Особенно долго пришлось усваивать момент с выбором серединного (значение с которым сравнивают). Оказалось просто тыкаешь в самый правый, затем надо переставить согласно меньше (в левую часть), больше (в правую часть). А быстра она благодаря тому что в она очень хорошо сочитеть с архитектурой копьютера. Главный минус в худшем случае она все равно очень долгая.

Сложность по времени худшее О(n^2) по памяти О(n log(n)).

 public int[] innerSort(int[] array) < if (array.length >1) < quickSortImpl(array, 0, array.length - 1); >return array; > private int partition(int[] array, int leftValueIndex, int reeghtValueIndex) < int partitionValue = array[reeghtValueIndex]; int partitionIndex = leftValueIndex; for (int i = leftValueIndex; i < reeghtValueIndex; i++) < if (array[i] > functions.swapValues(array, partitionIndex, reeghtValueIndex); return partitionIndex; > private void quickSortImpl(int[] array, int leftValue, int rightValue) < if (leftValue < rightValue) < int partitionIndex = partition(array, leftValue, rightValue); quickSortImpl(array, leftValue, partitionIndex - 1); quickSortImpl(array, partitionIndex + 1, rightValue); >>

• Selection — сортировка выбором. Медлення и очень дорогая сортировка. Сортировка предпологает выбор наименьшего значения и перестановку значения в начало массива(0), далее следует выбор наименьшего, за исключением (0), с перестановкой в следующее место(0 + 1) и так до конца массива.

Сложность по времени худшее О(n^2) по памяти О(n^2).

 public int[] innerSort(int[] integers) < for (int i = 0; i < integers.length; i++) < // Finding next min value into array integers. int indexOfMinValueInSubArray = functions.minVal(integers, i, integers.length); // Swap values into integers array. functions.swapValues(integers, i, indexOfMinValueInSubArray); >return integers; >

• Shaker — сортировка перемешиванием(туда и обратно🤷‍♂️). Это та же пузырьковая c той лишь разницей, что после итерации с лева на право следующая итерция начинаеться с права на лево.

Сложность по времени худшее О(n^2) по памяти О(n^2).

 public int[] innerSort(int[] integers) < int num; boolean isSorted = false; int i; while (!isSorted) < isSorted = true; for (i = 0; i < integers.length - 1; i++) < if (integers[i] >integers[i + 1]) < num = integers[i]; integers[i] = integers[i + 1]; integers[i + 1] = num; isSorted = false; >> for (; 0 < i; i--) < if (integers[i] < integers[i - 1]) < num = integers[i]; integers[i] = integers[i - 1]; integers[i - 1] = num; isSorted = false; >> > return integers; >

Решил прогнать у себя? Прочти это

Function.class В этом классе представлены вспомогательные методы.

Описания к методам класса Function.class.

swapValues() — перемена значений местами

minVal() — поиск минимального значения от index до index

printArray() — вывод на консоль массива данных

checkSortedArray() — проверяет массив на коррестность сортировки

generate() — генерирует массив с рандомными данными, есить перегруженный вариант который принмает и возращает массив с данными в заданном диапазоне.

setToLength() — приведение занчения к заданной длинне (есть перегрузка метода).

printResult() — вывод в консоль результа измерения времени сортировк, есть перегруженный вариан принимающй еще и среднее значение в виде Map

averageTimeSort() — принимает и возвращает Map со средним, максильным и минимальным временем сортировки. Под ключом «wrong» возвращает количесто не верных сортировок.

Для ценителей ООП

Для замера средних показателей по времени для мортировок мне понадобилось написать отдельный метод. И первым решением было нписать в каждом классе соответвующий метод. Но я же джавист). После первого же метода в пузырьковой сортировке я понял, что не хочу писать этот медод для каждого класса ведь это будет просто повторение кода. После парды дней ничего не делания решение пришло в виде полимофизма через интерфейс. И далее решение проблемы)

public Map averageTimeSort(Sorting sort)

принимает на вход интерфейс Sorting. Этот инрейфейс реализует всего лишь один метод innerSort(int[] integers). Через этот интейфейс я реализовал полиморфизм для каждого класса сортировок. Каждый класс сортировок реализует этот интерфейс. Тем самым в каждом классе сортировке есть один и тот же метод с разными реализациями (слабая связанность). Это то мне и дало возможность не писать в каждом классе метод averageTimeSort() в каждом классе, а сделать один метод для всех сортировок. Профит.

Подведение итогов

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

Источник