「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#22 - Qiita

【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」 前回の記事はこちら 6-6 クイックソート 最も高速なソートの一つとして知られており、広く利用されています。 クイックソートはグループわけの基準である枢軸を境に以上以下のグループで分ける手法を取ります。 枢軸は任意です。 最初に配列を2つのグループに分割する手順を考えます。 任意の数字を枢軸とした際、双方向バブルソートと同じように左右それぞれから走査し、枢軸と比較して以上、以下のグループ分けをします。添字について、左端側をpl、右端側をprとします。 この時配列aについて ・枢軸以下のグループ:a[0], ・・・, a[pl - 1] ・枢軸以上のグループ:a[pr + 1],・・・, a[n - 1] というグループ分けができます。 また、pl > pr + 1 のときに限り ・枢軸と一致するグループ：a[pr + 1],