Вставка Сортировка Алгоритм В месте и петли вариант

Question

Часть 1
Я знаю, что QuickSort можно использовать «на месте», но может кто-нибудь объяснить мне, как вставки рода алгоритм делает это с помощью «на месте».

Из моего понимания:

вставки Сортировка начинается с первого значения и сравнивает его к следующему значению, если это значение меньше нашего значения они меняются местами. Мы продолжаем это рекурсивно. (Краткое объяснение)

Так вы бы сказали, что это «на месте», потому что мы не создаем новый массив для этого, а просто сравниваем два элемента в массиве?

Если мое понимание было неправильным, то кто-то может объяснить алгоритм для вставки сортировки на месте.

Часть 2
Кроме того, как бы я использовать вставки рода, чтобы проиллюстрировать идею цикла инвариантного?

Я знаю, что инвариант цикла является условием, которое сразу истинно до и после каждой итерации цикла, но я не уверен, как это будет относиться к сортировке вставки.

Answer 1

Как и Thorsten, упомянутый в разделе комментариев, вы описали сортировку пузырьков. Модифицированный из Wikipedia, псевдокода для пузырьковой сортировки представлена ​​следующим образом:

procedure bubbleSort(A : list of sortable items) 
    n = length(A) 
    for i = 1 to n inclusive do // Outer Loop 
    for j = 1 to n-1-i inclusive do 
     /* if this pair is out of order */ 
     if A[j] > A[j+1] then 
     swap(A[j], A[j+1]) 
     end if 
    end for 
    end for 
end procedure 

Петля инвариантна в пузырьковой сортировке (для внешнего цикла) будет то, что, после каждой итерации цикла, всего массива до текущего значения i будет сортироваться. Это связано с тем, что каждый раз, когда он достигает внешнего цикла, он будет проходить через все итерации внутреннего цикла (от i до n-1), найдя там минимальный элемент и заменяя этот элемент на i-й.

Bubble sort, действительно, на месте, поскольку вся сортировка происходит внутри самого исходного массива и не требует отдельного внешнего массива.

Edit- Теперь на сортировку вставками:

Псевдо код выглядит следующим образом (все града Wikipedia):

for i = 1 to length(A) - 1 
    x = A[i] 
    j = i 
    while j > 0 and A[j-1] > x 
     A[j] = A[j-1] 
     j = j - 1 
    end while 
    A[j] = x[3] 
end for 

Здесь на каждом шагу, что происходит в том, что для каждого элемента, вы выберите подходящее место для его вставки в массив, т. е. вы вставляете его сразу после первого элемента, который меньше, чем в массиве. Немного более подробно, что делает внутренний цикл, это то, что он перемещает элементы вправо, пока не столкнется с элементом, меньшим, чем рассматриваемый элемент, после чего вы вставляете элемент сразу после меньшего элемента. Это будет означать, что каждый элемент до тех пор, пока вышеупомянутый элемент не будет отсортирован. внешний цикл гарантирует, что это делается для всех элементов в массиве, а это означает, что к моменту завершения внешнего цикла массив сортируется.

Инвариант цикла для внешнего контура, как и раньше, после i-й итерации будет отсортирован по всем элементам до текущего i. Однако перед i-м вступлением все элементы до i-1 будут отсортированы.

Алгоритм сортировки вставки не требует внешнего массива для сортировки. Более конкретно, все операции выполняются на самом массиве (за исключением одной переменной, которую нам нужно сохранить элемент, который мы сейчас пытаемся вставить в соответствующее место), и не используются внешние массивы - копирование из этого массива отсутствует к другому, например. Таким образом, сложность пространства, требуемая алгоритмом (исключая, конечно, пространство, которое занимает сам массив), будет O (1), в отличие от размера массива, а вид - это место, очень похоже на пузырь.