よく使われるソートアルゴリズムの比較と分析

1. よく使われるソートアルゴリズムの簡単な説明

以下では、主にソートアルゴリズムの基本的な概念と原則から始めて、アルゴリズムの時間計算量、空間計算量、アルゴリズムの安定性、速度を分析および比較します。ソートする問題の大きさ（レコード数n）に応じて、ソート処理中に必要なメモリ空間も異なるため、ソートアルゴリズムは[内部ソート]と[外部ソート]の2つに分類されます。

内部ソート: ソート中にすべてのデータ要素がコンピューターのランダム アクセス メモリ RAM に保存されるプロセスを指します。

外部ソート: ソートするレコードの数が非常に多いため、メモリが一度にすべてのレコードを保持できず、ソート処理で外部メモリにアクセスする必要があります。

まず、一般的なソートアルゴリズムの分類関係を理解し​​ましょう（図1-1参照）

図1-1 一般的なソートアルゴリズム

2. 内部ソート関連アルゴリズム

2.1 挿入ソート

基本的な考え方は、ソートするデータ要素を、以前にソートされたシーケンスの適切な位置に挿入して、ソートするすべてのデータ要素が挿入されるまでデータ要素の順序を維持することです。

2.1.1 直接挿入ソート

コアアイデア: 挿入する i 番目のデータ要素のキー コードを、以前にソートされた i-1、i-2、i-3、… データ要素の値と順番に比較します。この線形検索方法を使用して、i 番目のデータ要素の挿入位置を見つけ、元の位置にあるデータ要素を、すべてがソートされるまで後方にシフトします。

直接挿入ソートでは、同じキーワードを持つデータ要素は元の位置に残るため、アルゴリズムは安定しています。時間計算量の最悪値は平方オーダー O(n2) で、空間計算量は定数オーダー O(l) です。

Python ソースコード:

 # -------------------------直接挿入ソート--------------------------------  
 def insert_sort(データリスト):
 #配列内のすべての要素を走査します。デフォルトではインデックス要素0がソートされるので、1から開始します。
 xが範囲(1, len(data_list))内にある場合:
 # 要素をソートされた事前順序配列と順番に比較します。要素が小さい場合は、交換します。
 #range(x-1,-1,-1): x-1から0まで逆順にループします
iが範囲(x-1, -1, -1)内にある場合:
 #判定:条件を満たせば交換
 data_list[i] > data_list[i+1]の場合:
 temp = データリスト[i+1]
 データリスト[i+1] = データリスト[i]
 データリスト[i] =一時 

2.1.2 シェルソート

基本的な考え方は、インデックスの特定の増分に従ってレコードをグループ化し、直接挿入ソート アルゴリズムを使用して各グループをソートすることです。増分が徐々に減少するにつれて、各グループに含まれるキーワードの数が増えていきます。増分が 1 に減少すると、ファイル全体が 1 つのグループに分割され、アルゴリズムが終了します。

シェルソートの時間計算量は O(n2) より優れています。ただし、複数の挿入ソートでは、最初の挿入ソートは安定していますが、異なる挿入ソートプロセスでは、同じ要素がそれぞれの挿入ソートで移動される可能性があるため、シェルソートは不安定です。

Python ソースコード:

 # -------------------------シェルソート-----------------------------  
 def insert_shell(データリスト):
 # ステップ値を初期化します。ここではシーケンス長の半分を使用して値を割り当てます。
グループ= int (len(data_list)/2)
 #*** レイヤーループ:グループ値を順番に変更してリストをグループ化します
 グループ> 0 の場合:
 #下: 直接挿入ソートの考え方を使用してグループ化されたデータをソートする
 #range( group ,len(data_list)):グループから開始
iが範囲(グループ、len(データリスト))内にある場合:
 #range(x- group ,-1,- group ): x- groupから開始し、選択した要素を逆順に比較します。比較する各要素はグループで区切られます。  
 jが範囲内(i-グループ、-1、-グループ)の場合:
 #グループ内の2つの要素が交換条件を満たす場合、それらは交換されます
 data_list[j] > data_list[j+ group ]の場合:
 temp = data_list[j+グループ]
 data_list[j+グループ] = data_list[j]
 データリスト[j] =一時 
 #Whileループ条件が半分になった
グループ= int (グループ/ 2)

2.2 選択ソート

中心的なアイデア: 各スキャンで、ソートするデータ要素から最小または最大のキー コードを持つ要素を選択し、ソートするすべてのデータ要素が終了するまで、ソートされたシーケンスの最後に配置します。

2.2.1 直接選択ソート

基本的な考え方は、各位置でキー コードが最も小さいデータ要素を選択することです。つまり、最初の位置の要素と交換する最小の要素を選択し、次に残りの要素から 2 番目の位置の要素と交換する最小の要素を選択し、最後から 2 番目の要素が最初の要素と比較されるまでこれを続けます。

基本的な考え方によれば、スキャンが実行されるたびに、現在の要素が要素より小さく、この小さい要素が現在の要素と等しい要素の後ろに現れる場合、それらの位置が入れ替わります。したがって、直接選択ソートは不安定であり、その時間計算量は平方オーダー O(n2)、空間計算量は O(l) です。

Python ソースコード:

 # -------------------------直接選択ソート-----------------------------  
 def select_sort(データリスト):
 # シーケンス内の各要素を反復処理する
i が範囲(0, len(data_list))内にある場合:
 #現在の位置の要素をこのサイクルの最小値として定義します
 最小値 = データリスト[i]
 #この要素を残りの要素と比較して最小の要素を見つけます
jが範囲(i+1, len(data_list))内にある場合:
 data_list[j] < 最小値の場合:
 temp = データリスト[j];
 data_list[j] = 最小値;
 最低 =温度 
 #比較後に得られた真の最小値を現在の位置に割り当てる
 data_list[i] = 最小値

2.2.2 ヒープソート

ヒープソートは、直接選択ソートよりも効果的な改善です。

基本的な考え方は、すべてのデータをヒープ内に構築し、最新のデータをヒープの最上部に配置し、ヒープの最上部のデータ要素をシーケンスの最後の要素と交換し、次にヒープを再構築し、データを交換するなどして、すべてのデータ要素のソートを実現することです。ヒープソートを完了するには、ヒープの構築とヒープの調整という 2 つのアクションが必要であり、このプロセスが繰り返されます。

ヒープソートでは、同じ値を持つ 2 つの要素の位置が入れ替わる可能性があるため、不安定です。平均時間計算量は 0(nlog2n)、空間計算量は O(l) です。

Python ソースコード:

 # -------------------------ヒープソート--------------------------------  
 #***********左と右のリーフノードを取得します**********
定義左（i）：
 2*i + 1を返す
  
定義権利(i):
 2*i + 2を返す
  
 #*********** 最大ヒープを調整する **********
 #data_list: 調整するシーケンス length: シーケンスの長さ i: 調整するノード
def adjust_max_heap(データリスト、長さ、i):
 #現在のシーケンスの***値の添え字を保存するためのint値を定義します
 最大 = i
 #ループ操作を実行: 2 つのタスク: 1. *** 値の添え字を見つける。2. *** 値を親ノードと交換する
 一方1:
 #シーケンスの左と右のリーフノードの添え字を取得します
左、右= LEFT (i)、 RIGHT (i)
 #左葉ノードの添え字がシーケンス長より小さく、左葉ノードの値が親ノードより大きい場合、左葉ノードの添え字を最大のものに代入します。
 ( left < length)かつ(data_list[ left ] > data_list[i]) の場合:
 最大 =左 
 #print( '左のリーフノード' )
それ以外：
 最大 = i
 #右リーフノードの添字がシーケンスの長さより小さく、右リーフノードの値が親ノードより大きい場合、右リーフノードの添字の値を最大のノードに割り当てます。
 (右辺< 長さ)かつ(データリスト[右辺] > データリスト[最大]) の場合:
 最大 =右 
 #print( '右のリーフノード' )
 #最大がiと等しくない場合は、現在の親ノードが最大値ではないため、交換する必要があることを意味します。
 （最大!= i）の場合:
 temp = データリスト[i]
 data_list[i] = data_list[最大]
 data_list[最大] = temp  
 i = 最大
 #print(最大)
続く 
それ以外：
 壊す
  
 #********** 大きなトップヒープを作成する **********
 def build_max_heap(データリスト):
 長さ = len(データリスト)
 xが範囲内( int ((length-1)/2),-1,-1):
 adjust_max_heap(データリスト、長さ、x) 
  
 #*********** ヒープソート **********
 def heap_sort(データリスト):
 #まず、最大値がルートノードにあることを確認するために最大ヒープを作成し、親ノードの値がリーフノードよりも大きくなるようにします。
 build_max_heap(データリスト)
 #i: 現在のヒープ内のシーケンスの長さ。シーケンスの長さに初期化されます
 i = len(データリスト)
 #ループを実行: 1. 毎回ヒープの最上位要素を取り出して、シーケンスの末尾に配置します (len-1、len-2、len-3...)
 # 2. ヒープが最大ヒープの特性を満たし続けるようにヒープを調整し、ヒープ内のシーケンスの長さをリアルタイムで変更することに注意を払います。
 i > 0 の場合:
 temp = データリスト[i-1]
 データリスト[i-1] = データリスト[0]
 データリスト[0] =一時 
 #ヒープ内のシーケンスの長さを1減らす
 私 = 私-1
 #最大ヒープを調整する
 調整最大ヒープ(データリスト、i、0)

2.3 交換ソート

基本的な考え方: 名前が示すように、ソートするデータ要素のグループでは、キー コードが位置の順序で相互に比較されます。逆の順序になっている場合は、データ要素の順序が整うまで 2 つのデータ要素が交換されます。

2.3.1 バブルソート

コアアイデア: ソートするデータ要素のグループでは、各データ要素は重みのあるバブルと見なされます。軽いバブルは重いバブルの下には置けないという原則に従って、ソートされていないすべての要素が比較され、隣接する 2 つの要素ごとに上から下に調整され、重い要素が下に沈み、軽い要素が上に上がります。

基本的な考え方によれば、2 つの要素の順序がソート要件と逆の場合にのみ 2 つの要素の位置が交換され、それ以外の場合は変更されないため、バブル ソートは安定しています。時間計算量は2乗O(n2)、空間計算量はO(l)です。

Python ソースコード:

 # -------------------------バブルソート--------------------------------  
バブルソートの定義(データリスト):
 長さ = len(データリスト)
 #シーケンスの長さは長さであり、長さ-1ラウンドの交換が必要です
xが範囲(1,長さ)内にある場合:
 #交換の各ラウンドで、シーケンスの左と右の要素を比較します
#各交換ラウンドでは、シーケンスの***要素は***でなければならないため、各ループラウンドはシーケンスのソートされていない位置まで実行できます。
 iが範囲(0,長さ-x)内にある場合:
 data_list[i] > data_list[i+1]の場合:
 temp = データリスト[i]
 データリスト[i] = データリスト[i+1]
 データリスト[i+1] =一時 

2.3.2 クイックソート

クイックソートはバブルソートの本質的な改良です。

中核となるアイデア: インプレースソート、分割統治、大規模再帰アルゴリズムです。つまり、スキャン後、参照ポイントのデータ要素の左側の要素がそれより小さく、右側の要素がそれより大きいことを確認してから、参照ポイントの左側と右側に要素が 1 つだけになるまで、再帰的な方法で左側と右側の要素を処理します。

クイックソートは、最悪の場合の時間計算量が O(n2)、空間計算量が O(log2n) の不安定なアルゴリズムです。

Python ソースコード:

 # -------------------------クイックソート--------------------------------  
 #data_list: ソートするシーケンス。start はソートの開始インデックス、 end はシーケンスの最後のインデックスです。  
 #長さが length のシーケンスの場合: start = 0; end = length-1
 def quick_sort(data_list,start, end ):
 開始 <終了の場合:
 i 、 j 、ピボット = 開始、終了、データリスト[開始]
 i < j の場合:
 #右から始めて左に進み、ピボットより小さい最初の値を探します
 i < jかつdata_list[j] >= pivot の場合:
 j = j-1
 #ピボットより小さい値を左に移動する
 i < jの場合:
 データリスト[i] = データリスト[j]
 私 = 私+1
 #左から右へ進み、ピボットより大きい最初の値を見つけます
 i < jかつdata_list[i] < pivot の場合:
 私 = 私+1
 #ピボットより大きい値を右に移動する
 i < jの場合:
 データリスト[j] = データリスト[i]
 j = j-1
 #ループ終了後はi=jとなります。このとき左側の値は全てピボットより小さく、右側の値は全てピボットより大きくなります。
 #ピボットの位置は正しく移動されたので、左側と右側のシーケンスをさらにソートするには、この関数を呼び出すだけです。
 #再帰呼び出し関数: 左シーケンス: 0 から i-1 まで //右シーケンス: i+1 から終了まで 
 data_list[i] = ピボット
# 左側のシーケンスのソートを続行します
 クイックソート(データリスト、開始、i-1)
 # 正しい順序でソートを続ける
 quick_sort(データリスト、i+1、終了)

2.4 マージソート

基本的な考え方は、データ シーケンスを再帰的に短いシーケンスに分割することです。つまり、1 を 2 に、2 を 4 に分割します。1 のグループが 1 つしかない場合は、これらのグループを並べ替えてから、1 つずつ元のシーケンスにマージします。元のシーケンスが完全に並べ替えられるまで、マージを続けます。

マージ プロセスにより、現在の 2 つの等しい要素のうち、前の要素が結果シーケンスの前に保存されることが保証されます。したがって、マージ ソートは安定しており、時間の計算量は O(nlog2n)、空間の計算量は O(n) です。

Python ソースコード:

 # -------------------------マージソート--------------------------------  
 #これはマージ機能です
# シーケンス data_list[ first ...mid] をシーケンス data_list[mid+1... last ] とマージします。
 def mergearray(data_list, first ,mid, last , temp ):
 #i、j、kにそれぞれ値を割り当てる
 i,j,k =最初、中央+1,0
 #両側に数字がある場合は、比較して小さい方の数を取ります
 (i <= mid)かつ(j <= last ) の場合:
 data_list[i] <= data_list[j]の場合:
 temp [k] = データリスト[i]
 私 = 私+1
 ｋ＝ｋ＋１
それ以外：
 temp [k] = データリスト[j]
 j = j+1
 ｋ＝ｋ＋１
 #左のシーケンスにさらに数字がある場合
 (i <= mid) の間:
 temp [k] = データリスト[i]
 私 = 私+1
 ｋ＝ｋ＋１
 #正しい順序で数字がさらにある場合
 (j <= last )の間:
 temp [k] = データリスト[j]
 j = j+1
 ｋ＝ｋ＋１
 #temp内の順序付けられた要素をdata_list 内のソートされるシーケンスに割り当てて、部分的に順序付けします。
 xが範囲(0,k)内にある場合:
 data_list[最初+x] = temp [x]
 # これはグループ化機能です
def merge_sort(data_list, first , last , temp ):
 最初<最後 の場合:
 真ん中 = ( int )((最初+最後) / 2)
 # 左のシーケンスを順番に作成します
 merge_sort(データリスト、最初、中間、一時)
 # 正しい順序で並べる
 merge_sort(データリスト、mid+1、 last 、 temp )
 #2つの順序付けられたシーケンスをマージする
 mergearray(データリスト、最初、真ん中、最後、一時)
 # マージソート機能
def merge_sort_array(データリスト):
 #長さlen(data_list)の空のリストを宣言します
temp = len(データリスト)*[なし]
 #マージソートを呼び出す
 merge_sort(データリスト、0、長さ(データリスト)-1、一時)

2.5 基数ソート

基本的な考え方は、まず下位ビットをソートして収集し、次に上位ビットをソートして収集し、これを最後のビットまで繰り返すというものです。

Python ソースコード:

 # -------------------------基数ソート--------------------------------  
 #ソートの数を決定する
#ソート順はシーケンス内の桁数に関係します
定義 radix_sort_nums(データリスト):
 最大数 = データリスト[0]
 #シーケンス内の***番号を見つける
data_list内のxの場合:
 maxNum < xの場合:
 最大数 = x
 #シーケンスの最初の要素の桁数を決定する
 回 = 0
 (maxNum > 0) の場合:
 最大数 = ( int )(最大数/10)
 回 = 回 + 1
返却時間
#numのデータを低い位置から高い位置まで検索します
get_num_pos(num,pos)を定義します。
戻り値(( int )(num/(10**(pos-1))))%10
 # 基数ソート
定義radix_sort(データリスト):
 count = 10*[None] #各バケットのデータ統計を保存する
 bucket = len(data_list)*[None] #ソート結果を一時的に保存する
#ループを低から高へ実行します
posがrange(1,radix_sort_nums(data_list)+1 の場合):
 # 各バケットのデータ統計を空にする
xが範囲(0,10)の場合:
カウント[x] = 0
 #現在の位置にある要素の数を数えます (1 桁、10 桁、100 桁など)
 xが範囲(0,len(data_list))内にある場合:
 #各バケットに入れられる要素の数を数える
 j = get_num_pos( int (データリスト[x]),pos)
カウント[j] =カウント[j]+1
 # count [i]はi番目のバケットの右境界インデックスを表します
xが範囲(1,10)の場合:
カウント[x] =カウント[x] +カウント[x-1]
 #データを1つずつバケットに入れる
xが範囲(len(data_list)-1,-1,-1)内にある場合:
 #要素のK番目の桁を見つける
 j = get_num_pos(データリスト[x]、pos)
 #対応するバケットに入れます。count [j] - 1 は j 番目のバケットの右境界インデックスです。
 バケット[ count [j]-1] = data_list[x]
 #対応するバケット読み込みデータインデックス - 1
カウント[j] =カウント[j]-1
 # 割り当てられたバケットにデータを流し込みます。これで、テーブルは現在の桁数に従ってソートされます。
 xが範囲(0,len(data_list))内にある場合:
 data_list[x] = バケット[x]

3. ソートアルゴリズムテスト

図3-1 一般的なソートアルゴリズムの検定統計量

4. ソートアルゴリズムの比較と分析

表4-1 各種ソートアルゴリズムの比較

[直接挿入ソート]はバブルソートの改良版です。バブルソートよりも高速ですが、少量のデータ（1000）のソートにしか適していません。

[シェルソート]は比較的シンプルで、少量データ（5000未満）のソートに適しています。直接挿入ソートやバブルソートよりも高速です。そのため、シェルソートは少量データのソートに適しており、高いソート速度は要求されません。

[直接選択ソート]は、バブルソートアルゴリズムと同様に、n値が小さい場合に適しています。ソートアルゴリズムの開発の初期段階にあり、実際のアプリケーションで使用される可能性は低いです。

[ヒープソート]は、数百万以上のデータ量をソートするのに適しています。この場合、再帰的に設計されたクイックソートやマージソートを使用すると、スタックオーバーフローが発生する可能性があります。

[バブルソート]は最も遅いソートアルゴリズムであり、ソートアルゴリズムの開発の初期段階にあります。このアルゴリズムが実際のアプリケーションで使用される可能性は比較的低いです。

[クイックソート] は再帰的で最も高速なソートアルゴリズムですが、メモリが限られている場合には適していません。また、基本的に順序付けられたデータシーケンスをソートする場合、クイックソートは遅くなります。

[マージソート]はヒープソートよりも高速ですが、2倍のストレージスペースが必要です。

[基数ソート]はスケールnの値が非常に大きい場合に適していますが、整数のソートにのみ適用できます。浮動小数点数に対して基数ソートを実行する場合は、浮動小数点数の保存形式を指定してから、何らかの方法で整数にマッピングし、再度マッピングする必要があり、複雑なプロセスになります。