Care sunt diferențele dintre algoritmii de sortare rapidă și de sortare cu bule în ceea ce privește implementarea și eficiența lor?

Быстрая сортировка (QuickSort) и пузырьковая сортировка (Bubble Sort) существенно отличаются по реализации и эффективности.

Пузырьковая сортировка:

• Простая для понимания и реализации.
• Работает путём многократного прохода по массиву, сравнивая соседние элементы и меняя их местами, если они идут в неправильном порядке.
• В худшем и среднем случае имеет временную сложность O(n²), что делает её неэффективной для больших массивов.
• Использует мало дополнительной памяти (in-place).

Быстрая сортировка:

• Использует стратегию "разделяй и властвуй".
• Выбирает опорный элемент (pivot), делит массив на части с элементами меньше и больше опорного, затем рекурсивно сортирует эти части.
• В среднем работает за O(n log n), что значительно быстрее пузырьковой сортировки.
• В худшем случае (например, если массив уже отсортирован и выбран плохой pivot) может работать за O(n²), но это редко и можно минимизировать выбором случайного pivot.
• Требует дополнительной памяти для рекурсии.

Пример пузырьковой сортировки на Java:

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        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;
            }
        }
    }
}

Пример быстрой сортировки на Java:

void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

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