【クイックソート法とは】リストの昇順・降順ソートの原理と計算量【分割統治法】

クイックソート法とは？リストを昇順・降順ソートする手順について解説します。

[latexpage]

【クイックソートとは】リストを昇順・降順ソート
【計算例】昇順ソート
【計算コスト】クイックソートの計算時間
【プログラミング】クイックソートの実装
関連ページ

【クイックソートとは】リストを昇順・降順ソート

クイックソート法は、リストの要素を整列（昇順・降順ソート）するアルゴリズムの１つです。
リスト内のデータから適当な軸要素（pivot）を選び、その軸要素を基準値（しきい値）としてデータ全体を2つのグループに分割します。そして、２つのグループそれぞれでまた基準値を選んでさらに分割し、それを繰り返すことで整列を行います。

このような「分割を繰り返して整列を行う」手法は分割統治法（Divide and conquer）ともいわれます。

–	クイックソートの特徴
1	バブルソートと比較して、データの比較と交換回数が少ない。
2	ランダムに散らばっているデータに対して、最も高速に並べ替えができるため、　よく利用されている。

【計算例】昇順ソート

理解を深めるために、7つの要素をもつリスト[7, 3, 5, 6, 2, 1]の昇順ソートをクイックソート法で行ってみます。

リストの状態	操作
[4, 7, 9, 5, 2, 1, 3]	1番目の要素を軸要素（基準値）とする。
[2, 1, 3], [4], [7, 9, 5]	軸要素（基準値：4）よりも大きい値と小さい値の2グループに分割する（大きいグループは軸要素の右側、小さいグループは左側に移動）。
[2, 1, 3], [4], [7, 9, 5]	それぞれのグループの先頭要素を軸要素（基準値）とする。
[1], [2], [3], [4], [5], [7], [9]	それぞれのグループで軸要素（基準値）よりも大きい値と小さい値の2グループに分割する。
[1, 2, 3, 4, 5, 7, 9]	これ以上グループに分割できないので、ソートを終了する。

今回は、グループの先頭要素を軸要素としましたが、他にも「ランダムに要素を1つ選択」
「ランダムに要素を3つ選択し、その中央値を選択」「先頭と２番目の要素のうち、値が大きいほうを選択」するなど、軸要素の取り方は様々あります。

【計算コスト】クイックソートの計算時間

クイックソートの処理は、軸要素で各データを2分割していきます。

最高効率の計算時間

この処理（データの分割）が最も少ない回数だった場合、データ数をNをすると分割の深さはlog(N)となります。
各深さのデータ数はすべてNなので、総計算時間は「O(N log(N))」になります。

最低効率の計算時間

一方、処理が最も多い回数だった場合（分割が 1:N-1 にで最後まで行われる場合）、分割の深さはNとなり、それぞれのデータの深さは（N , N , N-1 , N-2 , … , 3 , 2）となります。
よって、クイックソートの総計算時間は、「N + N + N-1 + N-2 + … + 3 + 2 = N2/2 + 3N/2 -1=O(N^2)」となります。