Какие алгоритмы сортировки должен знать Junior Java Developer

Какие алгоритмы сортировки должен знать Junior Java Developer

Разбираем 5 ключевых.

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. Метод проходится по всему массиву до тех пор, пока самые меньшие значения не окажутся в его начале.

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

public void bubbleSort(int[] array) {
    boolean isSorted = false;
    int temp;
    while(!isSorted) {
        isSorted = true;
        for (int i = 0; i < array.length-1; i++) {
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                isSorted = false;
            }
        }
    }
}

В худшем и среднем случае такая сортировка имеет самую плохую временную сложность среди всех способов — квадратичную O(n^2).

2. Сортировка выбором

Для нее нужно пройтись по всему массиву и найти в нем наименьший элемент, а затем передвинуть его в стартовую позицию. При этом стартовая позиция для следующего прохода сдвинется направо.

public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int position = i;
        int min = array[i];
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < min) {
                position = j;
                min = array[j];
            }
        }
        array[position] = array[i];
        array[i] = min;
    }
}

Эта сортировка считается неустойчивой, если применяется к более сложным структурам данных. Например, если вы сортируете массив объектов, то такой алгоритм изменит порядок объектов с одинаковым ключом, но разными остальными значениями. Оценка по времени в худшем и среднем значении будет равна O(n^2).

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

Для сортировки вставками нам нужно сдвигать элементы направо, пока они не будут между ближайшими наибольшим и наименьшим значениями (строки 5–9).

public void insertSort(int[] array) {
    for (int left = 0; left < array.length; left++) {
        int key = array[left];
        int i = left - 1;
        for (; i >= 0; i--) {
            if (key < array[i]) {
                array[i + 1] = array[i];
            } else {
                break;
            }
        }
        array[i + 1] = key;
    }
}

В отличие от предыдущего способа, эта сортировка не меняет порядок одинаковых элементов и является устойчивой. Сложность для худшего и среднего случая — O(n^2), но лучший — O(n), из-за того, что не нужно будет идти по массиву второй раз.

4. Сортировка перемешиванием

Суть этой сортировки в том, что мы идем по массиву не только к концу (строки 8–12), но и к началу (строки 21–26). В обоих блоках кода мы, по сути, используем сортировку пузырьком.

void cocktailSort(int[] array) {
    boolean isSwapped = true;
    int start = 0;
    int end = array.length;

    while (isSwapped == true) {
        isSwapped = false;
        for (int i = start; i < end - 1; ++i) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                isSwapped = true;
            }
        }
        if (isSwapped == false)
            break;
        isSwapped = false;
        end = end - 1;

        for (int i = end - 1; i >= start; i--) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                isSwapped = true;
            }
        }
        start = start + 1;
    }
}

В худшем и лучшем случае оценка времени будет также O(n^2), но для лучшего — линейной O(n).

5. Быстрая сортировка

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

public void quickSort(int[] array, int low, int high) {
    if (low >= high) return;
    int pivot = array[low + (high - low) / 2];

    int i = low, j = high;
    while (i <= j) {
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }

        if (i <= j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }

    if (low < j) quickSort(array, low, j);
    if (high > i) quickSort(array, i, high);
}

В строке 3 обозначим элемент посередине массива как опорный. Затем разбиваем массив на две части (строки 5–12). Перемещаем все элементы с меньшими значениями до опорного элемента, с большими — после (строки 14–20). С помощью рекурсии применяем метод к значениям справа и слева (строки 22–23). Если сортировать будет уже нечего, метод завершится во второй строке. Худший случай все еще равен O(n^2), но средний значительно лучше — O(n log n).

Знать алгоритмы сортировки нужно, чтобы понимать устройство методов класса Arrays, коллекций и Stream API. Алгоритмы с разной «O» лучше всего демонстрируют, как оценивается сложность методов. Если вы поймете разницу между квадратичной и линейной сложностью, то перестанете писать избыточные циклы и будете знать, где взять готовую реализацию.

Ещё статьи
Как упростить разработку.
Data science, web development, gamedev и не только.