2

これら 2 つのアルゴリズムを組み合わせるのに問題があります。Binary Search要素を配列に挿入する必要があるインデックスを返すように変更するように依頼されました。Binary Insertion Sort次に、 myBinary Searchを使用してランダムに生成された の配列をソートするを実装するように依頼されましたints。

私Binary Searchの作品は想定どおりに動作し、単独でテストするたびに正しいインデックスを返します。私はBinary Insertion Sortそれがどのように機能するかの感触をつかむために書き、それも機能するようにしました. 2つを組み合わせるとすぐに壊れます。それらを一緒に間違って実装していることはわかっていますが、問題がどこにあるのかわかりません。

これが私が持っているものです：

public class Assignment3
{
    public static void main(String[] args)
    {   
        int[] binary = { 1, 7, 4, 9, 10, 2, 6, 12, 3, 8, 5 };

        ModifiedBinaryInsertionSort(binary);

    }

    static int ModifiedBinarySearch(int[] theArray, int theElement)
    {
        int leftIndex = 0;
        int rightIndex = theArray.length - 1;
        int middleIndex = 0;

        while(leftIndex <= rightIndex)
        {
            middleIndex = (leftIndex + rightIndex) / 2;

            if (theElement == theArray[middleIndex])
                return middleIndex;
            else if (theElement < theArray[middleIndex])
                rightIndex = middleIndex - 1;
            else
                leftIndex = middleIndex + 1;
        }

        return middleIndex - 1;
    }

    static void ModifiedBinaryInsertionSort(int[] theArray)
    {
        int i = 0;
        int[] returnArray = new int[theArray.length + 1];

        for(i = 0; i < theArray.length; i++)
        {
            returnArray[ModifiedBinarySearch(theArray, theArray[i])] = theArray[i];
        }

        for(i = 0; i < theArray.length; i++)
        {
            System.out.print(returnArray[i] + " ");
        }
    }
}

これを実行したときに得られる戻り値は です1 0 0 0 0 2 0 0 3 5 12。助言がありますか？

更新: ModifiedBinaryInsertionSort を更新しました

static void ModifiedBinaryInsertionSort(int[] theArray)
{
    int index = 0;
    int element = 0;
    int[] returnArray = new int[theArray.length];

    for (int i = 1; i < theArray.lenght - 1; i++)
    {
        element = theArray[i];
        index = ModifiedBinarySearch(theArray, 0, i, element);
        returnArray[i] = element;

        while (index >= 0 && theArray[index] > element)
        {
            theArray[index + 1] = theArray[index];
            index = index - 1;
        }
        returnArray[index + 1] = element;
    }
}
4

4 に答える 4

1

挿入ソートがどのように機能するかというと、新しい空の配列 B を作成し、ソートされていない配列 A の各要素に対して、これまでに構築された B のセクションをバイナリ検索し (左から右へ)、すべての要素をB の場所の右側に 1 つの右側を選択し、要素を挿入します。そのため、B のフルサイズになり、A のすべてが含まれるまで、常に並べ替えられた配列を B に構築します。

2つのこと：

1 つ目は、バイナリ検索で int startOfArray と int endOfArray を取得できる必要があり、これら 2 つのポイント間でのみバイナリ検索を行うことです。これにより、実際にソートされた配列である配列 B の部分のみを考慮するようにすることができます。

2 つ目は、挿入する前に、作成したギャップに挿入する前に、すべての要素を 1 つ右に移動する必要があることです。

于 2013-06-06T02:59:28.423 に答える
1

これが古いことは承知していますが、質問に対する答えは、おそらく少し直感に反して、「Middleindex - 1」がすべての場合に挿入インデックスになるわけではないということです。紙の上でいくつかのケースを実行すると、問題が明らかになるはずです。

この問題を解決する拡張メソッドがあります。これを状況に適用するには、既存のリストを反復処理して、空の開始リストに挿入します。

public static void BinaryInsert<TItem, TKey>(this IList<TItem> list, TItem item, Func<TItem, TKey> sortfFunc)
        where TKey : IComparable
    {
        if (list == null)
            throw new ArgumentNullException("list");

        int min = 0;
        int max = list.Count - 1;
        int index = 0;

        TKey insertKey = sortfFunc(item);

        while (min <= max)
        {
            index = (max + min) >> 1;

            TItem value = list[index];
            TKey compKey = sortfFunc(value);
            int result = compKey.CompareTo(insertKey);

            if (result == 0)
                break;
            if (result > 0)
                max = index - 1;
            else
                min = index + 1;
        }

        if (index <= 0)
            index = 0;
        else if (index >= list.Count)
            index = list.Count;
        else
            if (sortfFunc(list[index]).CompareTo(insertKey) < 0)
                ++index;

        list.Insert(index, item);
    }
于 2014-10-18T17:58:25.190 に答える