Рубрики

Алгоритмы | Сортировка | Вопрос 10

Какова наилучшая временная сложность пузырьковой сортировки?

(А) N ^ 2
(B) NlogN
(С) N
(D) N (logN) ^ 2

Ответ: (с)
Объяснение: Пузырьковая сортировка в лучшем случае, если входные данные отсортированы. т.е. если входные данные отсортированы в том же порядке, что и ожидаемый результат. Это может быть достигнуто с помощью одной логической переменной. Булева переменная используется для проверки, поменяются ли значения хотя бы один раз во внутреннем цикле.
Рассмотрим следующий фрагмент кода:

int main()

{   

    int arr[] = {10, 20, 30, 40, 50}, i, j, isSwapped;

    int n = sizeof(arr) / sizeof(*arr);

    isSwapped = 1;

    for(i = 0; i < n - 1 && isSwapped; ++i)

    {

        isSwapped = 0;

        for(j = 0; j < n - i - 1; ++j)

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

            {

                swap(&arr[j], &arr[j + 1]);

                isSwapped = 1;

            }

    }

    for(i = 0; i < n; ++i)

        printf("%d ", arr[i]);

    return 0;

}

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

Рекомендуемые посты:

Алгоритмы | Сортировка | Вопрос 10

0.00 (0%) 0 votes