0

そのため、配列の中央要素としてピボットを使用してクイックソートアルゴリズムを作成する必要がありました。私はそれをすべてうまくやった。しかし、サブリストのいずれかが20未満に減少したときに、insertionSortを使用してサブリストをソートするように、quickSortアルゴリズムを変更するように求められます。

私はそれが機能しているようでした。配列を完全にコンパイルしてソートしますが、変更されたクイックソートと通常のクイックソートのCPU時間の違いが異なるため、正しく実行したかどうかはわかりません。私の不確実性は、再帰メソッドrecQuickSortCにあり、ここで">=20"ステートメントがあります。それが変更を実装する正しい方法であるかどうかはわかりません。完全に間違っている可能性があります。私が知っているのは、それが正しくソートされていることだけです。どんな助けでもいいでしょう、ありがとう。

これが私の修正されたquickSortアルゴリズムです：

public void quickSortC(T[] list, int length)
{
    recQuickSortC(list, 0, length - 1);
}//end quickSort

private void recQuickSortC(T[] list, int first, int last)
{
  if (first < last)
  {
      int pivotLocation = partitionA(list, first, last);
      if ((pivotLocation - 1) >= 20)
          recQuickSortC(list, first, pivotLocation - 1);
      else
          insertionSort(list,pivotLocation -1);

      if ((pivotLocation - 1) >= 20)
          recQuickSortC(list, pivotLocation + 1, last);
      else
          insertionSort(list, pivotLocation + 1);
  }
}//end recQuickSort

private int partitionA(T[] list, int first, int last)
{
    T pivot;

    int smallIndex;

    swap(list, first, (first + last) / 2);

    pivot = list[first];
    smallIndex = first;

    for (int index = first + 1; index <= last; index++)
    {
        if (list[index].compareTo(pivot) < 0)
        {
            smallIndex++;
            swap(list, smallIndex, index);
        }
    }

    swap(list, first, smallIndex);

    return smallIndex;
}//end partition


    public void insertionSort(T[] list, int length)
{
    for (int unsortedIndex = 1; unsortedIndex < length;
                                unsortedIndex++)
    {
        Comparable<T> compElem =
                  (Comparable<T>) list[unsortedIndex];

        if (compElem.compareTo(list[unsortedIndex - 1]) < 0)
        {
            T temp = list[unsortedIndex];

            int location = unsortedIndex;

            do
            {
                list[location] = list[location - 1];
                location--;
            }
            while (location > 0 &&
                   temp.compareTo(list[location - 1]) < 0);

            list[location] = (T) temp;
        }
    }
}//end insertionSort

メソッドの横にたくさんのA、B、Cがあることに気付いた場合は、さまざまなクイックソートアルゴリズムを実行する必要があるためです。アルゴリズム内で使用されるすべてのコードを入力します。もっと必要な場合はお知らせください。ありがとうございます。

4

1 に答える 1

2

これは私にはまったく問題ないように見えますが、ピボット距離が最大20であるかどうかをテストする代わりに、クイックソートメソッドを次のように書き直しますif (last - first <= 20) { do insertion sort} else { do normal quicksort}。そうすれば、再帰の「側」ごとに1回ではなく、1回だけチェックを書き込む必要があります。

とは言うものの、Javaで正確なベンチマークを取得することは簡単でも明白でもないという理由だけで、ベンチマークが実際に適切な時間の見積もりを提供していない可能性があります。

于 2012-04-12T23:03:12.590 に答える