Какая роль первого и второго цикла в сортировке пузырьком?

Question

[UID_B Nintendo]

//Вопрос в комментах помечен знаком (?)

    public void bubbleSort(){

        int in, out;
        for(out = nElements-1; out > 1; out--)// внешний цикл (обратный) это количество раз сравнений ?
            for(in = 0; in < out; in++)//внутренний цикл (прямой) это количество раз поменяется местами ?
                if(a[in] > a[in+1])// условия при котором меняются местами
                    swap(in, in+1);// меняться местами
    }

Comments

[Максим Мосейчук]

SmInc, и квадратичной сложности

[Сергей Горностаев]

В чём суть вопроса? Вы хотите, чтобы вам построчно объяснили работу этого кода?

Answer 1

[Dimonchik]

внешний цикл (обратный) это количество раз сравнений ?

это взятия каждого элемента, ты же не можешь взять не все и говорить что все отсортировано

//внутренний цикл (прямой) это количество раз поменяется местами ?

а это сравнение взятого элемента с остальными

Comments

[UID_B Nintendo]

Окей получается если у меня 10 элементов в массиве то взятие элементов будет происходить 9 раз, и с каждым разом количество сравнений будет расти вплоть до того пока количество сравнений не станет больше количества взятий. Но тогда первый цикл 9 раз возьмет, а второй 5 раз сравнит. В итоге у меня получится 9 x 5 = 45 сравнений. Это так получается ?

[Dimonchik]

ну естесственно n2, это максимальная оценка
если он отсортирован в обратном порядке - будет 99