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

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

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

クイックソート法は、リストの要素を整列(昇順・降順ソート)するアルゴリズムの1つです。
リスト内のデータから適当な軸要素(pivot)を選び、その軸要素を基準値(しきい値)としてデータ全体を2つのグループに分割します。そして、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番目の要素のうち、値が大きいほうを選択」するなど、軸要素の取り方は様々あります。

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

クイックソートの処理は、軸要素で各データを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)」となります。

平均計算時間

平均的な計算時間は、「O(N log(N))」 となります。
※データがランダムに散りばめられている場合(すべて異なる一様分布のデータ)

【プログラミング】クイックソートの実装

プログラミング言語でクイックソートを実装する方法については、言語別に下記事で紹介しています。

メディアを追加

詳細記事
1 【Python】クイックソート法を実装
おすすめ記事
1 【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
2 【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験
コンピュータ
技術雑記

コメント

タイトルとURLをコピーしました