0

特定の配列をバブルソートし、配列が既にソートされている場合に実行を停止する関数を作成しました。

int sort(int *arr, int size) {
    int i, j, temp, st = 1, count = 0;
    for(i = 0; (i < size - 1) && (st == 1); i++)
    {
        st = 0;
        for(j = 0; j < size - 1; j++)
        {
            if(arr[j] < arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                st = 1;
            }
            count++;
        }
    }
   return count;
}

ご覧のとおり、size^2 の移動前に配列がソートされると、ループが壊れるはずです。

ただし、何かが間違っており、count 変数は常に size * size であり、渡した配列に関係なく、{1, 2, 3, 4, 5} でも同じ結果が得られます。

なにが問題ですか？

4

1 に答える 1

3

条件付き

if(arr[j] < arr[j + 1])

配列を降順でソートしています。したがって、それを渡すと[5, 4, 3, 2, 1]、未満の値が得られますsize*size。

外側のループの各反復は、1 つの要素を配列の最後の最後の場所に移動することに注意してください。

for(j = 0; j < size - 1 - i; j++)

走れば

#include <stdio.h>

int sort(int *arr, int size) {
    int i, j, temp, st = 1, count = 0;
    for(i = 0; (i < size - 1) && (st == 1); i++)
    {
        st = 0;
        for(j = 0; j < size - 1; j++)
        {
            if(arr[j] < arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                st = 1;
            }
            count++;
        }
    }
   return count;
}

int main(void) {
#ifdef ASCENDING
    int ar[] = { 1, 2, 3, 4, 5 };
#else
    int ar[] = { 5, 4, 3, 2, 1 };
#endif
    int i, ct = sort(ar, sizeof ar / sizeof ar[0]);
    printf("%d\n",ct);
    for(i = 0; i < (int)(sizeof ar / sizeof ar[0]); ++i) {
        printf("%d ", ar[i]);
    }
    printf("\n");
    return 0;
}

定義せずにコンパイルするASCENDINGと、出力は

4
5 4 3 2 1

したがって、配列はすでに目的どおりにソートされているため、最初の反復後に外側のループが中断されます。でコンパイルすると-DASCENDING、配列は元々昇順であり、ソートするには完全なサイクルが必要です。つまり、出力は次のようになります。

16
5 4 3 2 1

(内側のループが に対してのみ実行される場合、カウントは 10 に減らされますj < size - 1 - i)。

于 2012-11-15T19:01:23.223 に答える