C言語でクイックソート

クイックソートとは

クイックソートとは、O(n*log(n)) ソートの一つ。
比較ソートの中では最も高速なアルゴリズムの一つ。
再帰を用いるアルゴリズムなので、停止条件(ベースケース)の実装を忘れずに。
詳しくは クイックソート - Wikipedia を参照してください。

 

 

軸要素の選び方

今回、採用した軸要素の選び方は「最初の異なる二要素の内、大きい方」とした。
クイックソートのベースケースは「軸要素が見つからない時」なので、今回は「配列の全要素が等しい時(配列長が 1 の場合も含む)」にベースケースとなる。

 

ソースコード

quick sort implemented with C