(C言語)配列の特定の要素より前の要素を後ろに移動するプログラムの記述方法

Question

配列の特定の要素より前の要素を後ろに移動するプログラムの記述したいと考えています．

例えば，
x = [1,5,4,3,2,6]
という配列があった時に，ある要素を探し出して，それよりも前の要素を後ろに移動させたいです．

ある要素が4だった場合は，4よりも前の要素である[1,5]を後ろに移動させ，
x = [4,3,2,6,1,5]
という順番に入れ替えたいです．

このようなプログラムの記述方法を教えていただきたいです．

Comments

[jimbe]

アルゴリズムの書籍等を調べたりはされていないのでしょうか。

[ppaul]

x = [1,5,4,3,4,6]で、ある要素が4だった場合は、どうしたいのでしょう？

Answer 1

1234AB を入れ替えて AB1234 にするには

1. 1234 と AB をそれぞれ反転する 4321BA
2. (1)全体を反転する AB1234

はい、できあがり。

#include <stdio.h>

// x[first～last-1] を反転する
void reverse(int x[], int first, int last) {
  while ( first < last ) {
    --last;
    int tmp = x[first];
    x[first] = x[last];
    x[last] = tmp;
    ++first;
  }
}

// x[first～mid-1] と x[mid～last-1] を入れ替える
void rotate(int x[], int first, int mid, int last) {
  reverse(x, first, mid);
  reverse(x, mid, last);
  reverse(x, first, last);
}

// x[0～n-1]をプリントする
void print(int x[], int n) {
  for ( int i = 0; i < n; ++i )
    printf("%d ", x[i]);
  printf("\n");
}

int main() {
  int x[6] = { 1,5,4,3,2,6 };
  print(x,6);
  rotate(x, 0, 2, 6);
  print(x,6);
  return 0;
}

Answer 2

別の配列を使わずにやってみました。

#include <stdio.h>  // printf, putchar

void reverse(int x[], int i, int j)
{
	for (int t; i < --j; i++)
		t = x[i], x[i] = x[j], x[j] = t;
}

void f(int x[], int n, int k)
{
	for (int i = 0; i < n; i++)
		if (x[i] == k) {
			reverse(x, 0, i);
			reverse(x, i, n);
			reverse(x, 0, n);
			return;
		}
}

int main(void)
{
	int x[] = { 1, 5, 4, 3, 2, 6 };
	int n = sizeof x / sizeof *x;
	f(x, n, 4);
	for (int i = 0; i < n; i++) printf(" %d", x[i]);
	putchar('\n');
}

もちろん、やり方はいくつでもあります。
他のやり方も考えてみてください。

Answer 3

バブルソートの動きを模したり、前(対象を含まない)を反転・後ろ(対象を含む)を反転・全体を反転 等で出来ます。

Answer 4

まず、前提が違います。プログラミングは「こう書けばいい」というものではありません。
ロジックを考えるのです。

プログラミングは簡単に言えば『現実世界のシミュレーション』です。

なので、C言語で~とかは置いといて、現実世界で考えてみてください。

つまり、

[依頼]

ある数列anと対象データxを渡すので、あなたはanの中にあるxの値よりも前にある数字すべて後ろに持ってきてbnを作る処理をしてください。

[例1]
an = { 1, 2, 3, 4, 5 }
x  = 2
↓
bn = { 2, 3, 4, 5, 1 }

[例2]
an = { 1, 2, 3, 5, 6 }
x  = 3
↓
bn = { 3, 5, 6, 1, 2 }

のようなものですかね。

私なら、

[Flow 1]
1. xの値がある場所を調べる
2. (1)でわかった場所より一個前までの数字群を後ろに持ってくる

のような感じにします。

で、方法は今思いつくものだと、2種類ですかね。

一つ目は、『xを基準点として二つに分割して考えて、後ろ -> 前の順番にする』。
二つ目は、『xが出るまで後ろに追加していく』。

たとえば、an = { 1, 2, 3, 5, 6 }, x = 3 であれば、

xの値がある場所は (初項から考えると) 第3項ですね。
そうすると、前 = 初項第2項、後ろ = 第4項第5項 ですね。
そして、最終的な並びは bn = { 3, 5, 6, 1, 2 } ですね。

この場合は規則性を見付けると楽です。

an から bn の変化を見ると、依頼にあるようなものとは別に、『移動した値もすべて元の並びになっている』ですね。
*bn = { 3, 6, 5, 2, 1 } のようにでたらめに並んでいるわけではありません。

ということは、

cn = { 1, 2 }, dn = { 5, 6 }, 基準 = 3 という風になっていますね。

で、出てくる数字を見ると、基準 + dn + cn となっています。

ということは、まず基準値と 後ろにある dn = { 5, 6 } を先端から末尾まで別の数列として定義する。

en = { {3}, {5, 6} }

そして、さらに cnを追加する。

en = { {3}, {5, 6}, {1, 2} }

そして最後に、enをbnと読み替えて答えとする。

と考えるとどうでしょうか。

二つ目のやつは、単純に、

1. 先頭にxが出るまで繰り返す
     1.1. その位置のデータを取り出して元のデータを削除
     1.2. (1.1)で得たデータを末尾に追加

的なロジックになるかなと。

ただ、この二つ目の方法はC言語でやるとなると少々メンドクサイ気がします。

後はこういう考え方をC言語とかのようなやつで書き下して、エラーが出たらエラーに対処する。
これだけです。

Answer 5

同じ配列を使うとめんどくさいので、別の配列を用意して、見つかったところから順番に1つずつ別の配列にコピーしていけばいいと思います。

Answer 6

c.c

#include <stdio.h>  // printf, putchar

// 配列の内容を表示する
void show_array(int *ary, int size) {
  for (int i = 0; i < size; i++) {
    printf(" %d", ary[i]);
  }
  putchar('\n');
}

// 配列を左に１つ回転させる
void shift_left(int * ary, int size) {
  if (size <= 0) {
    return;
  }

  int x = ary[0];
  for (int i = 0; i < size -1; i++) {
    ary[i] = ary[i + 1];
  }
  ary[size - 1] = x;
}

// 配列を左に count 回, 回転させる
void shift_left_multi(int * ary, int size, int count) {
  for (int i = 0; i < count; i++) {
    shift_left(ary, size);
  }
}

// 配列中の x に位置を調べる
int find_x(int * ary, int size, int x) {
  for (int i = 0; i < size; i++) {
    if (ary[i] == x) {
      return i; // find
    }
  }
  return -1;  // not find
}

int main(void) {
  int x[] = { 1, 5, 4, 3, 2, 6 };
  int size = sizeof(x) / sizeof(int);
  show_array(x, size);

  // 4 を指定
  int p = find_x(x, size, 4);
  shift_left_multi(x, size, p);
  show_array(x, size);

  // 1 を指定
  p = find_x(x, size, 1);
  shift_left_multi(x, size, p);
  show_array(x, size);

  // 配列に存在しない値を指定したときは、変化しない
  p = find_x(x, size, 9);
  shift_left_multi(x, size, p);
  show_array(x, size);
}

実行例