現在、整数のリストがあります。このリストには、別のはるかに大きなリスト内の「アクティブな」オブジェクトを指すインデックス値が含まれています。「アクティブな」値の小さなリストが大きくなりすぎると、小さなリストを反復処理して非アクティブになった値を削除するループがトリガーされます。現在、非アクティブな値を無視して 2 番目のリストに追加するだけで、それらを削除します (2 番目のリストが再びいっぱいになると、同じプロセスが繰り返され、最初のリストに戻されます)。
このトリガーが発生した後、クイックソートの実装を使用してリストがソートされます。これはすべてうまくてダンディです。
- - - -質問 - - - - -
ただし、速度が向上する可能性があると思います。並べ替えが行われている間に非アクティブな値の削除を組み合わせることを想像しています。残念ながら、この方法でクイックソートを実装する方法が見つかりません。クイックソートがピボットで機能するという理由だけで、値がリストから削除された場合、ピボットは最終的にリスト内の存在しないスロットにアクセスしようとします。 .
では、2 つの操作を組み合わせる方法についてのアイデアはありますか? これを処理できるクイックソートほど高速なソートアルゴリズムを見つけることができないようです。または、おそらくそれをクイックソートに実装する方法がわかりません...ヒントをいただければ幸いです!
現在何が起こっているかをよりよく理解するためのコード: (現在の状況: 値は 0 から 200 万の範囲であり、同じ値は 2 つとなく、頻繁にソートされるため、一般的にほとんどソートされています)
if (deactive > 50000)//if the number of inactive coordinates is greater than 50k
{
for (int i = 0; i < activeCoords1.Count; i++)
{
if (largeArray[activeCoords[i]].active == true)//if coordinate is active, readd to list
{
activeCoords2.Add(activeCoords1[i]);
}
}
//clears the old list for future use
activeCoords1.Clear();
deactive = 0;
//sorts the new list
Quicksort(activeCoords2, 0, activeCoords2.Count() - 1);
}
static void Quicksort(List<int> elements, int left, int right)
{
int i = left, j = right;
int pivot = elements[(left + right) / 2];
while (i <= j)
{
// p < pivot
while (elements[i].CompareTo(pivot) < 0)
{
i++;
}
while (elements[j].CompareTo(pivot) > 0)
{
j--;
}
if (i <= j)
{
// Swap
int tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
i++;
j--;
}
}
// Recursive calls
if (left < j)
{
Quicksort(elements, elements, left, j);
}
if (i < right)
{
Quicksort(elements, elements, i, right);
}
}