C言語で書くクイックソート
試験に出てきたので、復習も兼ねて。C言語は久しぶりだったので色々駄目でしたよ。（笑）
クイックソートとは、データの中のある適当な数値を軸として、各データを調べます。調べながら各データを軸より小さいものは左側（array[0]側）、大きいものは右側（array[8]側）に分けていきます。こうすることで、軸、軸より小さい、軸より大きい、と3つに分けることができます。
この分ける作業を繰り返すことで、そのうちに軸より小さい、軸より大きい、というグループのデータ数が１つだけになります。そうなったらもう分ける必要がないので終了とします。
実際に書いてみましょう。以下のデータを並び替えしたいと思います。わかりやすいように、一桁目を1〜9という数値にしました。
次に、クイックソートのやり方です。
クイックソート関数には、小さなものを調べる、大きなものを調べる、といった位置を記憶させる変数を引数に持たせ、あとは並び替えたいデータの配列へのポインタを引数にしましょう。
はじめに終了条件を書きます。
そして、検索開始・終了位置を覚えていかないといけないので、位置を違う変数に記憶させます。さらに軸を設定します。今回は、軸を一番左側のデータとします。
まず、小さい・大きいという分別方法を考えたいと思います。クイックソートのやり方ですと、分けた後には【小さいグループ】【軸】【大きいグループ】となります。そこで、小さいグループを見つける係りと、大きいグループを見つける係りで分け、入れ替えてしまいます。すると、左には小さいグループ、右には大きいグループと分けることが出来ます。
軸より小さい、軸より大きい、という条件見つけるまではループさせます。この時に小さいものを見つける係りと、大きいものを見つける係りで分担させます。そして見つけたら入れ替えます。
この作業を、見つける係りがすれ違うまで繰り返します。すれ違ったらループを終了させます。
このあと今回は軸が一番左側としているので、すれ違った地点と軸を入れ替えます。こうすることで、【軸】【小さいグループ】（ここがすれ違った地点）【大きいグループ】が、（すれ違った地点）【小さいグループ】【軸】【大きいグループ】となり、大体の並び替えが終了します。あとは大体並び替えされている【小さいグループ】、【大きいグループ】にもクイックソートをかけます。
これを終了条件になるまで繰り返せば、クイックソートは完了です。
