Какие алгоритмы сортировки должен знать 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» лучше всего демонстрируют, как оценивается сложность методов. Если вы поймете разницу между квадратичной и линейной сложностью, то перестанете писать избыточные циклы и будете знать, где взять готовую реализацию.
