Список пирамидальная сортировка java

Метод пирамидальной сортировки, изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева.

Пирамидой ( кучей ) называется двоичное дерево такое, что

a[i] ≤ a[2i+1];

a[i] ≤ a[2i+2].

Подробнее

a[0] — минимальный элемент пирамиды.

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

Выполнение алгоритма разбивается на два этапа.

1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.

Например, массив для сортировки

24, 31, 15, 20, 52, 6

Расположим элементы в виде исходной пирамиды; номер элемента правой части (6/2-1)=2 — это элемент 15.

Результат просеивания элемента 15 через пирамиду.

Следующий просеиваемый элемент – 1, равный 31.

Затем – элемент 0, равный 24.

Разумеется, полученный массив еще не упорядочен. Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.

2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.

Продолжим процесс. В итоге массив будет отсортирован по убыванию.

Реализация пирамидальной сортировки на Си

Анализ алгоритма пирамидальной сортировки

Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших n. В худшем случае требуется n·log2n шагов, сдвигающих элементы. Среднее число перемещений примерно равно

и отклонения от этого значения относительно невелики.

Изучение алгоритмов сортировки на языке Java поможет не изобретать велосипеды и быстро выскочить на лесенку карьерного роста.

Задействование алгоритмов сортировки поможет нам упорядочить массивы Java. Для понимания: сортировка чисел от наименьшего к большему или наоборот, а также лексикографический порядок – это примеры алгоритмов сортировки, способные упорядочить Java строки и числа

Слышали о сортировке пузырьком? Его популярность обусловлена простотой, наглядностью и, конечно, названием.

Алгоритм просматривает массив и сравнивает каждую пару соседних элементов. Когда он встречает пару элементов, расположенных не по порядку, происходит замена двух элементов местами.

Остается вопрос: как узнать, что все элементы упорядочены? В этом случае очередная итерация пройдет без замены соседних элементов.

Вот шаги для сортировки массива чисел от наименьшего к большему:

  • 4 2 1 5 3 : два первых элемента расположены в массиве в неверном порядке. Меняем их.
  • 2 4 1 5 3 : вторая пара элементов тоже «не в порядке». Меняем и их.
  • 2 1 4 5 3 : а эти два элемента в верном порядке (4 2 1 4 5 3 : очередная замена.
  • 2 1 4 3 5 : результат после одной итерации.

Для полной сортировки нужен еще один шаг. Третья итерация пройдет уже без замены. Так вы поймете, что массив отсортирован.

Но причём тут пузырьки? Посмотрите снова на пример, и вы увидите, что алгоритм как бы смещается вправо. По этому поведению элементов в массиве и возникла аналогия с «пузырьками», всплывающими на «поверхность».

Реализация

Функция входит в цикл while , в котором проходит весь массив и меняет элементы местами при необходимости.

Массив в алгоритме считается отсортированным. При первой замене доказывается обратное и запускается еще одна итерация.

Цикл останавливается, когда все пары элементов в массиве пропускаются без замен:

Будьте осторожны с формулировкой условия замены!

Например, при условии a[i] >= a[i+1] алгоритм войдет в бесконечный цикл, потому что для равных элементов это условие остается true : отсюда следует бесконечная замена

Временная сложность

Рассмотрим наихудший сценарий. Вот в чем вопрос: сколько итераций нужно для сортировки всего массива? Пример:

При первой итерации 5 «всплывает на поверхность», при этом остальные элементы остаются в порядке убывания. Если вы хотите получить отсортированный массив, придется делать по одной итерации для каждого элемента, кроме 1 , и еще одну итерацию для проверки, что в сумме составляет 5 итераций.

Расширьте это утверждение для массива из n элементов, и получите n итераций. В коде это означает, что цикл while будет запускаться максимум n раз.

Каждая n-ая итерация по всему массиву (цикл for в коде) означает, что временная сложность в наихудшем случае будет равна O(n ^ 2).

Этот алгоритм разделяет оригинальный массив на сортированный и несортированный подмассивы.

Длина сортированной части равна 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 x 7 8 2 1 9 6
  • 3 x 5 7 8 2 1 9 6
  • 3 4 5 7 8 2 1 9 6

Теперь вы видите, что отсортированная часть дополнилась элементом. Каждая следующая итерация делает то же самое, и к концу вы получите отсортированный массив!

Реализация

Временная сложность

Вернемся к худшему сценарию – к массиву, отсортированному в убывающем порядке.

В этом случае каждая итерация сдвигает отсортированный массив на единицу O(n). Придется делать это для каждого элемента в каждом массиве, что приведет к сложности равной O(n ^ 2).

Сортировка выбором тоже разделяет массив на сортированный и несортированный подмассивы. Но на этот раз сортированный подмассив формируется вставкой минимального элемента не отсортированного подмассива в конец сортированного, заменой:

  • 3 5 1 2 4
  • 1 5 3 2 4
  • 1 23 5 4
  • 1 2 3 5 4
  • 1 2 3 45
  • 1 2 3 45

Реализация

В каждой итерации вы предполагаете, что первый неотсортированный элемент минимален и итерируете по всем оставшимся элементам в поисках меньшего.

После нахождения текущего минимума неотсортированной части массива вы меняете его местами с первым элементом, и он уже часть отсортированного массива:

Временная сложность

При поиске минимума для длины массива проверяются все элементы, поэтому сложность равна O(n). Поиск минимума для каждого элемента массива равен O(n^2).

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

Массив делится на два подмассива, а затем происходит:

  1. Сортировка левой половины массива (рекурсивно)
  2. Сортировка правой половины массива (рекурсивно)
  3. Слияние

На схеме показана работа рекурсивных вызовов. Для массивов, отмеченных стрелкой вниз, вызывается функция. Во время слияния возвращаются массивы со стрелкой вверх. Всё просто: мы следуем за стрелкой вниз к нижней части дерева, а затем возвращаемся и объединяем.

В примере массив 3 5 4 2 1 делится на 3 5 4 и 2 1 и так далее. При достижении «дна» начинается объединение и сортировка.

Реализация

В главную функцию передаются left и right – индексы подмассивов для сортировки, крайние слева и справа. Изначально они имеют значения 0 и array.length-1 , в зависимости от реализации.

Основа нашей рекурсии гарантирует, что мы выйдем, когда закончим, или когда left и right встретятся друг с другом. Мы находим среднюю точку mid и рекурсивно сортируем подмассивы слева и справа от середины, в итоге объединяя наши решения.

Возможно, вы вспомните дерево и спросите: почему мы не передаем два меньших массива? Ответ прост: это не нужно и вызовет огромное потребление памяти для очень длинных массивов.

Достаточно следовать индексам не нарушая логики дерева рекурсии:

Для сортировки двух подмассивов в один нужно вычислить их длину и создать временные массивы, в которые будем копировать. Так можно свободно изменять главный массив.

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

Временная сложность

Хотите легко рассчитывать рекурсивные реализации алгоритмов сортировки? Приготовьтесь к математике 🙂

Для вычисления временной сложности нам понадобится основная теорема о рекуррентных соотношениях. Временную сложность рекурсивных алгоритмов сортировки можно описать следующим уравнением:

Здесь a – это количество меньших рекурсивных вызовов, на которые мы делим проблему, а b указывает на входную величину рекурсивных вызовов.

Остальная часть уравнения – это сложность слияния всех решений в одно конечное. Упомянутая теорема решит все за вас:

Если T(n) – это время выполнения алгоритма для сортировки массива длинной n , сортировка слиянием запустится дважды для массивов длиной вполовину от оригинального.

Так, если a=2 , b=2 , шаг слияния занимает O(n) памяти при k=1 . Это означает, что уравнение для сортировки слиянием будет выглядеть так:

Примените теорему, и вы увидите, что в нашем случае a=b^k , ибо 2=2^1 . Значит, сложность равна O(nlog n), и это лучшая временная сложность для алгоритма сортировки. Доказано, что массив не может быть отсортирован быстрее, чем O(nlog n).

Для понимания работы пирамидального алгоритма сортировки нужно понять структуру, на которой он основан – пирамиду.

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

По мере движения вниз по дереву значения уменьшаются (min-heap) или увеличиваются (max-heap). Смотрите пример max-heap:

А теперь представим пирамиду в виде массива:

Чтение графа сверху вниз здесь представлено слева направо. Мы добились того, что позиция дочернего элемента по отношению к k -ому элементу в массиве – 2*k+1 и 2*k+2 (при условии, что индексация начинается с 0). Проверьте сами!

И наоборот, для k -го элемента дочерняя позиция всегда равна (k-1)/2 .

С этими знаниями вы сделаете max-heap из любого массива! Для этого проверьте каждый элемент на условие, что каждый из его дочерних элементов имеет меньшее значение.

Условие верно? Тогда меняйте местами один из дочерних элементов с родительским и повторяйте рекурсию с новым родительским элементом (он может всё ещё быть больше другого дочернего).

  • 6 1 8 3 5 2 4 : оба дочерних меньше родительского, оставляем как есть.
  • 6 1 8 3 5 2 4 : 5 > 1, поэтому меняем их. Теперь рекурсивно проверяем 5.
  • 6 5 8 3 1 2 4 : оба дочерних меньше 5, поэтому пропускаем.
  • 65 8 3 1 2 4 : 8 > 6, поэтому меняем их.
  • 8 5 6 3 1 2 4 : мы получили пирамиду, изображенную выше!

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

Постройте кучу из сокращенного массива и повторяйте процесс:

  • 8 5 6 3 1 2 4
  • 4 5 6 3 1 2 8 : замена
  • 6 5 4 3 1 28 : сортировка
  • 2 5 4 3 1 6 8 : замена
  • 5 2 4 2 16 8 : сортировка
  • 1 2 4 2 5 6 8 : замена

И так далее. Видите закономерность?

Реализация

Временная сложность

Посмотрите на функцию heapify() – кажется, что все делается за O(1), верно? Но нет же: все портит рекурсивный вызов!

Готовы посчитать, сколько вызовов нужно в наихудшем сценарии? В худшем случае рекурсивный вызов дойдет до самой вершины пирамиды прыжками к родителям каждого узла в отношении i/2 . Всего потребуется log n прыжков до вершины, значит, сложность равна O(log n).

В связи с циклами for , которые итерируют весь массив, сложность heapSort() равна O(n). Это дает нам суммарную сложность пирамидальной сортировки O(nlog n).

На этом участнике нашего топа мы закончим разбирать примеры алгоритмов сортировки.

Перед вами очередной алгоритм техники «разделяй и властвуй». Он выбирает один элемент массива в качестве стержня и сортирует остальные элементы вокруг (меньшие элементы налево, большие направо).

Так соблюдается правильная позиция самого «стержня». Затем алгоритм рекурсивно повторяет сортировку для правой и левой частей.

Реализация

Временная сложность

Временную сложность алгоритма быстрой сортировки можно описать следующим уравнением:

В наихудшем сценарии наибольший и наименьший элементы всегда выбираются в качестве стержня. Тогда уравнение приобретает вид:

Получается O(n^2).

На фоне алгоритмов сортировки со сложностью O(nlog n), выглядит не очень 🙁

На практике быстрая сортировка применяется широко. Судите сами: у алгоритма очень хорошее среднее время запуска, также равное O(nlog n), он эффективен для больших потоков ввода. И на этом преимущества не заканчиваются!

Алгоритм не занимает дополнительного пространства, вся сортировка происходит «на месте», отсутствуют затратные вызовы распределения, из-за чего его часто предпочитают сортировке слиянием.

На этом всё! Не пропустите книги по Java, среди которых Алгоритмы на Java – Роберт Седжвик, Кевин Уэйн – полезная книга для дальнейшего погружения в тему.

четверг, 1 декабря 2011 г.

Алгоритмы сортировки

Сортировки сравнением (Comparison sorts)

Сортировки сравнением имеют минимальную сложность O(n*lg n).

Сортировка вставками (Insert sort)

На каждом шаге алгоритма выбираем очередной элемент входных данных и сдвигаем его влево до тех пор, пока слева от него не останутся элементы, меньшие чем он. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы выбираются по порядку их появления во входном массиве.

Преимущества: практически не требует выделения памяти (всего O(1)); алгоритм эффективен при малом размере входного массива.

Недостатки: неэффективен на большом размере входного массива (более 100).

Реализация на Java:

Сортировка слиянием (Merge sort)

Сложность: O(n*lg n)

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

Преимущества: алгоритм эффективен при большом размере входного массива (более 1000).

Недостатки: требует выделения O(n) памяти

Реализация на Java:

Пирамидальная сортировка (Heap sort)

Сложность: O(n*lg n)

Сортировка пирамидой использует сортирующее дерево. Алгоритм заключается в выстраивании элементов массива в сортирующее дерево. Итерационно удаляем элементы из корня под одному за раз и перестраиваем дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.

Преимущества: практически не требует выделения памяти (всего O(1))

Недостатки: Из-за сложности алгоритма выигрыш получается только на больших n (более 1000)

Реализация на Java:

Быстрая сортировка (Quick sort)

Сложность: средняя O(n*lg n), максимальная O(n 2 )

Еще одна сортировка, основанная на парадигме "Разделяй и властвуй". Массив A[p..r] разбивается (путем переупорядочивания его элементов) на два подмассива A[p..q-1] и A[q+1..r]. Каждый элемент первого подмассива не превышает каждый елемент второго. Индекс q вычисляется в ходе процедуры разбиения и называется опорным элементом. Подмассивы сортируются путем рекурсивного вызова процедуры быстрой сортировки. После этого весь массив оказывается отсортированным.

Преимущества: при качественной реализации один из самых быстродействующих алгоритмов на практике; требует лишь O(lg n) дополнительной памяти

Недостатки: при неудачном выборе опорного элемента время вычисления деградирует к O(n 2 ).

Алгоритм:
Реализация на Java:

Сортировки за линейное время

Как видно из названия, сложность следующих сортировок O(n)

Сортировка подсчетом (Counting sort)

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

Достоинства: достаточно быстр

Недостатки: элементы входного массива должны быть в интервале от 0 до k, где k — натуральное число; требует выделения памяти

Реализация на Java:

Поразрядная сортировка (Radix sort)

Вариант сортировки с младших разрядов least significant digit (LSD). Сначала производится сортировка по младшему разряду, потом по следующему, и так далее, пока дело не дойдет до старшего разряда. Но существует и второй вариант — сортировка по старшему разряду (most significant digit (MSD)).

Недостатки: хотя для этой сортировки нужно меньшее количество итераций прохода по элементам, чем для сортировок сравнения, каждая итерация может длиться значительно дольше.

Реализация на Java:

Блочная (карманная) сортировка (Bucket sort)

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

Недостатки: ожидаемое время работы алгоритма линейно зависит от количества входных данных только при равномерном распределении входных элементов на отрезке.

Реализация на Java:
ну и напоследок выложу код для запуска всех вышеперечисленных сортировок, может кому-то он пригодится:


[an error occurred while processing the directive]
Карта сайта