Сортировка вставками в Java

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

Определение

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

Рассмотрим входные и выходные данные при сортировке вставками:

• Вход: массив A с неотсортированными числовыми элементами: A[0, 1, n, n-2…].
• Выход: массив, содержащий те же числа, только полностью отсортированные. Обычно он обозначается как массив B: B[0], B[1], …, B[n-1].

Существует несколько способов применения рассматриваемого алгоритма. К наиболее популярным из них относятся:

• Числовая сортировка по возрастанию: [1, 2, 3, 4, 5]
• Числовая сортировка по убыванию: [5, 4, 3, 2, 1]
• Алфавитная сортировка: [a, b, c, d]

Важно: пустой массив или массив из одного элемента по умолчанию считаются отсортированными!

Сортировка вставками по шагам

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

Шаг 1. Проход от arr[1] до arr[n], где n – числовое значение (обычно меньше 10).

Шаг 2. Сравнение текущего элемента (ключа) с предыдущим с помощью метода sort().

Шаг 3. Если все элементы больше ключа, сравнение повторяется до тех пор, пока не найдется меньшее значение.

Шаг 4. Все элементы, большие, чем ключ, сдвигаются на позицию вправо, после чего ключ вставляется на освободившееся место.

Шаг 5. Шаги повторяются, пока весь массив не будет отсортирован

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

Пошаговое руководство:

1. Объявление массива для сортировки

Создаем массив, используя int[]

int[] arrayA = {10, 14, 20, 30};

2. Использование sort_arr для реализации алгоритма

Метод sort_arr – один из самых распространенных способов реализации сортировки вставками. На практике это выглядит вот так:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Создание цикла и итератора

Использование цикла в алгоритме сортировки позволяет разработчикам избежать повторения логики для каждого элемента:

for(int i=0; i< sort_arr.length; ++i){

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

int j = i;

4. Реализация цикла while

Чтобы настроить цикл для сортировки по возрастанию, необходимо выполнить два условия:

• Значение j должно быть больше 0
• Значение j-1, должно быть больше значения j

Как только оба условия выполняются, значение ключа массива присваивается индексу j.

5. Сортировка массива

Значения по индексам j и j-1 будут меняться, пока оба условия в цикле while не будут выполнены. Аналогичным образом сортировка будет повторяться для каждого значения в цикле for до тех пор, пока условия цикла for также не будут выполнены.

Вот как сортировка вставками выглядит на практике:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Сортировка ArrayList: пошаговое руководство

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

1. Создаем класс Element для объектов коллекции:

public class Element {
    private int id;

    public Element(int id) {
        this.id = id;
    }

2. Реализуем метод compareTo() для сравнения элементов:

public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res = -1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

3. Реализуем алгоритм сортировки для ArrayList с использованием циклов

public static void insertionSortArrayList(List<element> list) {
    for (int j = 1; j < list.size(); j++) {
        Element current = list.get(j);
        int i = j-1;
        while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
            list.set(i+1, list.get(i));
            i--;
        }
        list.set(i+1, current);
    }
}

4. ArrayList можно дополнять новыми элементами следующим образом:

List<element> list = new ArrayList<>();


for (int i = 0; i < 25; i++) {
    list.add(new Element(i));
}


Collections.shuffle(list);

5. Выполняем сортировку:

list.forEach(e -> System.out.print(e.getId() + ", "));


insertionSortArrayList(list);

System.out.println();


list.forEach(e -> System.out.print(e.getId() + ", "));

6. Сравним входные и выходные данные:

4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Практические задачи

Вопрос на понимание теории № 1

Дан массив [1, 4, 6, 8], в него добавляется новый элемент n = 7. Какое количество сравнений необходимо сделать, чтобы получить отсортированную последовательность чисел? Укажите конечное значение индекса n в массиве.

Вопрос на понимание теории № 2

Дан набор чисел [0, 3, 6, 8, 9]. Каким должен быть порядок элементов во входной последовательности, чтобы время сортировки было максимальным?

Практическая задача

Отсортируйте массив [0, 1, 4, 5, 2, 3, 7, 9, 8] по возрастанию, применяя сортировку вставками.

Что дальше?

1. Проанализируйте различия между сортировкой вставками и сортировкой пузырьком/выбором/слиянием. Сравните их производительность.
2. Подумайте, можно ли улучшить сортировку вставками, добавив бинарный поиск для нахождения правильной позиции вставки?
3. Погрузитесь в изучение более эффективных алгоритмов, таких как Quick Sort и Merge Sort для больших наборов данных.

Готовы к новым испытаниям?

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

• Измените сортировку вставками для сортировки в порядке убывания.
• Реализуйте версию, которая сортирует только четные числа, а нечетные оставляет на месте.
• Объедините сортировку вставками с бинарным поиском для сокращения количества сравнений.

Перевод статьи «Insertion Sort in Java».