Вопросы алгоритма Bubblesort

Question

У меня есть этот вопрос, о котором я очень смущен, работал над ним какое-то время, и я не могу найти никакой помощи.

input a: array [1 .. n] of integer; n : integer; 
temp i, j : integer; 
j <-- n; 
while j ≥ 1 
    do I <-- 1; 
     while i ˂ j 
      do 
       if a[i] ˃ a[j] then swap a[i], a[j]; 
       i <-- i + 1; 
      od; 
     j < j – 1; 
    od 

1. Будет ли этот алгоритм прекращается?

   У меня есть мой ответ, так как нет, потому что [i] и [j] никогда не будут меняться.

2. Какова наихудшая временная сложность этого алгоритма в O-нотации в зависимости от размера проблемы сортировки?

3. Предпосылкой этого алгоритма является значение истины TRUE. Нужное постусловие алгоритма: for i ˂ j, a[i] ˂ a[j], for i = 1, 2, . . . , n-1, j = 2, . . . , n

Найти два инварианта цикла для внутренних и внешних контуров, которые, по вашему мнению, приведут к желаемому постусловию, если и когда алгоритм завершается.

Любая помощь будет оценена! Я хочу это понять!

Answer 1

Я рекомендую вам читать это первым: http://en.wikipedia.org/wiki/Bubble_sort

О вопросах.

1) Да, алгоритм определенно закончится. Он будет делать двойную петлю и закончить.

2) Худшая сложность - O (n^2).

3) Изучите и запишите: http://en.wikipedia.org/wiki/Loop_invariant. SO не будет делать всю домашнюю работу.