Сортировка массива чисел

15. Отсортировать массив чисел по возрастанию

Условие задачи:
Дан массив целых чисел int[].

Необходимо реализовать функцию, которая сортирует массив по возрастанию и возвращает результат.

Нельзя использовать готовый метод Arrays.sort().

Пример 1:

Вход:  [9, 4, 7, 3, 1]
Выход: [1, 3, 4, 7, 9]

Пример 2:

Вход:  [5, 1, 1, 2, 0, 0]
Выход: [0, 0, 1, 1, 2, 5]

Спойлеры к решению

Подсказки

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

Решение

public static int[] sortArray(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean swapped = false;

        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swapped = true;
            }
        }

        if (!swapped) {
            break;
        }
    }

    return arr;
}

На каждой итерации сравниваются соседние элементы:

if (arr[j] > arr[j + 1])

Если они расположены в неправильном порядке, элементы меняются местами.

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

j < arr.length - 1 - i

Флаг:

boolean swapped = false;

позволяет закончить работу раньше, если массив уже отсортирован.

Пример:

int[] nums = {9, 4, 7, 3, 1};

System.out.println(
        Arrays.toString(sortArray(nums))
);

Результат:

[1, 3, 4, 7, 9]

Алгоритм сортирует исходный массив на месте.

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

худший и средний случай — O(n²);
лучший случай для уже отсортированного массива — O(n) благодаря флагу swapped.

Дополнительная память — O(1).