1

イントロソートについて読んでいました。私はそのほとんどを理解していますが、ほとんどの実装がそのクイックソート部分に対して1つの再帰を持つ傾向がある理由を理解できません。クイック ソートの標準実装では、クイック ソートに 2 つの再帰を使用します。

Intro sort, main logic:
  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      while (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p, hi, depth_limit);
        hi=p;
      }
      insertionsort(a, lo, hi);
    }

ここで、同じものを次のように変更してみました。

  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      if (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p + 1, hi, depth_limit);
        introsort_loop(a, lo , p-1 , depth_limit);
      }
      insertionsort(a, lo, hi);
    }

私は 2 つの変更を行いました。

私の変更の有無にかかわらず、プログラムは正常に動作するようです。しかし、オンラインのほとんどの実装で単一再帰を使用する理由を知りたかったのです。

4

1 に答える 1

2

クイックソートの多くの実装では、実際に単一の再帰と while ループを使用して、スペースを節約し、時間を節約します。

数学的には、クイックソート アルゴリズムは次のようになります。

 Partition elements.
 Quicksort(elements less than pivot)
 Quicksort(elements greater than pivot)

お気付きかもしれませんが、2 つの再帰呼び出しが戻った後に実行する必要があるコードはありません。

この疑似コードを実際のコードに直接変換するとどうなるかを考えてみましょう。クイックソートが最初に呼び出されたときの元のスタック フレームは、クイックソートへの両方のサブコールが戻るまで残ります。つまり、スタック フレームのメモリは、アルゴリズム全体の実行が終了するまで持続し、多くのスペースを占有します。さらに、クイックソートが縮退した場合 (イントロソートでは不可能ですが、1 秒だけ待ってください)、スタック オーバーフローを引き起こすことになります。

これを回避する賢明な方法は、上記のクイックソートの説明が実際には末尾呼び出しの除去に適していることを理解することです。つまり、クイックソートへの 2 回目の呼び出しを行う代わりに、実装はパラメーターを最初の呼び出しに上書きしてから、while ループに入って、スタック フレームからスペースを再利用することができます。これにより、スペースの使用量が大幅に減少し、再帰呼び出しが不要になります。再帰呼び出しは (法外に高価ではありませんが) 通常、while ループよりも多くのコストがかかります。通常、実装は、配列の 2 つの半分のうち小さい方で再帰呼び出しを開始し、while ループを使用して大きい方の呼び出しを処理します。

上記のイントロソートの実装は、このトリックをクイックソートではなくイントロソートで機能するように適応させているように見えます。再帰呼び出しが 2 つではなく 1 つであることは、アルゴリズムがクイックソートを使用していないことを意味するのではなく、標準のクイックソート最適化手法を使用していることを意味します。

于 2015-08-25T19:20:42.860 に答える