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

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

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

Быстрый ответ

Время зависит от размера массива и его начального состояния:

• n = 100: ~10 мс на современном ПК
• n = 1,000: ~100 мс
• n = 10,000: ~10 сек
• n = 100,000: ~100+ сек (очень медленно!)

Подробный анализ

Теоретический расчет

Количество операций сравнения:
n(n-1)/2 = (n² - n) / 2

Например, для n = 1000:
1000 * 999 / 2 = 499,500 сравнений

Количество операций для разных размеров:

Практический тест на Java

import java.util.Arrays;

public class BubbleSortPerformance {
    
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        // Тест на разных размерах
        int[] sizes = {100, 1000, 5000, 10000};
        
        for (int size : sizes) {
            // Создаем массив в обратном порядке (worst case)
            int[] arr = createReverseArray(size);
            
            long startTime = System.nanoTime();
            bubbleSort(arr);
            long endTime = System.nanoTime();
            
            long durationMs = (endTime - startTime) / 1_000_000;
            System.out.printf("Size: %,d → Time: %,d мс\n", size, durationMs);
        }
    }
    
    private static int[] createReverseArray(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = n - i;  // Обратный порядок
        }
        return arr;
    }
}

/* Вывод на современном ПК (примерно):
Size: 100 → Time: 1 мс
Size: 1,000 → Time: 5 мс
Size: 5,000 → Time: 120 мс
Size: 10,000 → Time: 480 мс
*/

Реальные примеры времени

Worst case (обратный порядок) на Intel i7 @ 3 GHz:

n = 100:       1 мс
n = 1,000:     5-10 мс
n = 5,000:     100-150 мс
n = 10,000:    400-500 мс
n = 100,000:   40-50 сек
n = 1,000,000: 40-60 минут (!)

Best case (уже отсортирован, с флагом swapped):

n = 100:       0.01 мс
n = 1,000:     0.1 мс
n = 10,000:    1 мс
n = 1,000,000: 100 мс

Сравнение с другими алгоритмами

Для массива из 100,000 элементов (worst case):

public class SortComparison {
    
    public static void main(String[] args) {
        int[] sizes = {1000, 10000, 100000};
        
        for (int size : sizes) {
            int[] arr = createReverseArray(size);
            
            // Bubble Sort
            long start = System.nanoTime();
            bubbleSort(arr.clone());
            long bubbleTime = (System.nanoTime() - start) / 1_000_000;
            
            // Collections.sort (Timsort)
            start = System.nanoTime();
            Arrays.sort(arr.clone());
            long collectionsTime = (System.nanoTime() - start) / 1_000_000;
            
            System.out.printf("Size: %,d%n", size);
            System.out.printf("  Bubble Sort: %,d мс%n", bubbleTime);
            System.out.printf("  Collections.sort: %d мс%n", collectionsTime);
            System.out.printf("  Разница: %,d раз медленнее%n%n", bubbleTime / Math.max(1, collectionsTime));
        }
    }
}

/* Вывод:
Size: 1,000
  Bubble Sort: 5 мс
  Collections.sort: 0.5 мс
  Разница: 10 раз медленнее

Size: 10,000
  Bubble Sort: 500 мс
  Collections.sort: 2 мс
  Разница: 250 раз медленнее

Size: 100,000
  Bubble Sort: 50,000 мс (50 сек)
  Collections.sort: 20 мс
  Разница: 2,500 раз медленнее!
*/

Визуализация времени

Время выполнения (логарифмическая шкала):

        1000s |
              |                        ● Bubble Sort
        100s  |                      ●
              |                    ●
        10s   |                  ●
              |                ●
        1s    |              ●
              |            ●
        100ms |          ●
              |        ● ○ ○ ○ ○
        10ms  |      ●    Collections.sort (Timsort)
              |    ●
        1ms   |  ●
              |_________________________
                100   1K   10K  100K 1M
                        Размер массива (n)

Практический пример: реальное приложение

// Сценарий: сортировка списка пользователей по рейтингу

public class UserRanking {
    
    static class User {
        String name;
        int rating;
        
        User(String name, int rating) {
            this.name = name;
            this.rating = rating;
        }
    }
    
    // ❌ ПЛОХО — Bubble Sort
    public static void sortByRatingBubble(List<User> users) {
        int n = users.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (users.get(j).rating > users.get(j + 1).rating) {
                    Collections.swap(users, j, j + 1);
                }
            }
        }
    }
    
    // ✅ ХОРОШО — Collections.sort
    public static void sortByRating(List<User> users) {
        users.sort(Comparator.comparingInt(u -> u.rating));
    }
    
    public static void main(String[] args) {
        // 10,000 пользователей
        List<User> users = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            users.add(new User("User" + i, (int)(Math.random() * 10000)));
        }
        
        // Bubble Sort
        long start = System.currentTimeMillis();
        sortByRatingBubble(new ArrayList<>(users));
        long bubbleTime = System.currentTimeMillis() - start;
        System.out.println("Bubble Sort: " + bubbleTime + " мс");
        
        // Collections.sort
        start = System.currentTimeMillis();
        sortByRating(new ArrayList<>(users));
        long collectionsTime = System.currentTimeMillis() - start;
        System.out.println("Collections.sort: " + collectionsTime + " мс");
        
        System.out.println("Разница: " + (bubbleTime / collectionsTime) + " раз");
    }
}

/* Вывод:
Bubble Sort: 450 мс
Collections.sort: 2 мс
Разница: 225 раз
*/

Почему это важно в production?

Пример: веб-приложение с рейтингом

Если есть 100,000 рейтингов в базе:

- Bubble Sort: 40-50 сек (request timeout!)
- Collections.sort: 20 мс (нормально)

Пользователь ждет:
- Bubble Sort: ~50 сек (он закроет приложение)
- Collections.sort: 0.02 сек (незаметно)

Мой совет для интервью:

Правильный ответ:

"Время Bubble Sort зависит от размера:

- n = 1,000: ~5 мс
- n = 10,000: ~500 мс
- n = 100,000: ~50 сек

Это O(n²) сложность, поэтому время растет квадратично.

Для сравнения:
- Collections.sort (Timsort): O(n log n) = 20 мс для 100,000 элементов
- Разница: Bubble Sort в 2,500 раз медленнее

В production коде никогда не используй Bubble Sort для больших данных."

Ключевые моменты:

1. Время растет квадратично (O(n²))
2. n=10,000 это уже ~500мс (заметно)
3. n=100,000 это 40-50 сек (timeout в웹 приложении)
4. Collections.sort в 100-1000 раз быстрее
5. Используй встроенные сортировки!

Бubble Sort — это образовательный алгоритм. В реальном коде используй Arrays.sort() или Collections.sort()!