Встречается на собеседованиях • сегодня

Сколько работает Bubble Sort

В худшем и среднем случае Bubble Sort работает за O(n²), где n — количество элементов. Это связано с тем, что алгоритм проходит по массиву n раз, и на каждой итерации сравнивает все соседние элементы.

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

Пример:

java
void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; 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;  // оптимизация для лучшего случая
    }
}
Sophi
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
Попробовать бесплатноArrow

Следующий вопрос

Это единственный вопрос по вашему фильтру

как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы