私はクラスのプロジェクトに取り組んでいます。指定された値の挿入ソートに移行するクイックソートを記述する必要があります。私が今では難しかった問題は、なぜ私が期待しているパフォーマンスを得ていないのかを理解することです。挿入のあるクイックソートソートフィニッシュ - どこが間違っていますか?
要件の1つは、1300ミリ秒未満で5,00,000の整数の配列をソートする必要があることです(これは標準的なマシン上にあるため、CPUの速度は問題になりません)。まず、スタックオーバーフローエラー(再帰呼び出しが多すぎます)のために、5,000,000で動作するようにはできません。私がヒープサイズを大きくすると、私はまだそれよりもかなり遅くなっています。
以下はコードです。誰のヒント?事前に
おかげ
public class MyQuickSort {
public static void sort(int [] toSort, int moveToInsertion)
{
sort(toSort, 0, toSort.length - 1, moveToInsertion);
}
private static void sort(int[] toSort, int first, int last, int moveToInsertion)
{
if (first < last)
{
if ((last - first) < moveToInsertion)
{
insertionSort(toSort, first, last);
}
else
{
int split = quickHelper(toSort, first, last);
sort(toSort, first, split - 1, moveToInsertion);
sort(toSort, split + 1, last, moveToInsertion);
}
}
}
private static int quickHelper(int[] toSort, int first, int last)
{
sortPivot(toSort, first, last);
swap(toSort, first, first + (last - first)/2);
int left = first;
int right = last;
int pivotVal = toSort[first];
do
{
while ((left < last) && (toSort[left] <= pivotVal))
{
left++;
}
while (toSort[right] > pivotVal)
{
right--;
}
if (left < right)
{
swap(toSort, left, right);
}
} while (left < right);
swap(toSort, first, right);
return right;
}
private static void sortPivot(int[] toSort, int first, int last)
{
int middle = first + (last - first)/2;
if (toSort[middle] < toSort[first]) swap(toSort, first, middle);
if (toSort[last] < toSort[middle]) swap(toSort, middle, last);
if (toSort[middle] < toSort[first]) swap(toSort, first, middle);
}
private static void insertionSort(int [] toSort, int first, int last)
{
for (int nextVal = first + 1; nextVal <= last; nextVal++)
{
int toInsert = toSort[nextVal];
int j = nextVal - 1;
while (j >= 0 && toInsert < toSort[j])
{
toSort[j + 1] = toSort[j];
j--;
}
toSort[j + 1] = toInsert;
}
}
private static void swap(int[] toSort, int i, int j)
{
int temp = toSort[i];
toSort[i] = toSort[j];
toSort[j] = temp;
}
}
これはどのクラスですか?高校/カレッジ?私は好奇心が強いです –
カレッジ、2年生、私は何か複雑なことを想像しません...私はちょっとしたエラーがあるかもしれないと思います... – addisonj
'moveToInsertion'とは何ですか? – helpermethod