Array element transposition algorithm

dirtydog

Let a [0: n-1] be an array with n elements, and k (0 <= k <= n-1) be a non-negative integer. Try to design an algorithm to transpose the subarray a [0: k] and a [k + 1: n-1]. Requires the algorithm to use O (n) in the worst case and only uses O (1) auxiliary space

stoneboy4000

void swap(int a[], int b[], n){
  int i=0;
  int temp; /*O(1) auxiliary space*/
  for(; i <n; i++){
    temp = a[i];
    a[i] = b[i];
    b[i] = temp;
  }
}
void f(int a[], int n, int k){
  int first = k+1; /*a[0:k] length*/
  int second = n-first; /*a[k+1:n-1]length*/
  if(first==0 || second==0)
    return;
  else if(first <= second){
    swap(a,a+first,first);
    f(a+first,second,first-1);
  }
  else{
    swap(a,a+second,second);
    f(a+second,first,first-second-1);
  }
}
Each time is divided into 3 segments: [short, long-short, (k position) short] or [short, (k position) short, long-short]
The two short and short are interchanged, and the remaining two segments recursively after the first short is correct, until long=short, you can also use a loop
Similar to subtraction to find the greatest common divisor, the worst case should be long and short, the greatest common divisor is 1

Let each recursion: a[] length L(i), swap length X(i), then:
2X(0) <L(0) = total length of the array n
2X(1) <L(1) = L(0)-X(0)
2X(i) <L(i) = L(i-1)-X(i-1) = L(0)-X(0)-X(1)-…-X(i-1)
At last:
2X(N) = L(N) = L(N-1)-X(N-1) = L(0)-X(0)-X(1)-…-X(N-1)
Let the average value of X(0) to X(N) be X, because X(0)>X(1)>…>X(N),
So L(i)=L(0)-X(0)-X(1)-…-X(i-1)<L(0)-X-X-…-X=L(0)-i*X
Adding inequalities: 2*(N+1)*X <(N+1)*L(0)-[N(N+1)/2]*X
==> (2+N/2)*X <L(0)=n So the time complexity (N*X*constant) is O(n)

aog777ys

First reverse a[0:k]
Then reverse a[k+1:n]
Finally reverse the entire array

bigfj1234

Exchange a[k+1]...a[n-1] with a[k+1-m]..a[k] (m is n-1-k, the number of the second sub-array )
Save the position of k-m to k, repeat the above operation until k<0
The maximum number of exchanges is n
void main()
{
int k1,k,m,temp,i=0;
const int n=13;
int a[n]={1,2,3,4,5,6,7,8,9,10,11,12,13};
cin>>k;

k1=k;m=n-1-k;
while(k1>0&&k1<n-1)
{
k1 = k+1-m<0? 0: k+1-m;
while(i!=m)
{
temp = a[k1+i];
a[k1+i] = a[k+1+i];
a[k+1+i] = temp;
i++;
}
k = k1-1;
i = 0;
}
}

dirtydog

It's all so good! !
But I think theaog777ysmethod is more clever! ! learned

Also, I think thebigfj1234method may have some problems
a[k+1-m] may cross the boundary, m=n-1-k
k+1-m=k+1-(n-1-k)=2(k+1)-n
If k<n/2-1, k+1-m is less than 0

hujintao

programming pearls has this example

dirtydog

TOstoneboy4000:
     There is a mistake in the algorithm you gave. The recursive function f's else statement swap(a,a+second,second);
Should be swap(a, a+first, second);
     The exchange of two shorts, the starting element of the second short is always a+k+1, ie a+first

菜鸟级高手

My approach is to cover one location
#include <stdio.h>
//a[0] is useless, a[] has n+1 elements
void cycle(int a[],int k,int n)
{
int i, j;
int tmp, cur,next;
j=cur=n;
tmp=a[cur];
for(i=0;i<k;i++)
{
for(;j>k;j-=k)
a[j]=a[j-k];
next=j+n-k;
if(next==cur)
{
a[j]=tmp;
cur--;
j=cur;
tmp=a[j];
}
else
{
a[j]=a[next];
j=next;
}
}
}
void main()
{
int a[10]={0,1,2,3,4,5,6,7,8,9};
int k;
scanf("%d",&k);
cycle(a,k,9);
for(int i=1;i<10;i++)
printf("%d\t",a[i]);
}

duxiaolhh

reverse(0, k);
reverse(k+1, n-1);
reverse(0, n-1);

stoneboy4000

It’s really wrong, hey~~~ In the end, it’s unavoidable.

The second floor is easier to understand, the total number of exchanges n/2 + n/2 = n unchanged,

The algorithm ofbigfj1234should be similar to mine, starting from the end,
The total number of exchanges is n-(the greatest common divisor of k+1 and nk-1), and the number of exchanges each time is the number of elements in the right position. When recursive to the end, the length of the array is twice the greatest common divisor. End after 1 times the number of exchanges

But one exchange is three assignment operations,
The菜鸟级高手algorithm (regardless of right or wrong, but just the idea) efficiency should be the highest, k elements are assigned n/k rotations on average, the total is about k * n/k = n assignments, but the remainder of n/k is a problem. It is still very annoying to be clear, if n is a multiple of k, it is simple
In short, if the efficiency is high, understanding is troublesome