5

一定サイズ (実際のサイズ = 20) の配列があり、重複が許可されています。たとえば、次のようになります。

1 2 2 3 3 4 5 6 7 8 9

ちょうど 1 つの要素が更新されるようになりました。

1 5 2 3 3 4 5 6 7 8 9

この配列に頼る必要があります。バブルソートを使用する必要がありますか？

更新私が書いたものを呼び出す方法がわかりません。しかし、より速くソートすることは不可能だと思います。コメント大歓迎です！

    // array is already almost sorted and INCREASING, element at pos need to be inserted to the right place
    private void SortQuotes(List<Quote> quoteList, int pos)
    {
        var quoteToMove = quoteList[pos];
        if (pos == 0 || quoteList[pos - 1].Price < quoteToMove.Price)
        {
            MoveElementsDown(quoteList, pos);
        } else if (pos == quoteList.Count - 1 || quoteList[pos + 1].Price > quoteToMove.Price)
        {
            MoveElementsUp(quoteList, pos);
        }
    }

    private void MoveElementsDown(List<Quote> quoteList, int pos)
    {
        var quoteToInsert = quoteList[pos];
        var price = quoteToInsert.Price;
        for (int i = pos - 1; i >= 0; i--)
        {
            var nextQuote = quoteList[i];
            if (nextQuote.Price > price)
            {
                quoteList[i + 1] = quoteList[i];
                if (i == 0)   // last element
                {
                    quoteList[i] = quoteToInsert;
                }
            }
            else
            {
                quoteList[i + 1] = quoteToInsert;
                break;
            }
        }
    }

    private void MoveElementsUp(List<Quote> quoteList, int pos)
    {
        var quoteToInsert = quoteList[pos];
        var price = quoteToInsert.Price;
        for (int i = pos + 1; i < quoteList.Count; i++)
        {
            var nextQuote = quoteList[i];
            if (nextQuote.Price < price)
            {
                quoteList[i - 1] = quoteList[i];
                if (i == quoteList.Count - 1)   // last element
                {
                    quoteList[i] = quoteToInsert;
                }
            }
            else
            {
                quoteList[i - 1] = quoteToInsert;
                break;
            }
        }
    }

更新された私は、どの要素が奇数であるかを知っています。つまり、その位置がわかっています!

4

8 に答える 8

1

このソリューションは、奇数要素の正しい位置が見つかるまで、各要素を1つずつシフトします。最初のステップですでに上書きされているため、一時変数「h」に保存されてから、最終位置に書き込まれます。最小限の比較とシフト操作が必要です。

 static void MoveOddElementToRightPosition(int[] a, int oddPosition)
 {
   int h = a[oddPosition];
   int i;
   if (h > a[oddPosition + 1])
     for (i = oddPosition; i < a.Count()-1 && a[i+1] <= h; i++)
        a[i] = a[i+1];
   else
     for (i = oddPosition; i > 0 && a[i-1] >= h; i--)
        a[i] = a[i - 1];
   a[i] = h;
 }
于 2012-12-08T18:49:37.380 に答える
0
  • 要素をすばやく置き換えることに関心がある場合は、たとえばJavaのTreeSetのように、削除と挿入が高速な構造を使用することもできます。これは理論的にはO（log（n））を意味しますが、20個の要素の配列を操作するだけでは、それだけの価値はないかもしれません。
  • 1から9の数値を使用する例のように、すべての異なる要素のセットが有限である場合、O（1）に解があります。ソートされたリストを作成する代わりに、要素の出現回数を含む配列を保持するだけです。
  • それでもすべてを配列に保持したい場合、最速の方法はこれです
    1. O（log（n））で、二分法によって削除する要素の位置Aを見つけます。
    2. 新しい要素が同じように終わる位置Bを見つけます。より正確には、Bは、すべてのk>Bに対してnew_element<a[k]である最小のインデックスです。
    3. A <Bの場合、A + 1とBの間のすべての要素を左側に移動し、新しい要素を位置Bに設定します。B> Aの場合、同じことを行いますが、右側に配置します。現在、このステップはO（n）にありますが、ロジックはなく、メモリを移動しているだけです。Cでは、これにmemmoveを使用し、高度に最適化されていますが、Javaに相当するものはわかりません。
于 2012-12-08T13:30:53.993 に答える
0

It can be done in O(n). 要素がわからない場合は、O(n) で要素を検索し、各要素を比較して交換するだけで、O(n) が必要になります。したがって、合計 2n は O(n) を意味します。変更された要素がわかっている場合は、各要素を比較して交換します。

于 2012-12-08T12:02:11.953 に答える
0

これは、単純な C での単純な実装ですfprintf(stderr, ...。テスト後に削除します。ITEM は、比較機能があれば何でも構いません。それ以外の場合: ITEM へのポインターを使用します (さらに、余分な sizeofelem 引数、ala qsort を追加することもできます)。

#include <stdio.h>
#include <string.h>

typedef int ITEM;

int item_cmp(ITEM one, ITEM two);
unsigned one_bubble( ITEM *arr, unsigned cnt, unsigned hot , int (*cmp)(ITEM,ITEM) );

int item_cmp(ITEM one, ITEM two)
{
fprintf(stderr,"Cmp= %u to %u: %d\n", one, two, one-two);
if (one > two) return 1;
else if (one < two) return -1;
else return 0;
}

unsigned one_bubble( ITEM *arr, unsigned cnt, unsigned hot , int (*cmp)(ITEM,ITEM) )
{
unsigned goal = cnt;
int diff;
ITEM temp;

        /* hot element should move to the left */
if (hot > 0 && (diff=cmp( arr[hot-1], arr[hot])) > 0) {
        /* Find place to insert (this could be a binary search) */
        for (goal= hot; goal-- > 0; ) {
                diff=cmp( arr[goal], arr[hot]);
                if (diff <= 0) break;
                }
        goal++;
        fprintf(stderr,"Move %u LEFT to %u\n", hot, goal);
        if (goal==hot) return hot;
        temp = arr[hot];
                /* shift right */
        fprintf(stderr,"memmove(%u,%u,%u)\n", goal+1, goal, (hot-goal) );
        memmove(arr+goal+1, arr+goal, (hot-goal) *sizeof temp);
        arr[goal] = temp;
        return goal; /* new position */
        }
        /* hot element should move to the right */
else if (hot < cnt-1 && (diff=cmp( arr[hot], arr[hot+1])) > 0) {
        /* Find place to insert (this could be a binary search) */
        for (goal= hot+1; goal < cnt; goal++ ) {
                diff=cmp( arr[hot], arr[goal]);
                if (diff <= 0) break;
                }
        goal--;
        fprintf(stderr,"Move %u RIGHT to %u\n", hot, goal);
        if (goal==hot) return hot;
        temp = arr[hot];
                /* shift left */
        fprintf(stderr,"memmove(%u,%u,%u)\n", hot, hot+1, (goal-hot) );
        memmove(arr+hot, arr+hot+1, (goal-hot) *sizeof temp);
        arr[goal] = temp;
        return goal; /* new position */
        }
fprintf(stderr,"Diff=%d Move %u Not to %u\n", diff, hot, goal);
return hot;
}

ITEM array[10] = { 1,10,2,3,4,5,6,7,8,9,};
#define HOT_POS 1
int main(void)
{
unsigned idx;

idx = one_bubble(array, 10, HOT_POS, item_cmp);

printf("%u-> %u\n", HOT_POS, idx );

for (idx = 0; idx < 10; idx++) {
        printf("%u: %u\n", idx, array[idx] );
        }

return 0;
}
于 2012-12-08T19:08:29.063 に答える
0

再度並べ替える必要はありません。

1 つの要素のみが変更されます。したがって、リストを調べて、変更された番号を適切な場所に配置するだけです。これは O(n) complex になります。

int a[] = {1, 5, 2, 3, 3, 4, 5, 6, 7, 8, 9};
int count = 0;

//find the odd element
for(int jj=1; jj< a.length; jj++){
    if(a[jj] < a[count])
        break;
    else count++;
}
System.out.println(" Odd position "  + count);

//put odd element to proper position
for(int k= count+1; k<a.length; k++){
    if(a[count] > a[k]){
        int t = a[count];
        a[count] = a[k];
        a[k] = t;
        count++;
    }
}

上記は、特定の入力に対してテストされた作業コードです。楽しみ。

于 2012-12-08T12:42:20.957 に答える
0

配列が小さいため、小さな配列の場合、挿入ソートには約 ~O(n) の時間がかかります。1 つの値を更新するだけの場合、挿入ソートは可能な限り最良の方法で目的を達成する必要があります。

于 2012-12-08T11:49:30.287 に答える
0

最後の要素を前面に出す必要がある場合、バブルソートは n^2 時間を使用します。挿入ソートを使用します。

于 2012-12-08T10:22:12.200 に答える
0

この場合、バブルソートは最大 20 回の比較でまったく問題ありません。

しかし、二分探索で新しい位置を見つけるのは O(log(n)) で、この場合は 5 です。
やや高速です。最後のビットの奇妙な速度が必要な場合は、バイナリ検索を使用してください。それ以外の場合は、バブル ソートを使用できます。

于 2012-12-08T16:26:42.550 に答える