必ず知らないといけない、ソート・アルゴリズムのひとつ。

最悪の計算時間はO(n2)だが、平均計算時間はO(n log n)。他のソート法と比べて、最も高速だといわれているが、安定ソートではない。また、クイックソートの欠点は、順序よく並んだデータでは極端に遅くなってしまう。

<関数名>
  quickSort —- クイックソート

<形式>
  void quickSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  quickSort-test.c

<関数本体>
  quickSort.c

<説明>
  C. A. R. Hoare (ホア) によるクイックソート(quick sort)は、平均的に最も速いソートアルゴリズムだといわれている。クイックソートでは、昇順ソートの場合、
  1. 適当な値 x を選ぶ。その際、配列の x 以下の要素の数と x 以上の 要素の数とはなるべく同程度になるようにする。
  2. x 以下の要素を配列の前半に、x 以上の要素を配列の後半に集める。
  3. 配列の前半が要素数が2以上なら、配列の前半を再帰的にクイック ソートする。
  4. 配列の後半が要素数が2以上なら、配列の後半を再帰的にクイック ソートする。
  このように、配列をつぎつぎに2つにして、それぞれについてソートを行う。
  ご利用の際、データ構造を実際の問題に合わせて修正して欲しい。

Comments are closed.

Post Navigation