Рубрики
Без рубрики

Сортировка оболочки в Java

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

Автор оригинала: Dunja Spasić.

Вступление

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

На практике критерии порядка предоставляются алгоритму как метод, который сравнивает два объекта и возвращает:

  • 0: Если сравниваемые сущности считаются равными
  • 1: если первая сущность считается большей, чем вторая
  • -1: если вторая сущность считается большей, чем первая

Тем не менее, это наиболее эффективно делается, когда коллекция, которую мы сортируем, содержит сопоставимые объекты – объекты, реализующие Сопоставимый интерфейс.

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

Сортировка Оболочки

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

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

Параллели с сортировкой вставки

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

Вот фрагмент кода, который должен проиллюстрировать, как работает сортировка вставки. Вся коллекция смещается вправо в нужном месте, чтобы “освободить” место для вставляемого элемента.

public static void insertionSort(ArrayList arr,int n) {
    int i, j, newValue;

    for (i = 1; i < n; i++) {
        newValue = arr.get(i);
        j = i;

        while (j > 0 && arr.get(j-1) > newValue) {
            arr.set(j,arr.get(j-1));
            j--;
        }
        arr.set(j,newValue);
    }
}

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

Чтобы понять, как это работает, мы должны сначала объяснить, что такое массив с K-сортировкой и каковы его характеристики.

K-Сортированный Массив

Предположим, A представляет собой массив размера N. Массив A отсортирован по K, если каждый элемент находится не более чем в K местах от его целевой позиции. Другими словами, для каждого i между 1 и N целевое место A[i] находится где-то между iK и 1+K в A .

Для несортированного массива N-го размера его можно отсортировать за O(N log K) время.

Важным свойством K-отсортированных массивов является то, что если K 1 отсортированный массив равен K 2 -разобрались, все остается по-прежнему 1 разобрались. Это легко можно доказать.

Случай Первый

$$ K_{1} > K_{2} $$

Если A равно K 1 -отсортировано, тогда каждый элемент из A не более K 1 места вдали от своей целевой позиции. Если мы тогда К 2 -отсортируйте A, тогда каждый элемент из A будет не более K 2 места вдали от своей целевой позиции. С тех пор как К 2 меньше, чем K 1 , если элементы из A не более K 2 места, удаленные от их цели, то они должны быть ближе, чем К 1 места от их цели. Это означает, что если A равно K 2 -отсортировано, это должно быть K 1 -разобрались.

Дело Второе

$$ K_{1} < K_{2} $$

Когда A равно K 1 -отсортированы, если мы К 2 -отсортируйте его, ни один элемент не поменяется местами, потому что A уже является K 2 -отсортировано (объяснено в предыдущем случае). Это означает, что он также останется K 1 -разобрались.

Пример Сортировки Оболочки

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

А = [7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3]

Здесь количество элементов равно 11.

Теперь мы должны выбрать пробел между элементами, которые мы хотим сравнить , а затем сгруппировать:

$$ разрыв =. $$

А : 7, 13, 18, 22, 8, 29, 14, 7, 27, 25, 3

Теперь мы составляем группы чисел, разделенные 5 элементами (между ними 4 элемента). Группы являются (7, 29, 3), (13, 14), (18, 7), (22, 27), (8, 25).

Поскольку N/2 используется для начального значения gap , первая группа состоит из 3 элементов, а другие имеют по два элемента в каждой из-за того, что в нашей коллекции неравномерное количество элементов.

А : 7 , 13, 18, 22, 8, 29 , 14, 7, 27, 25, 3

В первой группе нет элементов с индексом меньше 0, поэтому мы начинаем со второго индекса, значение которого равно 29. Следующий шаг-сравнить 29 со всеми элементами в группе с меньшими индексами.

  • 7 < 29 верно, поэтому их места не будут поменяны местами.

В группе нет других элементов с индексом ниже 5, поэтому мы закончили с A[5] .

Следующее число в группе-3, исходный индекс которого равен 10:

  • 29 < 3 является ложным, поэтому они будут заменены:

А : 7 , 13, 18, 22, 8, 3 , 14, 7, 27, 25, 29

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Теперь значение A[5] равно 3. 29 должно находиться на своем упорядоченном месте в группе, потому что в этой группе нет элемента с большим индексом. 3, с другой стороны, все равно может быть меньше, чем члены группы с более низкими индексами.

  • 7 < 3 равно false, поэтому они будут заменены:

А : 3 , 13, 18, 22, 8, 7 , 14, 7, 27, 25, 29

В A нет элементов с индексом ниже 10, которые мы еще не сравнивали с A[10] . Все члены первой группы теперь отсортированы.

Следующая группа (13, 14):

А : 3, 13 , 18, 22, 8, 7, 14 , 7, 27, 25, 29

Легко заметить, что если в группе только два элемента, они меняются местами только в том случае, если первый больше второго. Группы, которые сейчас остались, это (18, 7), (22, 27), и (8, 25), и единственной группой, которой потребуется замена, будет (18, 7):

А : 3, 13, 7 , 22, 8, 7, 14, 18 , 27, 25, 29

На данный момент для анализа не осталось групп, поэтому массив 5-отсортирован . Хотя он выглядит лучше, чем раньше, он все еще не совсем закончен.

Теперь пробел снова разделен на два:

$$ разрыв = $$

Теперь мы создаем группы элементов, которые находятся всего в 2 элементах друг от друга, что означает, что между ними есть только один элемент. Эти группы являются (3, 7, 8, 14, 27, 29) и (13, 22, 7, 18, 25):

А : 3 , 13, 7 , 22, 8 , 7, 14 , 18, 27 , 25, 29

Сортировка, когда пробел равен 2, будет отображаться на 2-сортировке второй группы.

А : 3, 13 , 7, 22 , 8, 7 , 14, 18 , 27, 25 , 29

Эти две группы отсортированы так же, как были отсортированы предыдущие группы, и мы остаемся с:

А : 3, 7 , 7, 13 , 8, 18 , 14, 22 , 27, 25 , 29

Последнее, что осталось сделать, это 1-сортировать массив, то есть фактически сортировать по вставке.

Каждый элемент сравнивается со всеми другими элементами с меньшими индексами. Здесь важно отметить, что массив уже отсортирован по 2, поэтому возможно, что элементы на местах i и i+1 не упорядочены. Поэтому при 1-сортировке можно менять местами только элементы, расположенные рядом друг с другом.

Реализация

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

public static void shSort(ArrayList arr,int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i+= 1) {

            int temp = arr.get(i);
            int j;
            for (j = i; j >= gap && arr.get(j-gap) > temp; j -= gap)
                arr.set(j,arr.get(j-gap));
            arr.set(j,temp);
        }
    }
}

Массив и его размер задаются в качестве аргументов метода, и цикл выполняется log n раз.

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

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

В связи с этим последним номером, который будет наблюдаться, будет первый член группы. Второе условие состоит в том, что j-gap < temp . Это означает, что цикл выполняется, когда есть элементы с более низкими индексами, которые больше, чем arr[j] .

Первый, который ниже, разрывает петлю. Затем arr[j] перемещается в индекс, значение которого было меньше. Этот цикл повторяется i/пробел раз.

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

Давайте теперь рассчитаем временную сложность сортировки оболочки. Как уже упоминалось, первый цикл выполняется log n раз.

Второй цикл начинается с gap в качестве индекса, который равен 2 k . Поскольку в третьем цикле мы вычитаем пробел , это означает, что в сумме я должен быть разделен на пробел :

Все это приводит к временной сложности O(n logn) . Здесь мы исходили из того факта, что gap имеет значение n/2 .

Если разрыв задан по-другому, временная сложность будет другой. Здесь вы можете прочитать более подробную информацию о временной сложности сортировки оболочки в зависимости от выбора переменной gap .

Вывод

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

Сортировка по оболочке выполняется лучше, чем сортировка по вставке, но она имеет больший коэффициент пропусков кэша, чем быстрая сортировка.

Если вы хотите узнать больше о наиболее распространенных алгоритмах сортировки, ознакомьтесь с нашей статьей об алгоритмах сортировки на Java .

Читайте ещё по теме: