Pythonでのマージソートについて説明する

マージソートはソート手法です。これは、時間計算量が（ n logn ）の効率的な並べ替えアルゴリズムです。 ）ここで、nはソートされる配列の長さです。

マージソートは、DivideandConquersパラダイムに従うアルゴリズムです。配列を2つの等しい半分に連続的に分割します。その後、それぞれが1つの要素を持つリストの並べ替えを開始し、並べ替えられたリストを継続的にマージして、完全な並べ替えリストを形成します。

したがって、ソートされた配列を取得します。

例

紫色のボックスと黒い矢印は、リストが2つに分割されていることを示しています。

緑色のボックスと赤い矢印は、並べ替えられた2つのリストのマージを示しています。

マージソートの実装

リストを2つに分割するのは非常に簡単で、要素が1つだけになるまで再帰的に実行されます。後でマージ手順が実行されます。これは、実際には、2つのソートされたリストをマージするロジックを適用する場所です。

例

マージ関数は、マージされる2つのソートされた配列を取ります。 a1の最前面の要素は、a2の最前面の要素と比較されます。 2つのうち最小のものがリストcに追加され、その配列のポインターがインクリメントされます。

def merge(a1,a2):
   c=[]
   x=0
   y=0
   while(x<len(a1) and y<len(a2)):
      if(a1[x]<a2[y]):
         c.append(a1[x])
         x+=1
      else:
         c.append(a2[y])
         y+=1
   while(x<len(a1)):
      c.append(a1[x])
      x+=1
   while(y<len(a2)):
      c.append(a2[y])
      y+=1
   return c

def mergesort(array):
   if(len(array)==1):
      return array
   mid=(len(array))//2
   a1=mergesort(array[:mid])
   a2=mergesort(array[mid:])
   return merge(a1,a2)
array=[2,3,1,5,4,6,8,10,7,9]
print(mergesort(array))

出力

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]