出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．
この授業のトップページから レポートのページに移動し， レポートの提出状況を常に確認せよ．
先週まで学習した，簡単だが$O(n^2)$の「遅い」整列アルゴリズムの バブルソート，選択ソート，挿入ソートの要素数10万，20万のときの 実行デモを授業と並行して行う．この中で一番高速な選択ソートを要素数200万で実行し， 計算時間がオーダーの通り，入力の2乗に比例すること確認する．
最後の選択ソートと同じ要素数でクイックソートを実行して実行速度の違いを体感する．
バブルソートなどの単純なアルゴリズムが低速なのは， 近くの要素同士の入れ替えしか行わないためである． 隣合う要素を比較・交換の対象としている限り整列アルゴリズム の計算量は $O(n^2)$ の壁を超えられない（p.194 参照）．
シェルソートではあらかじめ離れた要素を入れ替えておくという 戦略で高速化されている．クイックソートも離れた要素の交換を 効率良く行うことを狙ったアルゴリズムである．
p.203の説明ではまず a[v] に枢軸を移動して， その両側に小さな要素と大きな要素を振り分ける， とあるが，最初に枢軸の値を決めた時点では 枢軸の左に最終的に振り分ける個数が決まっていないので v の値（枢軸の位置）を決めることは出来ず， この順番では処理できない．
この教科書では実際には，
という手順で実装している．
クイックソートも分割統治法で実現できる． 枢軸の左右の部分配列の問題に分割し， 再帰呼出しで処理すればよい．
p.204 Fig.14.2 の(2)にも上で述べたことと同様の 問題がある．実際にa[v]よりも小さい要素を集め終わらないと v の値が決まらないはずである． (2)は上述の 1.2.3. のように書き換えたほうが 実装方法にあっている．書き換えたクイックソートの疑似コードは 以下のようになる．
quick_sort(int a[], int l, int r)
{
if (整列する要素が 1 個のみである)
return;
整列する要素の値の一つを変数 pivot に代入し， /* */
それ以外でpivot より小さい要素を左（左端はa[l]）に，/*(2)*/
pivot より大きい要素を右（右端はa[r]）に集め， /* */
pivot の値を左右の間に置く（a[v]とする） /* */
quick_sort(a, l, v - 1);
quick_sort(a, v + 1, r);
}
図11.1. quick_sort の疑似コード（修正版）
クイックソートでは，配列の一部に対するソートが実行できなければ ならない．quick_sort(int a[], int l, int r) で a[l] から a[r] までの要素がソートできるように 関数 quick_sort を作成する．
quick_sort の疑似コードについても再帰の3つのポイント
を満たしていることがチェックできる．
図11.1 の疑似コードの(2)の部分がクイックソートの仕事のほとんどを占める． この処理を分割(partitioning)と呼ぶ．
ある値がソート後に置かれるべき位置のことを「本来の」位置と 呼ぶと，クイックソートの分割では本来の位置よりも極端に左にある 大きな要素と本来の位置よりも極端に右にある小さな要素を 入れ替えることが戦略の中心になる．この距離の大きな入れ替えで 高速な整列を可能にしている．
アルゴリズムはp.206のFig14.3がわかりやすい． ここでは枢軸として右端 a[r] の値（30）を使う． このため，分割対象の左端が a[l]，右端は a[r-1] となる．分割は要素数が 2 以上の時しか行わないので r-1 が l よりも小さくなることは無い．
左端（l）からスタートして右へ移動するポインタ添字 i と 右端（r-1）からスタートして左へ移動するポインタ添字 j と を使い，a[i]，a[j] を枢軸と比較する． 両方が入れ替えるべき数値がある場所まで進め， a[i]とa[j]を交換する．
これを i と j がぶつかるまで行う．
p.207 2 から 4 行目の 「ポインタiの左側には30よりも小さい要素のみが，ポインタjの右側には 30よりも大きい要素のみが」の部分は後のList 14.1 の実装では 「ポインタiの左側には30以下の要素のみが，ポインタjの右側には 30以上の要素のみが」となっている．枢軸と同じ値が あった場合のためである．クイックソートのアルゴリズムは 同じ値が複数あった場合の理解が難しいので 最初は Fig. 14.3. のように同じ値が存在しない データで考えると良い．
List 14.1 が図11.1. の疑似コードを実現したものである． 分割処理はそれだけで複雑な処理なので，（Fig. 14.3 の処理を行う） partition という名前で関数として独立させてある． クイックソートのプログラムも他の整列プログラムとは違い， 配列，左端，右端を引数として与える処理として書かれる． これを quick_sort_1 として作成し， 他の整列と同じように引数を配列，要素数として呼び出せるように インターフェースを統一するための関数 quick_sort を作成している．
List 14.1 の 7,8 行目で左から挟むポインタ添字 i の値の初期値が l-1， 右から挟むポインタ添字 j の初期値が r でスタートしており， どちらも本来のスタート位置よりも一個前になっている． （i は l からスタートして右に進む．j は a[r] に枢軸があるため， その左の r - 1 からスタートして左に進む） これは i は 14 行目の ++i で前置インクリメントされるので 最初に使われる値が 1 プラスしたものになるためである． （++i は値を使う前にインクリメントする） 同様に j は 17 行目の --j でデクリメントされてからa[j]にアクセスするので 最初に使われる値は 1 減らされたものになるので正しく動作する．
p.208 List14.1 を動作させよ． 練習10.1 と同様の追加を行うことで動作させることができる． （関数 print_array も同時に追加せよ） 但し，プロトタイプ宣言を書く部分（#include <stdio.h> より後，関数定義より前）に 関数 partition, print_array, quick_sort, quick_sort_1 のプロトタイプ宣言を書かなければいけない． それぞれの関数定義の書き出しを参考に正しく記述せよ． また，main でソート関数を呼び出すときの 関数名を quick_sort に変更することも必要である．
ループが行き過ぎないように必ず条件式にかかってループが止まるような 十分大きい値，あるいは十分小さい値を端に入れておく手法を 番兵（sentinel）と言う．
クイックソートがオーダーだけでなく， 実用の場面で高速なのは，pivot の値をレジスタに 入れるなど，計算機の設計に向いた高速化が行える ことなどが理由である．
クイックソートの実行時間にはばらつきがある． 枢軸として選ばれる値が配列を2等分する分割が 行えるような値（中央値）であれば理想的だが， 枢軸の値は制御できない．最悪なのは枢軸の 片方に全てのデータが行く場合で，整列済みの 配列が入力として与えられたときににこの ケースになる．このときのオーダーは $O(n^2)$ となる．また，このときの再帰呼出しの深さも 最悪になり $O(n)$ となる．
スタックが深くなりすぎて処理が不可能になる， という状況を回避する方法として，
ことが考えられる．さらに 2. は以下の 2つのレベルで対処が考えられる．
この 2 は抜本的な改善が期待できる．具体的には 左端と中央と右端の3つの数値を調べ， 中間の順位の値を枢軸として使う実装が よく用いられる．
配列の長さが 1 になるまでクイックソートを 行うのではなく，ある程度小さくなったら 挿入ソートに切り替えるように実装する方法 がある．
第 11 回課題「合計の計算」 を提出せよ．