Алгоритм сортировки с бесконечными свопами

Question

Мне нужна помощь со следующей проблемой, которую я нашел в учебнике.

sort (array[], nr_of_item) 
{ 
    while(true) 
    i:=value from an n-sided fair dice roll 
    j:=value from an n-sided fair dice roll 
    if (i > j) 
     swap i and j 
    if (array[i] > array [j]) 
     swap array[i] and array[j] 
    end while 
} 

Теперь он говорит, что не описывает правильный алгоритм. Но тогда они говорят:

Через некоторое время массив должен быть отсортирован и доказать, что количество сравнений для сортировки массива равно O (n^3), если вход не сортирован.

Еще один вопрос:

проверить, если алгоритм сортировки массива в O (п)

Я действительно не могу понять, как вы могли бы доказать это из-за хаотичности I и J ,

Answer 1

i и j относится к индексу, а j всегда скорректирован так, чтобы быть большим из двух. Это означает, что элемент, указанный индексом i, обозначенный как x, будет располагаться слева от элемента с индексом j, обозначенным как y.

Затем поменять элемент, только если y и x являются несортированными, что означает x больше y и положение их индексация, находятся слева от y, и, следовательно, выходит из строя. Это гарантирует, что функция только приближается (не дальше) к отсортированному состоянию.

Теперь, что касается сложности, представьте себе сортировку пузырьков, которая предназначена для итерации по массиву, в отличие от произвольного выбора. Это имеет сложность n-квадрата. Однако здесь есть что-то еще. Вы произвольно выбираете два элемента и, следовательно, n-выбираете-1 раз сложность сортировки пузырьков, которая становится n-кубической.

Каждый вызов функции выполняет два сравнения, в частности 2. Поэтому сложность представляет собой n-кубическое время 2, которое можно обозначить с помощью обозначения большого О, как n-cubed.