Это сортировка оболочки или вставка?

Question

Я только начинаю изучать алгоритмы сортировки и нашел один онлайн. Сначала я подумал, что это была оболочка, но ему не хватает определенного интервала «k» и деления массива пополам, поэтому я не уверен, так ли это. Мое второе предположение - сортировка вставкой, но я здесь, чтобы перепроверить:

for(n = 1; n < num; n++)
{
    key = A[n];
    k = n;
    while((k > 0) && (A[k-1] > key))
    {
        A[k] = A[k-1];
        k = k-1;    
    }
    A[k] = key;
}

Также, если вы можете объяснить, почему это было бы также полезно

Answer 1

Оболочечная сортировка состоит из множества сортировок вставки, которые выполняются для подмассивов исходного массива.

Код, который вы указали, является сортировкой вставки.

Комуполучить сортировку оболочки, это будет примерно иметь for вокруг вашего кода, изменяющего h (этот пробел в сортировке оболочки) и начальный индекс подмассива и внутри, вместо того, чтобы переходить от k к k-1вы переходите от k к k+h (или k-h в зависимости от того, в каком направлении вы выполняете сортировку вставкой)

Answer 2

Я думаю, что вы правы, это очень похоже на сортировку вставки .

Этот фрагмент предполагает, что A[0] уже вставлен. Если n == 0, то проверка k > 0 завершится неудачно, и выполнение продолжится на A[k] = key;, при этом первый элемент будет сохранен в массиве.

Этот фрагмент также предполагает, что A[0:n-1] уже отсортирован. Он проверяет A[n] и начинает сканирование массива в обратном направлении, перемещаясь на одно место вперед на каждый элемент, который больше, чем исходная клавиша A[n].

Как только сканирование обнаруживает элемент, меньший или равный ключу, оно вставляет его в это место.

Answer 3

Это называется сортировкой вставок, потому что строка A[k] = key вставляет текущее значение в правильную позицию в частично отсортированном массиве.