1

したがって、整数の配列を並べ替えて、ある整数よりも小さい数値がscanf左側に、このセット変数が中央に、大きい数値が右側に配置されるようにする必要があります。左右の部分をカバーしましたが、変数が真ん中にあるようにする方法がわかりません..何かアイデアはありますか?

#include <stdio.h>
int main()
{
    int y, i, k, temp;
    printf("give integer\n");
    scanf("%d", &y);
    int x[10] = {5,8,9,4,2,3,2,4,5,6};
    i=0;
    k=1;
    while(i<10)
    {
        while(x[i]>y&&k<10)
        {
            temp=x[k];
            x[k]=x[i];
            x[i]=temp;
            k++;
        }    

        i++;
        k=i+1;
    }


    for(i=0; i<10; i++)
    {
        printf("x[%d]=%d\n", i, x[i]);
    }
}

入力/出力の例:

input: x[i]={5,2,1,6,7,3,2,4,5,6}    y=5
output: x[i]={2,1,4,3,2,5,5,7,6,6}
4

4 に答える 4

1

クイックソート アルゴリズムのように、「パーティション」に似たアルゴリズムを探しています。アイデアは、2 つのインデックスを持つことでiあり、jwhereiは配列を反復処理するために使用されjますが、 は より大きいか等しい最初のアイテムのインデックスですy。

その最初のループの後、左側よりも小さい数値とy右側の他の数値があります。ただし、実際には、等しい値をグループ化し、右側にあるyよりも大きい数だけを使用する必要があります。yだから私は間隔[j、n]で同じことをすることを提案していますが、今はそれが等しいときにも動いています。

// Function to exchange the values of 2 integer variables.
void swap(int *a, int *b) {
    int buf = *a;
    *a = *b;
    *b = buf;
}

// Do the job, in place.
void partition(int *tab, int n, int y) {
    // This first part will move every values strictly lesser than y on the left. But the right part could be "6 7 5 8" with y=5. On the right side, numbers are greater or equal to `y`.
    int j = 0; // j is the index of the position of the first item greater or equal to y.
    int i;
    for (i = 0; i < n; i++) {
        if (tab[i] < y) {
        // We found a number lesser than y, we swap it with the first item that is greater or equal to `y`.
            swap(&tab[i], &tab[j]);
            j++; // Now the position of the first value greater or equal to y is the next one.
        }
    }

    // Basically the same idea on the right part of the array.
    for (i = j; i < n; i++) {
        if (tab[i] <= y) {
            swap(&tab[i], &tab[j]);
            j++;
        }
    }
}

int main() {
    int y;
    printf("give integer\n");
    scanf("%d", &y);
    int x[10] = {5,8,9,4,2,3,2,4,5,6};
    partition(x, 10, y);

    int i;
    for(i=0; i<10; i++)
    {
        printf("x[%d]=%d\n", i, x[i]);
    }

    return 0;
}

このコードは、 とx = {5,2,1,6,7,3,2,4,5,6};で次のようになりy = 5ます。

x[0]=2
x[1]=1
x[2]=3
x[3]=2
x[4]=4
x[5]=5
x[6]=5
x[7]=7
x[8]=6
x[9]=6

最初の 5 つの要素は 5 未満であり、他の要素は 5 以上です。

于 2013-10-27T19:07:35.980 に答える
1

自分でこれを処理したい場合の単純なアルゴリズム:

  1. 配列全体を として[min..y][y+1..max]分割し、分割された場所をメモします。
  2. 最初の部分のみを として再分割し[min..y-1][y..y]ます。

配列が分割され[min..y-1][y..y][y+1..max]ます。

最も簡単なのは、分割を行い、分割の位置を返す partition_helper 関数を使用することです。次に、プライマリ パーティション関数は、正しい引数を使用してこの関数を 2 回呼び出します。

他の方法で分割することもできます。[min..y-1][y..max]最初に、最後の部分を として再分割し[y..y][y+1..max]ます。最終結果は同じになります。

于 2013-10-27T20:52:40.870 に答える