сортировка вставкой во введении к алгоритму

Question

в Введение Алгоритм 2-е издание, я нашел вставки сортировки псевдокод

INSERTION-SORT(A) 
1 for j <- 2 to length[A] 
2  do key <- A[j] 
3   //Insert A[j] into the sorted sequence A[1 □ j - 1]. 
4   i <- j - 1 
5   while i > 0 and A[i] > key 
6   do A[i+1] <- A[i] 
7    i <- i -1 
8   A[i + 1] <- key 

, но я не могу понять, как своп работает здесь.

Я думаю, что она нуждается в операции своп, как это

INSERTION-SORT(A) 
1 for j <- 2 to length[A] 
2  do key <- A[j] 
3   //Insert A[j] into the sorted sequence A[1 □ j - 1]. 
4   i <- j - 1 
5   while i > 0 and A[i] > key 
6   do temp <- A[i+1] 
7    A[i+1] <- A[i] 
8    A[i] <- temp 
9    i <- i -1 
10   A[i + 1] <- key 

я получил что-то не так? , пожалуйста, помогите

Answer 1

Что происходит в сортировке вставки не является свопом.

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

Answer 2

, но я не могу понять, как здесь работает своп.

Нет, это не так.

Значение уже сохранено в начале.

Это экономит j, а затем сдвигает все остальные элементы до тех пор, пока не найдет подходящее место

Answer 3

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

Сложная часть об этом заключалась в том, что псевдокод использует нотации на основе 1 в отличие от большинства языков программирования!

#include <stdio.h> 

int main(void) 
{ 
    int A[] = { 50, 20, 10, 40, 60, 30 }; 
    int j, key, len, i; 
    len = (sizeof(A))/(sizeof(A[0])); 

    for (j = 1; j < 6; j++) { <-- Change here 
     key = A[j]; 
     // Insert key into the sorted sequence A[1 .. j - 1]. 
     i = j - 1; 
     while (i >= 0 && A[i] > key) { <-- Change here 
      A[i + 1] = A[i]; 
      i--; 
     } 
     A[i + 1] = key; 
    } 

    for (int z = 0; z < len; z++) { 
     printf("%d ", A[z]); 
    } 
    printf("\n"); 
} 

Answer 4

Код выполняет «multi-swap», точнее вращение k элементов по одному положению, на месте. Это занимает одну вспомогательную переменную key, как и обмен.