[Путь новичка] Сортировки на java
Что бы начать писать статью для Хабра, надо начать писать статью для Хабра.
Просто звучит — не просто написать.
О себе
После 30 решил сменить профессию. Раньше был станочник, а теперь безработный джавист мечьтающий запилить стартап. Многие наверное замечали что у кого то не очень прет со структурами, так вот я как раз из тех. Что бы сесть и сделать сортировки на джава мне понадобилось сначала изучить все разделы от core до multythreading, а потом вдруг решить что мне нужны все таки сортировки.
Gaziz
Собственно о сортировках
Предстваленные алгоритмы сортировок. Для меня это важно быть автором каждой строчьки кода, зачастую это играет злую шутку со мной.
Входные данные
Занчения сортируемых данных.
Количество сортировок для средних показателей 10 (Main.TIMES)
Замер времени осуществлялся через класс Calendar
Код генерации массивов
Bubble — пузырьковая сортировка. Самая долгая, но не дорогая по памяти сортировка. Тут итерируем массив сравиния соседние значения и меняем местами значения.
Сложность по времени О(N^2) по памяти О(1).
Comb — сортировка расческой. Понравилась простотой для понимания и сравнительной скоростью. Тут надо итерировать как в Bubbel, с той лишь разницей что сравниваемые элементы находиться на расстоянии R = Array.length/FACTOR. FACTOR в свою очередь равно FACTOR = 1.247. Как раз таки благодаря расстоянию между сравниваемыми значениями большие значения переставляются в конец за меньшее количество итераций.
Сложность по времени худшеe О(N^2) лучшеe О(nlog(n)) по памяти О(1).
Insertion — сортировка вставками. Понравилась. Тут приходить каждый элемент ташить чуть ли не через весь отсортировнный массив. И пальцы так не загибаються что бы хоть как то разьяснить как это выглядит. Смотрите код.
Сложность по времени худшее О(N^2) лучшее О(N) по памяти О(1).
Merge — сортировка слиянием. Из за большой вложенности итераторов и рекурсий сразу не далась. Тут надо делить массив до тех пор пока не поделишь на массивы длиной 1 элемент. Затем производишь слияние 2-x поэлементно сравния и записывая в буфферный или сразу в исходный массив, тут уж кто на что горазд.
Сложность по времени худшее О(nlog(n)) по памяти О(n).
NativeJava — нативная сортировка Arrays.sort
(Скопипасчено с документации на java 17)
Этот класс реализует мощные и полностью оптимизированные версии, как последовательные, так и параллельные, алгоритма Dual-Pivot Quicksort Владимира Ярославского, Джона Бентли и Джоша Блоха. Этот алгоритм обеспечивает производительность O(n log(n)) для всех наборов данных и, как правило, быстрее, чем традиционные реализации быстрой сортировки (с одним поворотом). Существуют также дополнительные алгоритмы, вызываемые из быстрой сортировки Dual-Pivot, такие как смешанная сортировка вставками, слияние прогонов и сортировка кучи, сортировка подсчетом и параллельная сортировка слиянием. С: 1,7*14
Сложность по времени худшее О(n log (n)).
Pyramid — сортировка через построение дерева. По началу вообще не понял как делать. Окзалось тут положили дерево на массив и перебирают узлы соритруя занчение в каждом из 3 значений: корне и двух листьях.
Сложность по времени худшее О(n log (n)) по памяти О(n).
Quick — быстрая сортировка. Думаю эта сортировка нравиться не только мне, хоть и не сразу я с ней подружился. Особенно долго пришлось усваивать момент с выбором серединного (значение с которым сравнивают). Оказалось просто тыкаешь в самый правый, затем надо переставить согласно меньше (в левую часть), больше (в правую часть). А быстра она благодаря тому что в она очень хорошо сочитеть с архитектурой копьютера. Главный минус в худшем случае она все равно очень долгая.
Сложность по времени худшее О(n^2) по памяти О(n log(n)).
Selection — сортировка выбором. Медлення и очень дорогая сортировка. Сортировка предпологает выбор наименьшего значения и перестановку значения в начало массива(0), далее следует выбор наименьшего, за исключением (0), с перестановкой в следующее место(0 + 1) и так до конца массива.
Сложность по времени худшее О(n^2) по памяти О(n^2).
Shaker — сортировка перемешиванием(туда и обратно��♂️). Это та же пузырьковая c той лишь разницей, что после итерации с лева на право следующая итерция начинаеться с права на лево.
Сложность по времени худшее О(n^2) по памяти О(n^2).
Решил прогнать у себя? Прочти это
Сломал? Читай инструкцию.
Function.class В этом классе представлены вспомогательные методы.
Описания к методам класса Function.class.
swapValues() — перемена значений местами
minVal() — поиск минимального значения от index до index
printArray() — вывод на консоль массива данных
checkSortedArray() — проверяет массив на коррестность сортировки
generate() — генерирует массив с рандомными данными, есить перегруженный вариант который принмает и возращает массив с данными в заданном диапазоне.
setToLength() — приведение занчения к заданной длинне (есть перегрузка метода).
printResult() — вывод в консоль результа измерения времени сортировк, есть перегруженный вариан принимающй еще и среднее значение в виде Map
averageTimeSort() — принимает и возвращает Map со средним, максильным и минимальным временем сортировки. Под ключом «wrong» возвращает количесто не верных сортировок.
Для ценителей ООП
Для замера средних показателей по времени для мортировок мне понадобилось написать отдельный метод. И первым решением было нписать в каждом классе соответвующий метод. Но я же джавист). После первого же метода в пузырьковой сортировке я понял, что не хочу писать этот медод для каждого класса ведь это будет просто повторение кода. После парды дней ничего не делания решение пришло в виде полимофизма через интерфейс. И далее решение проблемы)
В классе Function, метод
принимает на вход интерфейс Sorting. Этот инрейфейс реализует всего лишь один метод innerSort(int[] integers). Через этот интейфейс я реализовал полиморфизм для каждого класса сортировок. Каждый класс сортировок реализует этот интерфейс. Тем самым в каждом классе сортировке есть один и тот же метод с разными реализациями (слабая связанность). Это то мне и дало возможность не писать в каждом классе метод averageTimeSort() в каждом классе, а сделать один метод для всех сортировок. Профит.
Подведение итогов
Структуры данных очень важны. Особенно если это вызывает еще и интерес. Следующий шаг замеры времени на нескольких потоках, но это не точно.
Какие алгоритмы сортировки должен знать Junior Java Developer
Java-разработчики не пишут простые алгоритмы сортировки самостоятельно. Они пользуются готовыми решениями и методами коллекций. Но алгоритмические задачки предлагают решить во время собеседований на junior-позицию. Объясняем, какие виды сортировок нужно знать, чтобы получить работу.
Как измеряется эффективность алгоритмов
Сортировка — это алгоритм, а эффективность любого алгоритма измеряют с помощью нотации «О» большого. «О» отвечает за количество простых операций, которые должен выполнить алгоритм, и может измерять потраченное время или память. Например, сколько операций нужно сделать, чтобы отсортировать массив чисел или найти наименьшее значение. Такой подход помогает оценить, как будет увеличиваться время выполнения алгоритма с ростом входных данных — в метод может быть передан массив и из 10, и из 1000 чисел.
Для каждого алгоритма можно оценивать худший, средний и лучший случай.
Например, худший случай — когда элементы в массиве полностью перепутаны. Для прохождения собеседования достаточно помнить худшие и средние оценки по времени.
Универсальность, развитое сообщество и популярность.
Что нужно знать.
Задача может звучать так:
«Напишите метод, который сортирует числа в несортированном массиве array в возрастающем порядке. Затем назовите временную сложность алгоритма».
Алгоритмов сортировки — более 25, но на примере решения этой задачи мы расскажем о 5 ключевых, двигаясь от простого к сложному и более эффективному.
Так варьируется сложность алгоритмов:
- O(n) — линейная сложность означает, что каждый элемент массива нужно будет проверить 1 раз.
- O(n log n) — количество проверок будет равно логарифму количества элементов массива.
- O(n^2) — количество проверок будет равно n^2, где n — количество элементов.
1. Сортировка пузырьком
Самым простым и одновременно самым плохим решением будет сортировка пузырьком. Пока массив не будет отсортирован (isSorted = false), мы проходимся по всем элементам и сравниваем текущее и следующее значение (array[i] >array[i+1]). Если текущий элемент больше следующего, их нужно поменять местами. temp присваивается значение array[i], затем array[i] присваивается array[i+1], а array[i+1] приравнивается к temp. Метод проходится по всему массиву до тех пор, пока самые меньшие значения не окажутся в его начале.
Чем больше входной массив, тем больше проходов по нему нужно сделать, а это значит, что время на сравнение элементов увеличится.
В худшем и среднем случае такая сортировка имеет самую плохую временную сложность среди всех способов — квадратичную O(n^2).
2. Сортировка выбором
Для нее нужно пройтись по всему массиву и найти в нем наименьший элемент, а затем передвинуть его в стартовую позицию. При этом стартовая позиция для следующего прохода сдвинется направо.
Эта сортировка считается неустойчивой, если применяется к более сложным структурам данных. Например, если вы сортируете массив объектов, то такой алгоритм изменит порядок объектов с одинаковым ключом, но разными остальными значениями. Оценка по времени в худшем и среднем значении будет равна O(n^2).
3. Сортировка вставками
Для сортировки вставками нам нужно сдвигать элементы направо, пока они не будут между ближайшими наибольшим и наименьшим значениями (строки 5–9).
В отличие от предыдущего способа, эта сортировка не меняет порядок одинаковых элементов и является устойчивой. Сложность для худшего и среднего случая — O(n^2), но лучший — O(n), из-за того, что не нужно будет идти по массиву второй раз.
4. Сортировка перемешиванием
Суть этой сортировки в том, что мы идем по массиву не только к концу (строки 8–12), но и к началу (строки 21–26). В обоих блоках кода мы, по сути, используем сортировку пузырьком.
В худшем и лучшем случае оценка времени будет также O(n^2), но для лучшего — линейной O(n).
5. Быстрая сортировка
Самый эффективный способ для этой задачи — быстрая сортировка. Сначала мы выбираем один элемент, а затем по отношению к нему сортируем все остальные.
В строке 3 обозначим элемент посередине массива как опорный. Затем разбиваем массив на две части (строки 5–12). Перемещаем все элементы с меньшими значениями до опорного элемента, с большими — после (строки 14–20). С помощью рекурсии применяем метод к значениям справа и слева (строки 22–23). Если сортировать будет уже нечего, метод завершится во второй строке. Худший случай все еще равен O(n^2), но средний значительно лучше — O(n log n).
Знать алгоритмы сортировки нужно, чтобы понимать устройство методов класса Arrays, коллекций и Stream API. Алгоритмы с разной «O» лучше всего демонстрируют, как оценивается сложность методов. Если вы поймете разницу между квадратичной и линейной сложностью, то перестанете писать избыточные циклы и будете знать, где взять готовую реализацию.
Rukovodstvo
статьи и идеи для разработчиков программного обеспечения и веб-разработчиков.
Алгоритмы сортировки в Java
Введение Сортировка данных означает их упорядочение в определенном порядке, часто в виде структуры данных, подобной массиву. Вы можете использовать различные критерии упорядочения, распространенными из которых являются сортировка чисел от наименьшего к наибольшему или наоборот, либо лексикографическая сортировка строк [https://en.wikipedia.org/wiki/Lexicographic_order]. Вы даже можете определить свои собственные критерии, и мы рассмотрим практические способы сделать это к концу этой статьи. Если вам интересно, как работает сортировка, мы рассмотрим различные алгоритмы, fr
Время чтения: 20 мин.
Вступление
Сортировка данных означает их упорядочение в определенном порядке, часто в виде структуры данных, подобной массиву. Вы можете использовать различные критерии упорядочения, распространенными из которых являются сортировка чисел от наименьшего к наибольшему или наоборот, или лексикографическая сортировка строк. Вы даже можете определить свои собственные критерии, и мы рассмотрим практические способы сделать это к концу этой статьи.
Если вам интересно, как работает сортировка, мы рассмотрим различные алгоритмы, от неэффективных, но интуитивно понятных решений, до эффективных алгоритмов, которые фактически реализованы на Java и других языках.
Существуют различные алгоритмы сортировки, и не все они одинаково эффективны. Мы проанализируем их временную сложность , чтобы сравнить их и посмотреть, какие из них работают лучше всего.
Список алгоритмов, которые вы здесь изучите, ни в коем случае не является исчерпывающим, но мы собрали некоторые из наиболее распространенных и наиболее эффективных, чтобы помочь вам начать работу:
Примечание . В этой статье не рассматривается параллельная сортировка, поскольку она предназначена для начинающих.
Пузырьковая сортировка
Объяснение
Пузырьковая сортировка работает, меняя местами соседние элементы, если они находятся не в желаемом порядке. Этот процесс повторяется с начала массива, пока все элементы не будут в порядке.
Мы знаем, что все элементы в порядке, когда нам удается выполнить всю итерацию без замены мест вообще — тогда все элементы, которые мы сравнивали, были в желаемом порядке со своими соседними элементами, и, соответственно, со всем массивом.
Вот шаги для сортировки массива чисел от наименьшего к наибольшему:
4 2 1 5 3: Первые два элемента расположены в неправильном порядке, поэтому мы меняем их местами.
2 4 1 5 3: вторые два элемента тоже находятся в неправильном порядке, поэтому мы меняем местами.
2 1 4 5 3: Эти два расположены в правильном порядке, 4 <5, поэтому мы оставим их в покое.
2 1 4 5 3 : Другой обмен.
2 1 4 3 5: Вот результирующий массив после одной итерации.
Поскольку во время первого прохода произошел по крайней мере один обмен (на самом деле их было три), нам нужно снова пройти через весь массив и повторить тот же процесс.
Повторяя этот процесс, пока не перестанут делать свопы, мы получим отсортированный массив.
Причина, по которой этот алгоритм называется пузырьковой сортировкой, заключается в том, что числа как бы «всплывают» на «поверхность». Если вы еще раз просмотрите наш пример, следуя определенному числу (4 — отличный пример), вы увидите, что оно медленно перемещается вправо во время процесса.
Все числа постепенно перемещаются на свои места слева направо, как пузыри, медленно поднимающиеся из водоема.
Если вы хотите прочитать подробную статью о пузырьковой сортировке , мы вам поможем!
Выполнение
Мы собираемся реализовать пузырьковую сортировку так же, как мы изложили это на словах. Наша функция входит в цикл while, в котором она выполняет замену всего массива по мере необходимости.
Мы предполагаем, что массив отсортирован, но если мы ошиблись при сортировке (если произошла подкачка), мы проходим еще одну итерацию. Затем цикл while продолжается до тех пор, пока нам не удастся пройти через весь массив без подкачки:
При использовании этого алгоритма мы должны быть осторожны при формулировании условий обмена.
Например, если бы я использовал a[i] >= a[i+1] это могло бы закончиться бесконечным циклом, потому что для равных элементов это отношение всегда было бы true и, следовательно, всегда меняло их местами.
Сложность времени
Чтобы выяснить временную сложность пузырьковой сортировки, нам нужно рассмотреть наихудший из возможных сценариев. Какое максимальное количество раз нам нужно пройти через весь массив, прежде чем мы его отсортируем? Рассмотрим следующий пример:
В первой итерации 5 будет «всплывать на поверхность», но остальные элементы останутся в порядке убывания. Нам нужно будет сделать одну итерацию для каждого элемента, кроме 1, а затем еще одну итерацию, чтобы проверить, что все в порядке, так что всего 5 итераций.
Расширьте это до любого массива из n элементов, и это означает, что вам нужно сделать n итераций. Глядя на код, это будет означать, что наш в while цикл может работать максимум n раз.
Каждый из этих n раз мы перебираем весь массив (цикл for в коде), что означает, что в худшем случае временная сложность будет O (n ^ 2) .
Примечание . Временная сложность всегда была бы O (n ^ 2), если бы не sorted логическая проверка, которая завершает алгоритм, если во внутреннем цикле нет свопов, что означает, что массив отсортирован.
Сортировка вставкой
Объяснение
Идея сортировки вставкой состоит в разделении массива на отсортированные и несортированные подмассивы.
Отсортированная часть имеет длину 1 в начале и соответствует первому (самому левому) элементу в массиве. Мы перебираем массив и на каждой итерации расширяем отсортированную часть массива на один элемент.
При расширении мы помещаем новый элемент на свое место в отсортированном подмассиве. Мы делаем это, сдвигая все элементы вправо, пока не встретим первый элемент, который нам не нужно сдвигать.
Например, если в следующем массиве выделенная жирным шрифтом часть отсортирована в порядке возрастания, произойдет следующее:
3 5 7 8 4 2 1 9 6: Берем 4 и запоминаем, что это то, что нам нужно вставить. Поскольку 8> 4, мы сдвигаемся.
3 5 7 x 8 2 1 9 6: где значение x не имеет решающего значения, поскольку оно будет немедленно перезаписано (либо на 4, если это подходящее место, либо на 7, если мы переместим). Поскольку 7> 4, мы сдвигаемся.
3 5 х 7 8 2 1 9 6
3 х 5 7 8 2 1 9 6
3 4 5 7 8 2 1 9 6
После этого процесса отсортированная часть была расширена на один элемент, теперь у нас есть пять, а не четыре элемента. Каждая итерация делает это, и к концу у нас будет отсортирован весь массив.
Если вы хотите прочитать подробную статью о сортировке вставкой , мы вам поможем!
Выполнение
Сложность времени
Опять же, мы должны рассмотреть наихудший сценарий для нашего алгоритма, и это снова будет пример, когда весь массив убывает.
Это связано с тем, что на каждой итерации нам придется перемещать весь отсортированный список на единицу, что составляет O (n) . Мы должны сделать это для каждого элемента в каждом массиве, что означает, что он будет ограничен O (n ^ 2) .
Выбор Сортировка
Объяснение
Selection Sort также делит массив на отсортированный и несортированный подмассив. Хотя на этот раз отсортированный подмассив формируется путем вставки минимального элемента несортированного подмассива в конец отсортированного массива путем замены местами:
1 5 3 2 4
1 2 3 5 4
1 2 3 5 4
1 2 3 4 5
1 2 3 4 5
Выполнение
На каждой итерации мы предполагаем, что первый несортированный элемент является минимальным, и перебираем остальные, чтобы увидеть, есть ли элемент меньшего размера.
Как только мы находим текущий минимум неотсортированной части массива, мы меняем его местами с первым элементом и считаем его частью отсортированного массива:
Сложность времени
Нахождение минимума — это O (n) для длины массива, потому что мы должны проверить все элементы. Мы должны найти минимум для каждого элемента массива, сделав весь процесс ограниченным O (n ^ 2) .
Сортировка слиянием
Объяснение
Сортировка слиянием использует рекурсию для решения проблемы сортировки более эффективно, чем ранее представленные алгоритмы, и, в частности, использует подход «разделяй и властвуй».
Используя обе эти концепции, мы разделим весь массив на два подмассива, а затем:
- Сортировать левую половину массива (рекурсивно)
- Сортировать правую половину массива (рекурсивно)
- Объедините решения
Это дерево предназначено для представления того, как работают рекурсивные вызовы. Массивы, отмеченные стрелкой вниз, — это те, для которых мы вызываем функцию, в то время как мы объединяем массивы со стрелкой вверх, возвращаясь вверх. Итак, вы следуете за стрелкой вниз до нижней части дерева, а затем снова поднимаетесь и объединяетесь.
В нашем примере у нас есть массив 3 5 3 2 1 , поэтому мы делим его на 3 5 4 и 2 1 . Чтобы отсортировать их, мы далее разделяем их на составляющие. Как только мы достигли дна, мы начинаем объединять и сортировать их по мере продвижения.
Если вы хотите прочитать подробную статью о сортировке слиянием , мы вам поможем!
Выполнение
Основная функция работает примерно так, как описано в объяснении. Мы просто передаем индексы left и right которые являются индексами самого левого и самого правого элемента подмассива, который мы хотим отсортировать. Первоначально они должны быть 0 и array.length-1 , в зависимости от реализации.
Основа нашей рекурсии гарантирует, что мы выйдем, когда мы закончим или когда right и left встретятся друг с другом. Мы находим середину mid и рекурсивно сортируем подмассивы слева и справа от нее, в конечном итоге объединяя наши решения.
Если вы помните нашу древовидную графику, вы можете задаться вопросом, почему бы нам не создать два новых меньших массива и вместо этого передать их. Это связано с тем, что на очень длинных массивах это привело бы к огромному потреблению памяти для чего-то, что по сути не нужно.
Сортировка слиянием уже не работает на месте из-за этапа слияния, и это только ухудшит ее эффективность использования памяти. В остальном логика нашего дерева рекурсии остается прежней, хотя нам просто нужно следовать индексам, которые мы используем:
Чтобы объединить отсортированные подмассивы в один, нам нужно рассчитать длину каждого и создать временные массивы для их копирования, чтобы мы могли свободно изменять наш основной массив.
После копирования проходим получившийся массив и присваиваем ему текущий минимум. Поскольку наши подмассивы отсортированы, мы просто выбрали меньший из двух элементов, которые еще не были выбраны, и переместили итератор для этого подмассива вперед:
Сложность времени
Если мы хотим определить сложность рекурсивных алгоритмов, нам понадобится немного математики.
Основная теорема используется для определения временной сложности рекурсивных алгоритмов. Для нерекурсивных алгоритмов мы обычно можем записать точную временную сложность в виде некоторого уравнения, а затем использовать нотацию Big-O, чтобы отсортировать их по классам алгоритмов аналогичного поведения.
Проблема с рекурсивными алгоритмами в том, что это же уравнение будет выглядеть примерно так:
$$
T (n) = aT (\ frac
$
Само уравнение рекурсивное! В этом уравнении a сообщает нам, сколько раз мы вызываем рекурсию, а b сообщает нам, на сколько частей разделена наша проблема. В этом случае это может показаться несущественным различием, потому что они равны для сортировки слиянием, но для некоторых проблем их может не быть.
Остальная часть уравнения — это сложность объединения всех этих решений в одно в конце. Основная теорема решает это уравнение за нас:
$$
Т (п) = \ Bigg \ <
\ begin
O (n ^
O (n ^ k), & a <b ^ k
\ end
$
Если T(n) — это время выполнения алгоритма при сортировке массива длины n , сортировка слиянием будет выполняться дважды для массивов, которые составляют половину длины исходного массива.
Итак, если у нас есть a=2 , b=2 . Шаг слияния занимает O (n) памяти, поэтому k=1 . Это означает, что уравнение сортировки слиянием будет выглядеть следующим образом:
Если мы применим основную теорему, мы увидим, что наш случай — это тот, где a=b^k потому что у нас 2=2^1 . Это означает, что наша сложность O (nlog n) . Это чрезвычайно хорошая временная сложность для алгоритма сортировки, поскольку было доказано, что массив не может быть отсортирован быстрее, чем O (nlog n) .
Хотя версия, которую мы продемонстрировали, потребляет много памяти, существуют более сложные версии сортировки слиянием, которые занимают только O (1) места.
Кроме того, алгоритм чрезвычайно легко распараллелить, поскольку рекурсивные вызовы из одного узла могут выполняться полностью независимо от отдельных ветвей. Хотя мы не будем вдаваться в подробности, как и почему, поскольку это выходит за рамки данной статьи, стоит помнить о плюсах использования этого конкретного алгоритма.
Heapsort
Объяснение
Чтобы правильно понять, почему работает Heapsort, вы должны сначала понять структуру, на которой он основан — кучи . Мы будем говорить конкретно о двоичной куче, но вы можете обобщить большую часть этого и на другие структуры кучи.
Куча — это дерево, которое удовлетворяет свойству кучи, то есть для каждого узла все его дочерние элементы находятся в заданном отношении к нему. Кроме того, куча должна быть почти полной. Почти полное двоичное дерево глубины d имеет поддерево глубины d-1 с тем же полным корнем, в котором каждый узел с левым потомком имеет полное левое поддерево. Другими словами, при добавлении узла мы всегда выбираем крайнюю левую позицию на самом высоком незавершенном уровне.
Если куча — это максимальная куча , тогда все дочерние элементы меньше родительского, а если это минимальная куча, все они больше.
Другими словами, по мере движения вниз по дереву вы получаете все меньшие и меньшие числа (min-heap) или все большие и большие числа (max-heap). Вот пример максимальной кучи:
Мы можем представить эту максимальную кучу в памяти в виде массива следующим образом:
Вы можете представить себе это как чтение от уровня графика слева направо. Этим мы достигли того, что если мы возьмем kth элемент в массиве, его дочерние позиции будут 2*k+1 и 2*k+2 (при условии, что индексирование начинается с 0). Вы можете убедиться в этом сами.
И наоборот, для kth элемента позиция родителя всегда (k-1)/2 .
Зная это, вы можете легко "максимально увеличить кучу" для любого заданного массива. Для каждого элемента проверьте, не меньше ли его дочерний элемент. Если это так, поменяйте местами один из них с родительским и рекурсивно повторите этот шаг с родительским элементом (потому что новый большой элемент все еще может быть больше, чем его другой дочерний элемент).
У листьев нет дочерних элементов, поэтому они банально представляют собой максимальные кучи:
6 1 8 3 5 2 4 : Оба потомка меньше, чем родитель, поэтому все остается неизменным.
6 1 8 3 5 2 4: Поскольку 5> 1, мы меняем их местами. Мы рекурсивно нагромождаем сейчас 5.
6 5 8 3 1 2 4: Оба ребенка меньше, поэтому ничего не происходит.
6 5 8 3 1 2 4: Поскольку 8> 6, мы меняем их местами.
8 5 6 3 1 2 4: У нас есть куча, изображенная выше!
Как только мы научимся нагромождать массив, все остальное будет довольно просто. Мы меняем местами корень кучи с концом массива и сокращаем массив на единицу.
Мы снова нагромождаем сокращенный массив и повторяем процесс:
4 5 6 3 1 2 8 : поменяно местами
6 5 4 3 1 2 8 : с кучей
2 5 4 3 1 6 8 : поменяно местами
5 2 4 2 1 6 8 : с кучей
1 2 4 2 5 6 8 : поменяно местами
И так далее, я уверен, вы можете увидеть, как возникает закономерность.
Выполнение
Сложность времени
Когда мы смотрим на heapify() , кажется, что все делается за O (1) , но есть этот надоедливый рекурсивный вызов.
Сколько раз это будет вызвано в худшем случае? Что ж, в худшем случае он будет распространяться до самого верха кучи. Он сделает это, перейдя к родительскому элементу каждого узла, таким образом, вокруг позиции i/2 . это означает, что он сделает в худшем случае log n прыжков, прежде чем достигнет вершины, поэтому сложность составляет O (log n) .
Поскольку heapSort() явно O (n) из-за циклов for, повторяющихся по всему массиву, это сделает общую сложность Heapsort равной O (nlog n) .
Heapsort — это сортировка на месте, то есть для нее требуется O (1) дополнительного места, в отличие от сортировки слиянием, но у нее также есть некоторые недостатки, такие как сложность распараллеливания.
Быстрая сортировка
Объяснение
Quicksort — это еще один алгоритм «разделяй и властвуй». Он выбирает один элемент массива в качестве точки поворота и сортирует все остальные элементы вокруг него, например меньшие элементы слева и большие справа.
Это гарантирует, что ось будет на своем месте после процесса. Затем алгоритм рекурсивно делает то же самое для левой и правой частей массива.
Выполнение
Сложность времени
Временная сложность Quicksort может быть выражена следующим уравнением:
Наихудший сценарий — когда для поворота всегда выбирается самый большой или самый маленький элемент. Тогда уравнение будет выглядеть так:
$$
Т (п) = Т (0) + Т (п-1) + О (п) = Т (п-1) + О (п)
$
Оказывается, это O (n ^ 2) .
Это может показаться плохим, поскольку мы уже изучили несколько алгоритмов, которые работают за время O (nlog n) как наихудший случай, но Quicksort на самом деле очень широко используется.
Это потому, что он имеет действительно хорошее среднее время выполнения, также ограниченное O (nlog n) , и очень эффективно для большой части возможных входных данных.
Одна из причин, по которой предпочтение отдается сортировке слиянием, заключается в том, что она не занимает лишнего места, вся сортировка выполняется на месте и отсутствуют дорогостоящие вызовы выделения и освобождения.
Сравнение производительности
При этом часто бывает полезно запустить все эти алгоритмы на вашем компьютере несколько раз, чтобы получить представление о том, как они работают.
Они будут работать по-разному с разными коллекциями, которые, конечно, сортируются, но даже с учетом этого вы сможете заметить некоторые тенденции.
Давайте запустим все реализации, одну за другой, каждая на копии перетасованного массива из 10 000 целых чисел:
время (нс) Пузырьковая сортировка Сортировка вставкой Выбор Сортировка Сортировка слиянием HeapSort QuickSort
Первый забег 266 089 476 21 973 989 66 603 076 5 511 069 5 283 411 4 156 005
Второй прогон 323 692 591 29 138 068 80 963 267 8 075 023 6 420 768 7 060 203
Третий пробег 303 853 052 21 380 896 91 810 620 7 765 258 8 009 711 7 622 817
Четвертый забег 410 171 593 30 995 411 96 545 412 6 560 722 5 837 317 2 358 377
Пятый заезд 315 602 328 26 119 110 95 742 699 5 471 260 14 629 836 3 331 834
Шестой пробег 286 841 514 26 789 954 90 266 152 9 898 465 4 671 969 4 401 080
Седьмой забег 384 841 823 18 979 289 72 569 462 5 135 060 10 348 805 4 982 666
Восьмерка 393 849 249 34 476 528 107 951 645 8 436 103 10 142 295 13 678 772
Девятый забег 306 140 830 57 831 705 138 244 799 5 154 343 5 654 133 4,663,260
Десятый забег 306 686 339 34 594 400 89 442 602 5 601 573 4 675 390 3 148 027
Очевидно, мы видим, что пузырьковая сортировка — худшая, когда дело касается производительности. Избегайте использования его в производственной среде, если вы не можете гарантировать, что он будет обрабатывать только небольшие коллекции и не остановит приложение.
HeapSort и QuickSort являются лучшими с точки зрения производительности. Хотя они выдают похожие результаты, QuickSort, как правило, немного лучше и согласованнее, что подтверждается.
Сортировка в Java
Сопоставимый интерфейс
Если у вас есть собственные типы, реализация отдельного алгоритма сортировки для каждого из них может оказаться обременительной. Вот почему Java предоставляет интерфейс, позволяющий использовать Collections.sort() в ваших собственных классах.
Для этого ваш класс должен реализовать Comparable<T> , где T — ваш тип, и переопределить метод с именем .compareTo() .
Этот метод возвращает отрицательное целое число, если this меньше элемента аргумента, 0, если они равны, и положительное целое число, если this больше.
В нашем примере мы создали класс « Student , и каждый студент идентифицируется по id и году начала учебы.
Мы хотим отсортировать их в первую очередь по поколениям, но также во вторую очередь по идентификаторам:
А вот как его использовать в приложении:
Интерфейс компаратора
Мы могли бы захотеть отсортировать наши объекты неортодоксальным способом для определенной цели, но мы не хотим реализовывать это как поведение нашего класса по умолчанию, или мы могли бы сортировать коллекцию встроенного типа в не- способ по умолчанию.
Для этого мы можем использовать интерфейс Comparator Например, возьмем наш Student и отсортируем только по ID:
Если мы заменим вызов sort в main следующим:
Как все это работает
Collection.sort() работает, вызывая базовый Arrays.sort() , в то время как сама сортировка использует сортировку вставкой для массивов короче 47 и Quicksort для остальных.
Согласно документации JDK10, он основан на конкретной реализации Quicksort с двумя опорами, что позволяет избежать большинства типичных причин снижения производительности до квадратичной.
Заключение
Сортировка — очень распространенная операция с наборами данных, будь то их дальнейший анализ, ускорение поиска за счет использования более эффективных алгоритмов, основанных на сортируемых данных, фильтрации данных и т. Д.
Сортировка поддерживается многими языками, и интерфейсы часто скрывают от программиста, что на самом деле происходит. Хотя эта абстракция приветствуется и необходима для эффективной работы, иногда она может быть смертельной для эффективности, и полезно знать, как реализовать различные алгоритмы, и знать их плюсы и минусы, а также то, как легко получить доступ к встроенным реализациям.
Алгоритмы поиска и сортировки в Java
Advertisements report this ad
Please enable JavaScript
Алгоритмы сортировки
Алгоритмы сортировки в основном используются для переупорядочения набора элементов. Сортировка обычно выполняется в массивах для отображения элементов определенным образом, который требуется. Сортировка всех видов происходит по оператору сравнения, который действует как порог для рассматриваемых элементов. Оператор сравнения определяет окончательную структуру коллекции после выполнения сортировки.
В этой статье мы подробно обсудим алгоритмы поиска и сортировки в Java.
Методы сортировки на месте и не на месте
Сортировка осуществляется двумя различными методами, а именно методом на месте и без него. Сортировка на месте — это когда сортировка выполняется без использования какой-либо дополнительной или внешней памяти, кроме соответствующего массива. Двумя распространенными примерами этого метода являются сортировка выбором и сортировка вставками. С другой стороны, сортировка не на месте — это когда метод требует дополнительной памяти (как правило, флаговой переменной) для завершения переупорядочения содержимого коллекции. Сортировка слиянием и сортировка подсчетом — два примера сортировки не на месте.
Алгоритмы поиска
Алгоритмы поиска — это метод проверки элемента или извлечения элемента из коллекции или структуры данных. Как следует из названия, алгоритмы поиска используют итератор или иным образом для индивидуальной проверки каждого элемента коллекции. В зависимости от типа проводимого поиска эти алгоритмы можно разделить на последовательный и интервальный поиск.
Последовательный поиск
Эти методы поиска включают в себя запуск с первого элемента и обход всего списка до тех пор, пока не будет найден требуемый элемент. Следовательно, это влечет за собой большую сложность.
Интервальный поиск
Методы интервального поиска применяются, когда нужно искать в уже отсортированном списке. Поэтому, в зависимости от критериев сортировки, требуется поиск только в сегменте всего списка, что делает интервальный поиск гораздо более эффективным, чем последовательный поиск.
Преимущество использования алгоритмов поиска и сортировки в Java
В отсортированном списке поиск выполняется быстрее, чем в несортированном. Поэтому оба процесса идут рука об руку друг с другом, чтобы повысить эффективность нашей программы.