Прямая вставка, как считать свопы?

Question

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

[4 2 1 3] 

Итак, когда алгоритм умирает, он должен работать как этот

1. [2 4 1 3] 
2. [1 2 4 3] 
3. [1 2 3 4] 

Может кто-то помочь мне считать свопы для каждого шага? С моей точки зрения его, вероятно, 1) 1 своп, 2) 2 свопа, 3) 1 своп. Это верно? благодаря

Алгоритм:

for(i=1; i<N; i++) 
{ 
    x = p[i]; 
    j = i -1; 
    while(x<p[j] && j>=0) 
    { 
     p[j+1] = p[j]; 
     j = j-1; 
    } 
    p[j+1] = x; 
} 

Answer 1

Во-первых, этот алгоритм является новым (его точно не вставка рода, но очень близко к нему)

Теперь количество свопы, что этот алгоритм делает это 0 , Он просто выполняет задания, без свопов. Если вы вызываете число присвоений внутри while как swaps, то да, вы правы. И если вы хотите это проверить, просто отредактируйте свой код:

for(i=1; i<N; i++) 
{ 
    x = p[i]; 
    j = i -1; 
    int n=0; 
    while(x<p[j] && j>=0) 
    { 
     p[j+1] = p[j]; 
     j = j-1; 
     n++; 
    } 
    //output n, looks like c so 
    printf("%d\n",n); 
    p[j+1] = x; 
}